Let *q,n,k* be positive integers with *q*>1, *n*>3.

- Show that
(

has no solutions.*k*choose 2)-1=(*q*-1)/(^{n}*q*-1) - Show that
(

has only the solution*k*choose 2)-1=*q*+1^{n}*q*=64,^{n}*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
*d _{n}* be the average density of edges in the list (that is,
the total number of edges divided by (

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**|=2^{n-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<=wherea_{1}<...<a<=_{t}n

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 *W _{n}* be the space of binary words of
length

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
*S _{n}* or the alternating group

(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*)/2^{n/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

- line graphs,
- line graphs of bipartite graphs,
- comparability graphs of 2-dimensional posets

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

3Describe the cycles of this permutation. In particular, does it have only finitely many finite cycles?n-> 2n, 3n±1 -> 4n±1

In fact, this problem is older: it is
the "original Collatz problem" from the 1930s (before the famous
"3*x*+1 problem"), though never published by Collatz.
A paper by
Jeff Lagarias gives details.

This problem is due to Donald Keedwell.

Suppose that *x*_{1},...,*x _{m}*,

- for any vertex, the sets of colours appearing on edges at that vertex are the same in both colourings;
- no edge receives the same colour in both colourings.

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
*v*_{1},...,*v _{n}* in

Sum (Then the matroidsvtensor_{i}w) = 0._{i}

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
*v*_{1},...,*v _{n}* in

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

- any two points lie in
*at least*two blocks, - any two blocks meet in
*at most*two points?

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 *C _{n}*, with

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(*n*^{1/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)=Does a similar result hold for other random graph models, in particular for random regular graphs of degreeG| Aut(Gamma)>=G) tends toa(G) asntends to infinity.

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

Sumfor all distinct points_{z<>x,y}f({x,y,z}) = 1

**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 *S _{n}*, of
the minimum Hamming distance from

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 *E*_{6}, *E*_{7}
and *E*_{8}.
(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 2*I*-*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:

LetThe assertion is true for all graphs with at most 9 vertices and also for all line graphs.Gbe a graph with at least one edge. IfAis the adjacency matrix ofG, then there exists a non-zero (0,1)-vector in the row space ofA(over the real numbers) which does not occur as a row ofA.

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.

- Is it true that the real roots of the orbital chromatic polynomial are bounded above by the largest real root of the chromatic polynomial?
- Is it true that real roots of the orbital chromatic polynomial, in
cases where
*G*consists of even permutations of the vertex set of*Gamma*, are dense in [1,*infinity*)? (There are no such roots less than 1 except 0; but a result of Thomassen,*Combin. Probab. Comput***6**(1997), 497-506, shows that such roots are dense in [32/27,*infinity*).)

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