Let q,n,k be positive integers with q>1, n>3.
(k choose 2)-1=(qn-1)/(q-1)has no solutions.
(k choose 2)-1=qn+1has only the solution qn=64, k=12.
Richard Guy remarks that, for fixed n, these equations are presumably of the sort to which Faltings' theorem applies, in which case there are only finitely many solutions for each n. But surely these equations are less difficult than Fermat's last theorem!
Hering (LMSLN 165 (1992), 448-458) has obtained further results on these equations, including the fact that the second equation has only finitely many solutions if q<47 or if n is divisible by 3.
This problem is due independently to Jacques Tits and me.
Show that there is no generalised quadrangle with parameters s,t, where s is finite and greater than 1, and t is infinite.
A generalised quadrangle is a geometry of points and lines, with any two points on at most one line, such that if point P is not on line L, then P is collinear with a unique point of L. It has parameters s,t if each line contains s+1 points and each point lies on t+1 lines. If s=1, it is a complete bipartite graph. The finiteness of t when s=2,3,4 was shown by Cameron, Kantor, and Cherlin respectively; a simplified proof for the case s=3 was given by Brouwer. Cherlin's argument (Discrete Math. 291 (2005), 73-79), gives a general method which can in principle deal with larger values of s (with ever-increasing amounts of hard labour).
Let G be an infinite graph. List all labelled n-vertex subgraphs of G (a finite list, for each n), and let dn be the average density of edges in the list (that is, the total number of edges divided by (n choose 2) times the number of graphs in the list. Does the limit of dn, as n tends to infinity, exist?
This problem is due to P. J. Cameron, P. Frankl and W. M. Kantor, Europ. J. Combinatorics 10 (1989), 149-160.
Let F be an intersecting family of subsets of {1,2,...,n} which is maximal (that is, |F|=2n-1) and regular (each point lies in the same number of elements of F). Let m be the size of the smallest set in F. It is known that m>=(1/2)log n+c; examples are known with m about the square root of n. What is the truth?
This problem has been solved by Aaron Meyerowitz (Europ. J. Combinatorics 16 (1995), 491-501); doi: 10.1016/0195-6698(95)90004-7, who showed that the lower bound is correct.
This problem was posed by Paul Erdös and me (Number Theory, ed. R. Mollin, de Gruyter 1990).
Let f(n) be the number of sequences
1<=a1<...<at<=nwhere ai doesn't divide aj for i<j. Prove that the limit, as n tends to infinity, of f(n)1/n exists.
The limit should be about 1.58.
This problem was posed by A. Gyárfás.
For which n and q does there exist a permutation p of the point set of the finite projective space PG(n,q) with the property that, for any hyperplane H, there exists a hyperplane H' meeting p(H) in the empty set? It is known that the answer is "yes" for n=2 (asymptotically, almost all permutations have this property), and "no" for n>q (by a short argument due to A. Blokhuis).
For odd n, let Wn be the space of binary words of length n and even weight. Let f(n) be the maximum codimension of a subspace U of Wn such that the union of all cyclic shifts of U is equal to Wn. It is known that f(n)>=2 for n>3, but little more is known. Does f(n) tend to infinity as n does? Or is f(n) equal to 2 for infinitely many n?
This problem is due to Marion Kimberley (as a result of an incorrect statement by a student).
An affine design is a resolvable 2-design in which any two non-parallel blocks meet in a constant number y of points. What happens if we replace "non-parallel" by "non-disjoint" in this definition? In addition to affine designs, there are resolvable designs with lambda=1 (and y=1), for example Kirkman systems. No others are known: the first unknown case is a resolvable 2-(70,10,6) design with y=2.
For fixed s and large n, the best known upper and lower bounds for the maximum number of permutations of an n-set with s different distances are both roughly (cn/s)2s (with different values of c). Find the correct value.
What is the probability that, in a random sum-free set S of natural numbers, 2 is the only even number in S? (Is it zero or not?) The probability measure is defined by the following rule. Consider the natural numbers in their usual order. If n is the sum of two numbers in S, then n is not in S; otherwise, decide on the toss of a fair coin. It is known that the probability that S contains no even number is non-zero, but the present problem is a bit more delicate.
This problem has been solved by Neil Calkin and me (Combin. Probab. Comput. 7 (1998), 27-32). We showed that the probability is strictly positive and gave a heuristic estimate for it.
This problem is due to Jeanette Janssen and me.
(a) It is known that, for almost all Latin squares of order n (that is, a proportion tending to 1 as n tends to infinity), the rows of the square (regarded as permutations) generate either the symmetric group Sn or the alternating group An. Is this statement still true if the squares are normalized so that the first row is the identity permutation?
(b) Is it true that the distribution of the number of rows of a random Latin square which are odd permutations is "approximately" binomial Bin(n,1/2)?
(c) Let M(n) and m(n) denote the maximum and minimum numbers of extensions of a 2×n Latin rectangle to an n×n Latin square. Find a good upper bound for M(n)/m(n).
(d) How do you choose a random Latin square of order n?
In connection with (b), Häggkvist and Janssen (Discrete Math. 157 (1996), 199-206) have shown that the proportion of Latin squares in which all rows are even permutations is exponentially small. This was the form asked at the Conference; the strengthened version was suggested by Jeannette Janssen.
A Markov chain method for choosing a random Latin square was given by Jacobson and Matthews (J. Combinatorial Design 4 (1996), 405-437).
I currently conjecture that the ratio in (c) tends to 1.
For even n, the number of permutations of {1,...,n} with all cycles of even length is equal to the number of permutations with all cycles of odd length. Find a bijective proof of this fact.
After the conference, this problem was solved independently by Richard Lewis and Simon Norton. Their joint paper appears in the volume of contributed papers (Discrete Math. 138 (1995), 315-318).
This problem is due to Paul Erdös and me.
Let s(n) be the number of sum-free subsets of {1,...,n} (that is, containing no solution to x+y=z). Show that there exist constants c' and c'' such that s(n)/2n/2 tends to c' or c'' as n tends to infinity through odd or even values respectively.
This problem has been solved by Ben Green, Bulletin of the London Mathematical Society 36 (2004), 769-778 (doi: 10.1112/S0024609304003650); and by Alexander Sapozhenko, Discrete Mathematics 308 (2008), 4361-4369 (doi: 10.1016/j.disc.2007.08.103
This problem is due to Cheryl Praeger and me: see Discrete Math. 118 (1993), 33-43, and Finite Geometry and Combinatorics, CUP 1993.
A t-(v, k, lambda) design has v points and a collection of blocks of size k, any t points lying in exactly lambda blocks. Terms such as "block-transitive" apply to the action of the automorphism group.
(a) Show that there is no block-transitive 6-design.
(b) Show that a block-transitive, point-imprimitive 3-design satisfies v<=(k choose 2)+1.
(c) Is there a block-transitive 2-(infty,4,1) design which is not point-transitive?
The design asked for in (c) has been constructed by David Evans, J. Combin. Des. 12 (2004), 459-465. Part (b) has been answered in the affirmative by Avinoam Mann and Ngo Dac Tuan, Geom. Dedicata 88 (2001), 81-90.
Which graphs G have the property that, in the class X(G) of graphs having no induced subgraph isomorphic to G, the limiting probability of connectedness is strictly between zero and one (in either the unlabelled or the labelled case)? (The smallest G with this property is the path of length 3; the probability of connectedness in X(G) is 1/2 if the number of vertices is greater than one.)
See Combin. Probab. Comput. 8 (1999), 31-43 and Electron. J. Combin. 7 (2000), #R33 for more information.
Find good asymptotic estimates for the numbers of
The last class of graphs are defined as follows: Take a permutation p of {1,...,n}, and join i to j whenever (i-j)(p(i)-p(j))>0.
Added 24/09/2007: The first question has been solved in the labelled case. The solution is here.
As an example of a "typical" automorphism of the space of periodic integrable functions (acting on Fourier coefficients), W. Rudin (Acta Math. 95 (1956), 39-56) considered the permutation of the integers defined by
3n -> 2n, 3n±1 -> 4n±1Describe the cycles of this permutation. In particular, does it have only finitely many finite cycles?
In fact, this problem is older: it is the "original Collatz problem" from the 1930s (before the famous "3x+1 problem"), though never published by Collatz. A paper by Jeff Lagarias gives details.
This problem is due to Donald Keedwell.
Suppose that x1,...,xm, y1,...,ym are positive integers such that there exists a bipartite graph with vertex degrees x1,...,xm in one bipartite block and y1,...,ym in the other. (This is equivalent to asserting that the conditions of the Gale--Ryser theorem are satisfied.) Suppose further that all the xi and yj are greater than 1. Show that there is a bipartite graph having these vertex degrees, which has two proper edge-colourings such that
This problem has been solved by Rong Luo, Wen-An Zang and Cun-Quan Zhang, Combinatorica 24 (2004), 641-657; doi: 10.1007/s00493-004-0039-2
This problem is due to Paul Fisher and me.
Call a strongly regular graph Gamma abnormal if it contains vertices x,y,z such that x is not adjacent to y or z, y and z are adjacent, and Gamma(x) intersect Gamma(y)=Gamma(x) intersect Gamma(z), where Gamma(x) denotes the set of neighbours of x.
Does an abnormal strongly regular graph exist?
Such a graph must have lambda>=mu, and not all the induced subgraphs on the non-neighbours of a vertex can be edge-regular. Any strongly regular graph with lambda>0 and mu=1 is abnormal; but no such graphs are known.
This problem is due to Leonard Soicher, R.A. Bailey and me.
An (n×n)/k semi-Latin square is an arrangement of nk letters in an n×n square, with k letters per cell, such that each letter occurs once in each row and once in each column. It is a Trojan square if it can be obtained by superimposing k mutually orthogonal n×n Latin squares. It is a partial linear space if no two letters occur together in the same cell more than once. Trojan squares are partial linear spaces.
Bailey (Statistica Sinica 2 (1992), 413-437) showed that when k=n-1 then any semi-Latin square which is a partial linear space must be Trojan, and arises from an affine plane with two distinguished parallel classes of lines.
If k=n-2, must any semi-Latin square which is a partial linear space be Trojan?
Semi-Latin squares which are partial linear spaces are known as SOMAs.
Recent exhaustive checking by Soicher shows that the answer to the problem stated is affirmative when n=6 (there are no SLS-PLS or Trojan squares) and when n=7.
Let V and W be vector spaces over a field F. Suppose that v1,...,vn in V and w1,...,wn in W
Sum (vi tensor wi) = 0.Then the matroids M and M' on the ground set {1,...,n} represented by (v1,...,vn) and (w1,...,wn) are orthogonal, in the sense that any base of M is disjoint from some base of M' and vice versa.
Let M and M' be matroids on {1,...,n} which are both representable over a field F and are orthogonal in the above sense. Do there exist representations of M and M' (by v1,...,vn in V and w1,...,wn in W respectively) over F such that the displayed equation holds?
This problem is due to Gregory Gutin.
Given n, what is the smallest m such that there exist m subsets (called blocks) of the point set {1,...,n} such that
It is known that n<=m<=(2+o(1))n; the lower bound comes from a simple counting argument, and the upper bound is obtained by taking blocks to be the translates of D and -D, where D is a planar difference set in Cn, with n=q²+q+1. For more details, see Australasian J. Combinatorics 20 (1999), 97-100.
This problem is due to John Sheehan and me.
Marusic and Scapellato (Europ. J. Comb. 19 (1998), 707-712) proved that a vertex-transitive connected cubic simple graph has a non-trivial semiregular automorphism (one for which all cycles have the same length). Is it true that there exists such an automorphism having order at least f(n), where n is the number of vertices and f is a function going to infinity with n? Easy examples show that f(n) cannot exceed O(n1/3).
The proposers and Pablo Spiga have recently shown that there is a semiregular automorphism of order greater than 2 (Europ. J. Comb., to appear).
It is known (Europ. J. Comb. 1 (1980), 91-96) that, for any finite group G, there exists a rational number a(G) [0,1] such that, if Gamma denotes a random graph on the vertex set {1,...,n} (with all graphs equally likely), then
Prob(Aut(Gamma)=G | Aut(Gamma)>=G) tends to a(G) as n tends to infinity.Does a similar result hold for other random graph models, in particular for random regular graphs of degree d>2 (as described by Nick Wormald at the conference)?
This problem is due to Carrie Rutherford and Fuad Shareef.
Associated with any matrix A over a field F, there is a matroid representable over F (whose elements are the columns of A, and in which dependence is linear dependence) and a linear code (spanned by the rows of F). Greene (Studies in Applied Math. 55 (1976), 119-128) showed that the weight enumerator of the code is a specialisation of the Tutte polynomial of the matroid.
Do there exist two binary linear codes which have the same Tutte polynomials but different covering radii? (There are codes with the same weight enumerators but different covering radii.)
This problem has been answered in the negative by Thomas Britz and Carrie Rutherford, Discrete Math. 296 (2005), 117-120; doi: 10.1016/j.disc.2005.03.002
This problem is possibly due to Ph. Delsarte.
Does there exist a collection S of planes in the projective space PG(n,q), where n>2, such that any line lies in a unique member of S? (This would be the analogue for projective spaces of a Steiner triple system.) No examples are known.
One can easily define analogues of arbitrary t-designs in projective spaces (probably Delsarte was the first to do so), but very few examples are known. However, infinite examples exist in great profusion!
A slight modification of the method of Jacobson and Matthews (J. Combinatorial Design 4 (1996), 405-437) should work for Steiner triple systems. We simply replace "ordered triples" by "unordered triples of distinct elements" in the definition; then a STS is a function from unordered triples to {0,1} which satisfies
Sumz<>x,y f({x,y,z}) = 1for all distinct points x,y, and an improper STS is allowed to take the value -1 exactly once. Now the moves are defined as before. However, before we know that the limiting distribution is uniform, we have to solve the following
Problem: Is the chain connected? That is, is it possible to get from any STS to any other by a sequence of moves?
This problem is due to Harut Aydinian.
What is the size of the largest sum-free set (one not containing two points and their vector sum) in the square {1,...,n}×{1,...,n}? In particular, show that the number is $cn²+O(n), and find the constant c.
Upper and lower bounds for c are e-½=0.6065... and 3/5=0.6 respectively.
The group PGL(2,q) is the group of all linear fractional transformations x -> (ax+b)/(cx+d) of the projective line over GF(q), where ad-bc<>0.
The covering radius of a set S of permutations is the maximum, over all permutations g in Sn, of the minimum Hamming distance from g to S.
The covering radius of PGL(2,q) is known in all cases where q is not congruent to 1 mod 6. (It is q-2 if q is even, and q-3 if q is odd.) For the excluded case, it is only known that the covering radius is between q-5 and q-3 inclusive. See Discrete Math. 293 (2005), 91-109.
Find the exact value.
This problem has a geometric formulation, suggested by N. Knarr. What is the smallest s such that there is a set of q+1 points in the classical Minkowski plane (ruled quadric) of order q which meets every line in exactly one point and every conic in at most s points? The covering radius of PGL(2,q) is then q+1-s.
Let s and t be the numbers of positive and negative eigenvalues of the adjacency matrix of a graph. Torgasev (Publ. Inst. Math. (Beograd) 51(65) (1992), 25-28) proved that s is bounded by a function of t.
Find the best bound. In particular, there a polynomial (or even a quadratic) bound?
This problem is due to Robin Chapman.
Let p be a prime congruent to 3 mod 4, and let k=(p+1)/2. Let A be the k×k matrix with (i,j) entry (j-i/p), where (x/p) is the Legendre symbol (equal to +1 if x is a non-zero square mod p, to -1 if x is a non-square mod p, and to 0 if p divides x).
Prove that det(A)=1.
This conjecture is true for primes p<1000.
There is a well-known relation between the three polyhedral groups Alt(4), Sym(4) and Alt(5) (the groups of rotations of the tetrahedron, octahedron and dodecahedron), and the three exceptional root lattices E6, E7 and E8. (See the "McKay correspondence" (Kostant, Proc. Nat. Acad. Sci. U.S.A. 81 (1984), 5275-5277) and various results in singularity theory (Arnol'd, Funkcional. Anal. i Prilozen 6 (1972), 3-25).
For a finite group G, the Möbius number mu(G) is the value of mu(1,G), where mu is the Möbius function of the subgroup lattice of G (Shareshian, J. Combinatorial Theory (A) 78 (1997), 236-267). Let n(G)=|G|/mu(G).
The index of connection of a root lattice L is its index in the dual lattice, or the determinant of the Coxeter matrix, (Humphreys, Reflection Groups and Coxeter Groups, CUP 1990, p.40). The Coxeter matrix is 2I-A, where A is the adjacency matrix of the Coxeter-Dynkin diagram of the lattice.
Is it just coincidence that, ignoring signs, the values of n(G) for the three polyhedral groups are equal to the indices of connection of the corresponding root lattices? The numbers are 3, 2, 1 respectively.
This problem is due to S. Akbari, G. B. Khosrovshahi and me; it was communicated by S. Akbari.
Prove the following assertion:
Let G be a graph with at least one edge. If A is the adjacency matrix of G, then there exists a non-zero (0,1)-vector in the row space of A (over the real numbers) which does not occur as a row of A.The assertion is true for all graphs with at most 9 vertices and also for all line graphs.
This problem is due to Koko Kayibi and me.
Let Gamma be a graph and G a group of automorphisms of Gamma. The orbital chromatic polynomial of (Gamma,G) is the polynomial whose value at the positive integer k is the number of orbits of G on proper vertex colourings of Gamma with k colours. Note that if G=1, then the orbital chromatic polyomial is the chromatic polynomial of Gamma (where 1 denotes the trivial group). See Cameron, Jackson and Rudd, Discrete Math., to appear.
Roots of orbital chromatic polynomials are investigated by Cameron and Kayibi, Combin. Probab. Computing 16 (2007), 401-407. Here are two open problems.
This problem is due to Sam Tarzi and me. It arises in studying the automorphism group of the countable "n-coloured random graph". An involution in a group is an element of order 2.
Let n be a multiple of 8. Does there exist a finite group G, and a homomorphism from G onto the symmetric group of degree n, such that no involution of G maps to a fixed-point-free involution in the symmetric group? If so, what is the order of the smallest such group?
If n is odd, the symmetric group has no fixed-point-free involutions, and so the smallest group is the symmetric group itself. It is known that, if n is even and not a multiple of 8, then there is a group whose order is just twice that of the symmetric group.
Peter J. Cameron
p.j.cameron(AT)qmul.ac.uk
12 September 2007