## Problems   These are problems which have been on my homepage and are now put out to grass. See also permutation group problems.

Problem 1. In 1956, Rudin defined a permutation of the integers which maps 3x to 2x, 3x+1 to 4x+1, and 3x-1 to 4x-1 for all x. Problem: Determine the cycle structure of this permutation.

I have just learned (December 1998) that this problem is older: it is the "original Collatz problem" from the 1930s (before the famous 3x+1 problem). A paper by Jeff Lagarias gives details.

Problem 2. Let f(k,n) be the number of rooted trees with n leaves, all at level k (that is, distance k from the root), up to isomorphism of rooted trees. Prove that f(k+1,n)/f(k,n) tends to infinity with n, for fixed k. Is it even true that f(k+1,n)/f(k,n) is at least 1 + (n-1)/k?

Solution by Peter Johnson.

Let r be the maximum number of edges from a vertex on one level to the next level, in a tree with n vertices at level k. Then rk is at least n, so r is at least n1/k.

From any tree of height k+1, we obtain at most k different trees of height k by suppressing one level (replacing the paths of length 2 crossing this level by single edges).

But there is some tree of height k from which at least p(n1/k) trees of height k+1 can be recovered by introducing a new level. (Choose a level where some vertex has at least n1/k upward edges; if the number of such edges is r, then we can split the r edges in p(r) ways giving non-isomorphic trees. (Treat all the other vertices on this level alike.)

So f(k+1,n)/f(k,n) is at least p(n1/k)/k.

For motivation, see On the probability of connectedness in Discrete Mathematics 167/168 (1997), 173-185.

Problem 3. Let C be a class of graphs closed under forming disjoint unions and connected components. Let cn be the number of connected n-vertex graphs in C, and an the total number of n-vertex graphs in C (up to isomorphism). Suppose that c(x) is the generating function of the sequence (cn); assume that c(x) has non-zero radius of convergence r less than 1.

Is it true that, if the ratio cn/an tends to a positive limit as n tends to infinity, then c(r) converges?

For further information, see papers in Discrete Mathematics 167/168 (1997), 173-185; and Electronic J. Combinatorics 7(1) (2000), article #R33.

Problem 4. The number of strings of n red and blue beads is equal to the number of collections of necklaces of red and blue beads, where rotation of each necklace is permitted and only necklaces with no rotational symmetry are allowed. (The number is 2n in each case.)

For example, when n=2, the collections of necklaces are (R)(R), (R)(B), (B)(B), and (RB); (RR) and (BB) are not allowed. The strings are RR, RB, BR, BB.

Problem: find a bijective proof of this fact.

Solutions were given by Dima Fon-Der-Flass, Rosemary Bailey, and Robin Chapman. Then Roger Bryant drew my attention to C. Reutenauer, Free Lie Algebras, London Math. Soc. Monographs (New Series) 7, Oxford University Press, 1993, which contains this and more.

An account of my secret agenda in asking this question is in the paper The algebra of an age, in Model Theory of Groups and Automorphism Groups (ed. David M. Evans), London Math. Soc. Lecture Notes 244, Cambridge University Press, 1997, pp. 126-133.

Problem 5. Let G be a finite graph, and X(G) the class of graphs containing no induced subgraph isomorphic to G. For which G is it true that the probability that a (labelled or unlabelled) graph in X(G) with n vertices is connected tends to a limit strictly between zero and one as n tends to infinity?

For example, if G is the path of length 3, then the probability of connectedness in n-vertex graphs in X(G) is 1/2 for all n>1.

Problem 6. Let s(n) be the number of sequences of elements from the set {1,...,n} for which each term is at least twice the preceding one, and u(n) the number of such sequences in which each term is greater than the sum of its predecessors. It is known that u(n) - u(n-1) = s(n)/2. Problem: Find a bijective proof.

Solution by Jeannette Janssen:

Use the terms S-sequence and U-sequence for the sequences counted by s(n) and u(n). The left-hand side of the equality counts U-sequences ending in n; removing the last term gives a U-sequence with sum less than n.

Given an S-sequence, we can add or remove 1 without changing the S-sequence property. So the right-hand side counts S-sequences containing 1.

Now take one of these U-sequences, say u1, u2, ...; the corresponding S-sequence is 1, 1+u1, 1+u1+u2, ...

Note: this problem is from my combinatorics textbook, for which a Web page now exists.

Problem 7. A triangular prism made of uniform material has cross-section with sides a, b and c (not necessarily equal). It is rolled along a smooth plane so that it rotates about its axis. It gradually loses energy (because of air resistance). What are the probabilities that it lands on each of the three faces (in terms of a, b and c)?

There are obviously some points of detail in the physics to discuss. Dima Fon-Der-Flaass has an argument to show that, if the loss of energy is infinitesimally slow, and the triangle has unequal sides, then the probabilities are either 1/2, 1/4, 1/4 or 1/2, 1/2, 0.

This assumption is not physically realistic. Paul Glendinning found the even more surprising result that there is a collection of non-trivial intervals, arbitrarily close to 0, such that if the dissipation rate d lies in one of these intervals, then the probabilities are 1, 0, 0 for almost all initial conditions; that is, there is one face on which the prism is almost certain to land. See P. Glendinning, Inaccessible attractors of weakly dissipative systems, Nonlinearity 10 (1997), 507-522.

Franco Vivaldi pointed out that, if instead the prism is turned to a random orientation and dropped onto a plane covered with glue, then the probabilities are proportional to the angles subtended by the sides at the centroid of the triangle.

Problem 8. It can be shown that, if Fi is the number of orbits of a finite permutation group G on i-tuples of distinct elements, then the proportion of elements of G which are derangements (have no fixed points) is the alternating sum of the quantities Fi/i!. (See N. Boston, W. Dabrowski, T. Foguel, P. J. Gies, J. Leavitt, D. T. Ose and D. A. Jackson, The proportion of fixed-point-free elements of a transitive permutation group, Communications in Algebra 21 (1993), 3259-3275.)

For an infinite oligomorphic group (one with Fi finite for all i), the alternating sum may make sense (i.e. it may converge, or some other summation method may apply), even though the proportion of derangements does not. Problem: What does this mean?

For example, in the infinite symmetric group, Fi=1 for all i, and the sum is 1/e, which is just the limiting proportion of derangements in finite symmetric groups.

A more mysterious example is the group of order preserving permutations of the rational numbers. Here, fi=i! for all i, and the sum is 1-1+1-1...=1/2 (according to Euler). In what sense are half of the order-preserving permutations derangements?

For a closely related problem, see here.

Problem 9. (A. D. Keedwell). Suppose that x1, ..., xm, y1, ..., yn are positive integers such that there exists a bipartite graph with vertex degrees x1, ..., xm in one bipartite block and y1, ..., yn 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
• 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.
Note: it is not true that any graph with these vertex-degrees has such a pair of colourings. A counterexample is given by the two degree sequences (3,2,2,2) and (3,2,2,2), when the graph consisting of two 4-cycles joined by an edge does not have such a pair of colourings (though the graph consisting of two vertices joined by three disjoint paths of length 3 has such the same degree sequences and does have such colourings.

The conjecture is true if the degrees are all equal, or if every degree is either 2 or 3.

This problem is also Problem 16.15 in the list of BCC16 problems (PostScript file). See also Discrete Math. 197/198 (1999), 799-812.

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

Problem 10. Let S be the symmetric group on the infinite set X. Consider the product action of S2 on X2, and let an be the number of orbits on subsets of size n.

Problem: Find a formula for, or an efficient means of calculating, an.

The number an has other combinatorial interpretations:

• It is the number of zero-one matrices with n ones, with no zero rows or columns, up to row and column permutation.
• It is the number of bipartite graphs with n edges, no isolated vertices, and a distinguished bipartite block, up to isomorphism.
For more information see two papers with T. Prellberg and D. Stark: Electronic J. Combinatorics 13 (2006), #R85 (19pp.), and Journal of Physics: Conference Series 42 (2006), 59-70.
Problem 11. (a) Do there exist eight subsets of the set 1..10 with the properties
1. any two points lie in at most two sets,
2. any two sets meet in at least two points?

Solution: yes; I found one by hand:

• 1, 2, 5, 8, 9
• 1, 2, 6, 7, 9
• 3, 4, 5, 7, 9
• 3, 4, 6, 8, 9
• 1, 3, 5, 6, 10
• 2, 4, 5, 6, 10
• 1, 4, 7, 8, 10
• 2, 3, 7, 8, 10

(b) Do there exist twelve subsets of the set 1..15 with the above properties?

Solution: no (by a combination of case analysis and computer search).

Remark. The next interesting open case is eighteen subsets of 1..21. This has been settled in the negative by Pablo Spiga (personal communication).

Clearly this problem should be updated to ask for some analysis of configurations satisfying the two conditions 1 and 2 above!

Problem 12. Let An denote the nth element on the axis of symmetry of Pascal's triangle (the middle binomial coefficient 2n choose n).

A simple argument with generating functions shows that

A0An + A1An-1 + ... + AnA0 = 4n.

(The generating function ∑Antn is equal to (1-4t)-1/2, by the binomial theorem.)

Problem. Find a "counting proof" of this identity.

This problem is due to Alastair King and Andrew Swann. I heard it from Geoff Smith. A solution was found by Omer Egecioglu. Subsequently, Robin Chapman told me that the result is due to Daniel J. Kleitman, A note on some subset identites, Studies in Applied Mathematics LIV 289-293 (1975). Then an even earlier `proof' was unearthed in W. Feller's classic An Introduction to Probability Theory and its Applications, by Alastair King. Here are his comments (with an addition by Robin Chapman):

Solution: As observed by Kleitman, the "central binomial convolution identity" amounts to the fact that the number of balanced +1/-1 sequences (random walks) is equal to the number of never balanced ones of the same length.

A simple combinatorial proof of this fact can be extracted from the probability literature:

W. Feller, An Introduction to Probability Theory and its Applications, Wiley, New York, 1950.

The result plays a fundamental role in the analysis of random walks (Main Lemma III.3.1). The proof given in the text is not strictly combinatorial, but Problem III.10.7 asks for a purely combinatorial proof and sketches the construction of a bijection which is attributed to E. Nelson. Confusingly, the sketch appears to construct a bijection with another set of random walks of the same size, namely those which are non-negative. However, a small modification yields the following:

Identify the "initial" segment of a walk as being:

• for a balanced walk, up to the first time it reaches either
• its minimum value for walks that start -1 or
• its maximum value for walks that start +1,
• for a never balanced walk, up to the last time it reaches half its final value
The bijection reverses the signs and order of the initial segment.

Note: the first and last steps in an initial segment have the same sign. Thus balanced walks that start -1 correspond to never balanced ones that start +1 (and vice versa).

Problem 13. This problem is due to Sylvie Corteel, Carla D. Savage, Herbert S. Wilf and Doron Zeilberger, and appeared in the Journal of Combinatorial Theory, Series A, 82 (1998), 186-192.

Among the ordered pairs of monic polynomials of degree n over GF(2), exactly half consist of relatively prime polynomials. Find a nice bijection between the relatively prime pairs and the non-relatively-prime pairs.

Added 3/12/2007: This problem has been solved by

• A. Reifegerste, On an Involution Concerning Pairs of Polynomials in F2, Journal of Combinatorial Theory, Series A, 90 (2000) 216-220; and
• Arthur T. Benjamin and Curtis D. Bennett, The Probability of Relatively Prime Polynomials, Mathematics Magazine, 80, No. 3, (2007), 196-202.
Thanks to Carrie Rutherford for the information.
Problem 14. Two problems on designs and partitions.

1. Is it possible to partition the 4-subsets of a 16-set into 13 sets of 140 subsets, each set isomorphic to the set of planes in the affine space AG(4,2)?

Solution: Rudi Mathon informs me that Luc Teirlinck has shown the non-existence of such a partition. I will add the reference when I find it.

Of course, one can now ask for a partition of the 4-subsets of a 32-set into 29 copies of AG(5,2).

2. Is there a Steiner system S(3,5,26) (a set of 5-subsets of a 26-set with the property that any 3 points lie in just one of them) having the property that there are no three of the blocks which have pairwise intersections of size 2 but the intersection of all three is empty? Such a design would give rise to a strongly regular graph on 352 vertices and hence to a biplane with 352 points and the same number of blocks.

Problem 15. Two problems on random Latin squares

1. Call a row of a Latin square even or odd according as it is an even or an odd permutation of the set {1,2,...,n}. Prove that the number of even rows of a random Latin square of order n is approximately binomial B(n,1/2). (The best result in this direction is due to R. Häggkvist and J. Janssen, Discrete Mathematics 157 (1996), 199-206: the probability that all rows are even is exponentially small.)

2. Define a probability measure on permutations of {1,2,...,n} as follows: the probability of a permutation is the proportion of Latin squares with first row (1,2,...,n) in which it occurs as the second row. What can be said about this distribution? (For example, a permutation has non-zero probability if and only if it is a derangement.) In particular, prove that the probability that a permutation lies in no transitive proper subgroup of the symmetric group except possibly the alternating group tends to 1 as n approaches infinity.

(The analogous result for the uniform distribution was proved by T. Luczak and L. Pyber, Combinatorics, Probability and Computing 2 (1993), 505-512. Their result gives a simple deduction that the group generated by the rows of a random Latin square is almost surely the symmetric group. A solution to this problem would give the same conclusion for a random "normalised" Latin square.)

Note added 28 July 2005: I now believe that the distribution defined here "approaches" the uniform distribution on derangements as n grows. For example, when n=7, the numbers of ways of extending a two-rowed Latin rectangle corresponding to each type of derangement (with cycle lengths 7, 2+5, 2+2+3, and 3+4 respectively) are 6566400, 6604800, 6635520, and 6543360 respectively.

Problem 16. Find all positive integers greater than two which can be written as the sum of two powers of the same prime in three different ways. (I know of only six such integers, none of which has more than three different representations of this form.)
Problem 17. It is known that the average number of ways in which a positive integer in the range [1,...,n] can be written as a sum of consecutive primes tends to the limit loge2 as n tends to infinity. Is it true that the limiting distribution of the number of representations of this form is Poisson with parameter loge2?

This would imply that the density of the set of numbers with no such representation is 1/2. It would also imply that there exist integers with arbitrarily many such representations. Either of these assertions would be a nice result!

Problem 18. A problem on Fibonacci numbers. (I learned this problem from John Conway; see also C. Kimberling, Numeration systems and fractal sequences, Acta Arith. 73 (1995), 103-117.)

Any positive integer can be written uniquely as the sum of non-consecutive Fibonacci numbers. Hence we can define the Fibonacci successor function on the natural numbers by taking this expression and "moving each Fibonacci number along one". So, for example, 40 = 34 + 5 + 1; its Fibonacci successor is 55 + 8 + 2 = 65.

Now produce a table in which each row begins with the smallest number which doesn't occur in any earlier row, and all further entries are obtained by applying the Fibonacci successor function. (So the top row consists of the Fibonacci numbers 1, 2, 3, 5, 8, ...; the next begins 4, 7, 11, ...) It turns out that if we extrapolate each row back two steps using the recurrence relation for the Fibonacci numbers, we obtain the natural numbers 0, 1, 2, 3, ...; this gives a convenient numbering of the rows. Every positive integer occurs exactly once in this table, and every sequence of positive integers satisfying the Fibonacci recurrence relation agrees from some point on with a row of the table.

Now let xn denote the fractional part of n times the golden ratio. Let an and bn be the number of earlier terms of this sequence to the left and the right respectively of xn (including 0 and 1). The sequence of pairs (an, bn) begins (1,1), (1,2), (3,1), (2,3), (1,5), (5,2), ...

If we look at the pairs occurring in the Fibonacci-numbered positions, we see (1,1), (1,2), (3,1), (1,5), ... In other words, one number in the pair is 1, and it bounces from side to side as we progress along the sequence. This follows from well-known properties of the continued fraction expansion of the golden ratio.

Problems. If we consider the pairs in the positions numbered by any fixed row in the table, show that there is a "bouncing number" which alternates sides in the pairs. Which numbers occur as "bouncing numbers"?

For example: row number 1 of the table is 4, 7, 11, 18, 29, ...; the pairs in these positions are (2,3), (3,5), (9,3), (3,16), (27,3), ...; so the "bouncing number" is 3. The "bouncing numbers" for rows 0, 1, 2, 3, 4, ... appear to be 1, 3, 2, 5, 8, 5, 9, ...

Further information here, in DVI or PostScript.

Problem 19. Let p1 be a prime number. For every n, let pn+1 be the smallest prime divisor of p1...pn+1.
• Is it true that, for every n, there is a prime p1 for which none of the first n terms of the sequence is equal to 3?

• Is there a prime p1 for which no term of the sequence is equal to 3?
(This problem is due to Steve Donkin.)
Problem 20. Is the following true?
If P is a 2-group which is not elementary abelian, then some non-identity element of the centre of P is a square.
Solution: The answer to this question is negative. The smallest counterexamples have order 128, and there are two of them. This was found by Alexander Hulpke and Andreas Caranti. Alexander provided the following example in GAP:
```
gap> g:=SmallGroup(128,36);

gap> z:=Centre(g);
Group([ f6, f7 ])
gap> r:=List(ConjugacyClasses(g),Representative);;
gap> s:=Filtered(r,i->Order(i)>2);;
gap> List(s,Order);
[ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 ]
gap> Set(List(s,i->i^2));
[ f4, f5, f4*f7, f5*f6, f3*f4*f5, f3*f4*f5*f6, f3*f4*f5*f7, f3*f4*f5*f6*f7 ]
gap> List(last,i->i in z);
[ false, false, false, false, false, false, false, false ]

```
If not, is the following weaker statement true?
If P is a 2-group which is not elementary abelian, and Q is a core-free subgroup of P, then there is an element lying in no conjugate of Q which is a square.
Avinoam Mann also suggested the above group as a possible counterexample to the second question. However, Steve Linton and John Murray both checked that there is no core-free subgroup Q for which it is a counterexample. So the question is still open.

Solution (13 September 2004): The answer to the second question is also negative. Pablo Spiga found that the group of order 128 with generators (1,2,7,3)(4,8)(5,11)(6,9)(10,14)(12,16,13,15), (1,4,7,5)(2,8)(3,11)(6,13,14,12)(9,15)(10,16), and (1,6)(2,9,3,10)(4,12,5,13)(7,14)(8,15)(11,16) is a counterexample. Indeed, in this group the set of elements with fixed points coincides with the set of squares. This group is SmallGroup(128,836) in the GAP library.

This was motivated by the question of whether a vertex-transitive cubic graph necessarily has a semiregular group of automorphisms of order greater than 3 (see Problem 50), which is now solved in the affirmative.

Problem 21. A symmetric graph design, or SGD, with parameters (n, X, λ, F), (where n and λ are positive integers and X and F are graphs on n vertices), is a set {X1, ..., Xn} of subgraphs of the complete graph on {1, ..., n} having the following properties:
1. Xi is isomorphic to X for all i;
2. Xi intersection Xj is isomorphic to F for all distinct i,j;
3. any edge of the complete graph lies in exactly λ of the graphs X1, ..., Xn.
To avoid degenerate cases, we assume that X is neither the complete nor the null graph on n vertices. Symmetric graph designs generalise symmetric BIBDs (symmetric 2-designs, the case where X=Kk and F=Kλ). In this case, condition 2 follows from conditions 1 and 3.

Problem: Does condition 2 follow from 1 and 3 in general? Does 3 follow from 1 and 2? Does 1 follow from 2 and 3? (Assume that λ is greater than 1.)

Dima Fon-Der-Flaass has shown that condition 1 does not follow from 2 and 3. An example for λ=2: it is easy to find n subgraphs of Kn, each having n-1 edges, in such a way that every edge belongs to exactly two of them, and every two subgraphs have a single edge in common. The subgraphs can be arbitrary.

Santi Spadaro points out that 3 does not follow from 1 and 2, essentially because we can take a symmetric graph design and choose an arbitrary subset of the graphs Xi. Moreover, 2 does not follow from 1 and 3: take all graphs on n vertices isomorphic to a fixed graph X; then 1 and 3 hold but 2 usually fails. This problem is now completely settled in the negative. (11 June 2002)

Problem 22. It is known that, if G is a permutation group in which every non-identity element fixes exactly k points, then either G has a fixed set of size k, or G is one of a finite list of groups (for given k). The problem is to find a good upper bound (in terms of k) for the orders of the groups in this finite list.

For example, when k=2, the groups are the tetrahedral, octahedral and icosahedral groups, acting on the vertices, edges and faces of the corresponding polyhedra. (Every rotation has an axis, so has just two fixed points in this action.) So the correct bound is 60. (This is a theorem of Iwahori, J. Fac. Sci., Univ. Tokyo 11 (1964), 47-64.)

C. Franchi, in European J. Combinatorics 22 (2001), 821-837; doi: 10.1006/eujc.2001.0508, solved this by giving the bound max{60,a!a(a!a-1)}. I don't know whether this can be improved.

Problem 23. Let G be a finite group, a an automorphism of G, and X the semidirect product of G by the group generated by a. Suppose that every element of X not in G has prime order p.

It follows that the centraliser of a in G is a p-group. Let its order be pm.

A theorem of Kegel (Math. Z. 75 (1961), 373-376) shows that G is nilpotent. Then a theorem of Khukhro (Mat. Zametki 38 (1985), 652-657) shows that G has a normal subgroup whose nilpotency class and index are bounded by functions of p and m.

Is it true that the nilpotency class of G is bounded by a function of p and m?

Solution: This question has been settled in the affirmative by Andrei Jaikin, using a theorem of E. Khukhro, On locally nilpotent groups admitting a splitting automorphism of prime order, Mat. sb. 130 (1986), 120-127.

Problem 24. A separation relation on a set is the quaternary relation induced by a circular order on the set by the rule that S(a,b,c,d) holds if a and b separate c and d. (This holds for exactly one of the three partitions of the four points a,b,c,d into two pairs.)

It is known that a quaternary relation is a separation relation if and only if its restriction to every 5-element set is a separation relation.

Let P be an inversive plane, C a circle of P. Define a relation S on C by the rule that S(a,b,c,d) holds if every circle through a and b meets every circle through c and d.

Problem: What does it mean for P if, for every circle C of P, the above relation S is a separation relation?

Problem 25. Let Sn and Pn be the respectively the symmetric group (the set of all permutations) and the set of all partitions on the set [1..n]. There is a function F from Sn to Pn which replaces every permutation by the partition corresponding to its cycle decomposition.

(a) Is there an efficient method to decide whether a set of partitions is the image under F of a subgroup of Sn?

(b) If G and H are subgroups of Sn such that F(G)=F(H), then G and H have the same order. Are they necessarily isomorphic?

Note added 19 May 2000: The answer to (b) is negative. Eamonn O'Brien has shown that there are two pairs of groups of order 64 (numbers 19 and 111, and 94 and 249, in the lists in MAGMA and GAP), which act transivitely on 16 points, such that the two groups in each pair give rise to the same sets of cycle partitions. You can find a GAP program to verify this.

For further details see a paper in Discrete Math. 291 (2005), 45-54; doi: 10.1016/j.disc.2004.04.019

Problem 26. It is known that the only finite or countably infinite graphs G with the property that, for any partition of the vertex set into two parts, at least one of the parts induces a subgraph isomorphic to G, are a single vertex, the countable complete and null graphs, and the countable random graphs.

Which graphs have the property that, for any partition of the vertex set into three parts, the induced subgraph on the union of some two of the parts is isomorphic to the original graph?

Note 26/6/2000: This problem is solved: see the paper by Bonato, Cameron, Delic and Thomassé in European J. Combinatorics 23 (2002), 257-274; doi: 10.1006/eujc.2002.0574

Problem 27. Let G be a subgroup of the symmetric group Sn. For i = 0, ..., n, let pi be the probability that a random element of G has exactly i fixed points, and let Fi be the number of orbits of G on i-tuples of distinct points. These two sequences determine each other. In fact, N. Boston, W. Dabrowski, T. Foguel, P. J. Gies, J. Leavitt, D. T. Ose and D. A. Jackson, Communications in Algebra 21 (1993), 3259-3275, showed that, if
P(x) = ∑pi xi and F(x) = ∑Fi xi/i! , then
F(x) = P(x+1).

Now consider the linear analogue. Let G be a subgroup of the general linear group GL(n,q). For i = 0, ..., n, let pi be the probability that the fixed points of a random element form precisely an i-dimensional subspace, and let Fi be the number of orbits of G on linearly independent i-tuples. Again the two sequences determine each other.

Problem: Express the relation between these two sequences in terms of generating functions.

Note: This problem is now solved (2 August 2000). It is just a case of finding the right definitions of the q-analogues! See my paper with Shahn Majid in Communications in Algebra 31 (2003), 2003-2013.

Problem 28. (An old problem revisited)

Let G be a permutation group on the infinite set X. Assume that G is oligomorphic, that is, G has only finitely many (say fn) orbits on the set of n-element subsets of X. Dugald Macpherson, Proc. London Math. Soc. (3) 46 (1983), 471-486, showed that, if G is primitive on X (preserves no non-trivial equivalence relation) but not highly set-transitive ((that is, fn > 1 for some n), then the sequence (fn) grows exponentially, that is, limsup (fn)1/n > 1. These two assumptions apply throughout this problem, though analogous problems can be posed with primitivity relaxed.

1. Is it true that lim (fn)1/n exists for any group G?
2. What is the smallest possible value of the limsup? (Macpherson's lower bound of 21/5 has been improved by F. Merola to about 1.324. The smallest known value is 2.)
3. What is the smallest limit point of the set of values of the limsup?

Further information on such sequences is available in my survey article.

Problem 29. Let n be a positive integer and a a positive real number. It is easy to show that there is a positive real number b (depending on n and a) with the property that, for any positive integers x1, ..., xn,
if (1/x1) + ... + (1/xn) < a, then (1/x1) + ... + (1/xn) <= a-b.
Problem: If a is an integer, find an explicit lower bound for b in terms of n and a.
Problem 30. Let k be a positive integer.
1. Which finite groups G have the property that, given any k elements of G, there is an automorphism of G which simultaneously inverts them all?
2. Which finite groups G have the weaker property that, given any k elements of G, there is an automorphism of G and a permutation of the elements whose combination maps each element to its inverse?
All abelian groups have the first property. Perhaps, for moderately large k, there are not too many more.

Added 12 March 2001: The problem of bounding k has been solved by my colleague R. A. Bailey. For a non-abelian group G, the value of k is at most 2 for the first question, 5 for the second. These bounds are best possible. The problem of classifying all groups attaining the bounds (or, indeed, having one of these properties for a positive k) remains open.

Problem 31. (This is a variant of Problem 30.) Which finite groups have the property that the automorphism group acts transitively on the set of ordered pairs of non-commuting elements?

Added 22 March 2004: Pablo Spiga has pointed out that such a group must be a p-group of Frattini class 2.

Problem 32. A graph is N-free if it does not contain the path of length 3 as an induced subgraph. Let c(n) be the number of connected N-free graphs on n vertices. Then the following identity holds.
n>0(1-qn)-c(n)  = 1 - q + 2∑n>0c(n)qn.
This somewhat resembles in form the denominator identity of a Kac-Moody Lie algebra.

Problem: Is there a nice connection?

Problem 33. Let A0, ..., As be n×n matrices of zeros and ones. Consider the following conditions:
• (1) A0 + ... + As = J, the all-1 matrix.
• (2) A0 = I, the identity matrix.
• (3) For all i, there exists j such that AiT = Aj.
• (3+) For all i, AiT = Ai.
• (4) There are numbers pijk such that AiAj = ∑ pijkAk.
• (4-) There are numbers qijk such that AiAj + AjAi = ∑ qijkAk.

If (1), (2), (3+) and (4) hold, we have an association scheme. Conditions (1), (2), (3) and (4) define a homogeneous coherent configuration. Conditions (1), (2), (3+) and (4-) define a Jordan scheme (so-called because the span of the matrices is a Jordan algebra).

The operation of symmetrizing involves, for each non-symmetric matrix Ai, replacing it and its transpose by their sum (a symmetric zero-one matrix). It is easy to see that symmetrizing a homogeneous coherent configuration gives a Jordan scheme.

Problem: Is there a Jordan scheme which is not obtained by symmetrizing a homogeneous coherent configuration?

Problem 34. A base for a permutation group is a sequence of points whose stabiliser is the identity; it is irredundant if no point is fixed by the stabiliser of its predecessors. Cameron and Fon-Der-Flaass, Europ. J. Combinatorics 16 (1995), 537-544, called a permutation group an IBIS group if all irredundant bases have the same number of elements; they showed that the irredundant bases of an IBIS group are the bases of a matroid.

Problem: What is the relation between the Tutte polynomial of the matroid and the cycle index of the permutation group?

It is known that sometimes the first determines the second and sometimes vice versa. Perhaps there is a gadget which generalises both! See my paper in Electronic J. Combinatorics 9(1) (2002), #N2 (10pp).

Problem 35. R. D. Carmichael defined a primitive lambda-root or PLR of n to be an element of U(n) (the group of units modulo n) whose order is equal to the exponent of U(n). It is possible to count the number of PLRs of n, for any n. Donald Preece asked: is it possible to count the number of PLRs x having the property that x-1 is a unit? In particular, for which n do all (resp. some, none) of the PLRs have this property?

Combinatorics Study Group notes on primitive lambda-roots are available. For reasons explained therein, the number can be counted in principle by inclusion-exclusion, but there is unlikely to be a neat formula ...

Problem 36. How large is the largest antichain of subgroups of the symmetric group Sn? More precisely, estimate an/sn, where an is the size of the largest antichain and sn the total number of subgroups.
Problem 37. 37. Let L(G) be the subgroup lattice of the finite group G. Is the following true or false? Suppose that the Boolean lattice B(n) of subsets of an n-element set is embeddable as a meet-semilattice of L(G), and suppose that n is maximal with this property. Then there is an embedding of B(n) as meet-semilattice, such that the least element of B(n) is a normal subgroup of G.

Note: The quaternion group Q8 shows that we cannot make the least element of B(n) correspond to the identity in general.

Problem 38. This problem is due to R. A. Bailey.

Let A be an affine plane of order q. Is it possible to find, for each point x of A, a permutation px of the set of parallel classes of A with the properties

1. for all x, px is a derangement;
2. for all distinct x, y, if the line xy lies in parallel class C, then Cpx is different from Cpy?

There is no solution for q=2, since there are only two derangements and four points. For q=3, there is a solution. It is conjectured that a solution exists for all larger q.

Problem 39. This problem is due to Harut Aydinian, and was communicated to me by Oriol Serra.

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 cn2+O(n), and find the constant c.

Upper and lower bounds for c are e-1/2=0.6065... and 3/5=0.6 respectively. The lower bound for the number is the integer part of 3n(n+1)/5. Proofs can be found here.

Problem 40. Let Z(G) denote the cycle index of the permutation group G, and let F*n(G) be the number of orbits of G on the set of all n-tuples of its permutation domain.

Let G and H be permutation groups acting on sets X and Y respectively. We consider G×H as a permutation group on X×Y. We have

• Z(G×H) = Z(G)oZ(H), where siosj = (slcm(i,j))gcd(i,j), and the operation is extended multiplicatively and additively;
• F*n(G×H) = F*n(G)F*n(H).
The second assertion is trivially proved directly. The challenge is to deduce it from the first; this will probably require methods of dealing with these very strange operations on polynomials.

Solution: Solved by Daniele Gewurz. See a paper by Daniele Gewurz, Francesca Merola and me in Discrete Mathematics 308 (2008), 386-394; doi: 10.1016/j.disc.2006.11.054

Problem 41. Given n and k, what is the largest number m with the property that, if S is any set of m permutations on the set {1,...,n}, there exists a permutation which agrees with each element of S in at most k places?

For k=0, the value of m is the integer part of n/2. For k=1 and even n, it does not exceed n-1, but I do not know whether this is the exact value. (Note: Kézdy and Snevily conjectured that n-1 is the correct value in this case, and that the value is at least n for odd n. This conjecture implies two celebrated conjectures by Ryser and Brualdi on Latin squares: Ryser conjectured that any Latin square of odd order has a transversal, and Brualdi that any Latin square has a partial transversal of size n-1.)

A related question: Is it true that, if S is the set of rows of a Latin square of order n, there is a permutation agreeing with each element of S in at most two places? Note: The answer is "yes": see my paper with Ian Wanless in Discrete Math. 293 (2005), 91-109.

Problem 42. This problem was suggested by Donald Preece.

Following Carmichael, a primitive lambda-root of n is a unit in the integers modulo n which has the largest possible order. Let F(n) be the number of primitive lambda-roots of n. If primitive roots of n exist (that is, if n is an odd prime power, or twice an odd prime power, or 4), then F(n)=phi(phi(n)), where phi is Euler's totient function. However, this equation holds for other numbers too; indeed, it is true for more than half of the integers up to a million. In general, the left-hand side is at least as large as the right-hand side.

Problem: Is it true that the proportion of natural numbers for which the equation F(n)=phi(phi(n)) holds tends to a non-zero limit? If so, what is the limit?

See our notes on primitive lambda-roots for more details.

Solution: This problem has been solved by T. W. Müller and J.-C. Puchta: the limiting proportion is zero (though it tends to zero rather slowly). I will give the reference when the paper appears.

Problem 43. What is the cardinality of the largest subset of the group PSL(2,q) with the property that any two of its elements agree in at least two points? The two-point stabiliser, with size (q-1)/2 for odd q, has this property, but at least for small q there are larger sets.

Pablo Spiga points out that, if q is congruent to 1 mod 4, then the stabiliser of an unordered pair of points has the above property, and has size q-1.

Problem 44. Consider the following decision problem.
Let p1, ..., pm be partial permutations of a finite set A (that is, bijections between subsets). Suppose that
• p1 is the identity map on A, and
• for any i,j, there is at most one k such that pk extends pi o pj.
Does there exist a finite set B containing A, and permutations fi of B extending pi for i=1,...,m, such that, if pk extends pi o pj, then fi o fj = fk?
What is the computational complexity of this problem? How is this affected if we insist that B=A?

Problem 45. This problem is due to Patrick Moss, in his Ph.D. thesis (University of East Anglia 2003). A sequence (u(n)) of non-negative integers is said to be realizable if there is a set X and a permutation T of X such that u(n) is the number of fixed points of Tn in X. Moss shows indirectly that, if (u(n)) is realizable, then so are the sequences (u(n)n) and (u(nk)), where k is a fixed positive integer.

Problem: Find a pair (X',T') realizing each of these sequences, in terms of the pair (X,T) realizing the original sequence.

The first sequence is not likely to be easy. For example, let p be a prime. The constant sequence with value p is realized by the identity permutation of a set of size p. An obvious realization of the sequence (pn) is (X,T), where X is the algebraic closure of the field with p elements and T is the Frobenius map T(x)=xp.

The second, however, is reasonably straightforward. Indeed, let f be a function on the natural numbers such that n divides f(n), and suppose that there is a function g such that g(m) divides n if and only if m divides f(n). Then a realization of (u(f(n))) can be constructed directly from a realization of (u(n)). The function f(n)=nk has these properties. The proof is here.

Problem 46. This problem is based on joint work with Jarik Nešetřil.

A graph G is said to be homomorphism-homogeneous, or HH, if any homomorphism from a finite subgraph of G into G can be extended to an endomorphism of G.

All finite HH graphs are known. The countable examples we know are disjoint unions of complete graphs of the same size, and graphs which contain the random graph R as an induced subgraph.

Problem: Are there any others?

Note: The analogous problem for posets has been solved by D. Lockett.

Problem 47. The Stirling transform of a sequence a is the sequence b given by b(n) = ∑ S(n,k)a(k), where S(n,k) are the Stirling numbers of the second kind.

What can be said about the asymptotics of a sequence a for which b(n) ~ c·a(n) for some constant c > 1?

Many interesting sequences (e.g. chains in the partition lattice, zero-one matrices with n ones and no non-zero rows or columns) have this property.

Problem 48. Let G be a Frobenius group with Frobenius kernel N and Frobenius complement H having orders n and h respectively. Number the elements of N as x1,...,xn. Now let Xij be the n × n matrix with (k,l) entry equal to the cardinality of the intersection of xi-1Hxk and xj-1Hxl. Note that Xii = hI while, for i and j distinct, Xij is a zero-one matrix.

Is it true that

k XikXkj = nXij+h(h-1)J,
where J is the all-one matrix?

Solution: This problem is now solved in the affirmative (but I have lost the solution . . .)

Problem 49. Let s and t be the numbers of positive and negative eigenvalues of the adjacency matrix of a graph. A. Torgasev proved that s is bounded by a function of t.

Problem: Find the best bound. In particular, there a polynomial (or even a quadratic) bound?

Problem 50. Since Problem 20 above has a negative solution, the following problem (due to John Sheehan and me, BCC problem 17.12) is open again.

Is it true that a vertex-transitive trivalent graph has a semiregular automorphism (one with all cycles of the same size) of order greater than 2?

Note: This has now been settled affirmatively: see P. J. Cameron, J. Sheehan and P. Spiga, Europ. J. Combinatorics 27 (2006), 924-930; doi: 10.1080/00927870701404812, and a stronger result has been given by Cai Heng Li, Proc. Amer. Math. Soc. 136 (2008), 1905-1910.

Problem 51. There is a well-known connection between the three polyhedral groups Alt(4), Sym(4) and Alt(5), on the one hand, and the exceptional root lattices E6, E7 and E8 on the other. (See the McKay correspondence and various results in singularity theory).

For a finite group G, let n(G) denote |G|/mu(1,G), where mu is the Möbius function of the subgroup lattice of G.

Is it just coincidence that, ignoring signs, the values of n(G) for the three polyhedral groups are equal to the connection numbers of the corresponding root lattices (the index in the dual lattice)? The numbers are 3, 2, 1 respectively.

The coincidence becomes sharper if we include the correspondence between cyclic and dihedral groups and the root lattices An and Dn, for which the numbers also agree up to sign if n+1 is squarefree. (This requires some charity about the interpretation of the McKay correspondence.)

A subsidiary question: If there is a natural explanation, what is the interpretation for root lattices of the sign of the Möbius function?

Problem 52. Let G be a permutation group of degree n. The base size of G is the smallest number b(G) of points whose stabiliser is the identity; the separation number of G is the smallest size of a set S of points such that, for any two distinct points x,y, there exists s in S such that x and y lie in distinct orbits of the stabiliser of s.

Clearly b(G) <= s(G). Is it true that, if G is primitive but not 2-transitive, then s(G) <= b(G) log n?

See Combinatorics Study Group notes on this problem (PDF file).

Problem 53. This problem is due to Robin Chapman.

Let p be a prime congruent to 3 mod 4, and let r=(p+1)/2. Let (x/p) denote the Legendre symbol (taking the values +1, -1, or 0 according as x is congruent to a nonzero square, a non-square, or zero mod p. Show that the r×r matrix with (i,j) entry ((j-i)/p) has determinant 1.

This is true for primes less than 1000.

Problem 54. John Dixon has shown that the number of pairs of permutations on {1,...,n} which generate a transitive subgroup of Sn is equal to (n-1)! times the number of indecomposable permutations of {1,...,n+1}. (Here a permutation is indecomposable if there is no positive k less than n+1 such that it maps the set {1,...,k} to itself.)

Problem: Find a bijective proof!

Problem 55. A tournament is a directed graph in which every pair of vertices is joined by an arc in one direction. Its score sequence is the list of the out-degrees of the vertices in decreasing order.

A permutation (represented by a n × n permutation matrix P) is said to be binary if no two 1s in P are on the same northeast-southwest diagonal. The shadow of a binary permutation is the (2n-1)-tuple (indexed from 2 to 2n) with 1 in position i+j if Pij=1, and other entries 0.

C. Bebeacua, T. Mansour, A. Postnikov, and S. Severini conjecture that the number of score sequences of n-vertex tournaments is equal to the number of shadows of binary permutations on n elements.

Problems: Prove (or refute) this conjecture! If it is true, find a bijective proof.

Problem 56. Consider the following operation of "critical set reduction" of a family of sets: Find a minimal proper subfamily which is critical (that is, equality holds in Hall's condition), if one exists; remove elements of its union from all the other sets in the family; now apply this method recursively to the sets not in the critical subfamily. Clearly the new family has the same systems of distinct representatives as the old one.

Now suppose that a Su Doku puzzle is given. (By definition, a Su Doku must have a unique solution.) Consider the following algorithm:

First, for each blank cell, calculate the "free set" consisting of numbers not appearing in the row, column, or subsquare containing that cell. Now repeat the following until no further progress occurs:

• if one of the free sets has cardinality 1, write its entry in the puzzle and blank it out;
• for each row, column, and subsquare, apply critical set reduction to its free sets.
Problem: Find a Su Doku puzzle which is not solved by this algorithm.

Remark: Daniele Gewurz and Francesca Merola have pointed out that solutions to this problem can be found on Gordon Royle's Sudoku page.

Problem 57. This problem is due to R. A. Bailey.

Given a completed Su Doku design (a 9×9 Latin square divided into nine 3×3 subsquares each of which contains the numbers 1,...,9 once), consider the following block design:

• the point set is {1,...,9};
• the blocks are the "short rows" and "short columns", i.e. the 54 sets formed by the triples of points forming a row or column of one of the subsquares.
The problem is to find an example where, in this design, any two points lie in either 4 or 5 blocks, or to show that no such example exists. (The average concurrence is 9/2.)

Added 26/11/2005: A solution has been found by Emil Vaughan:
 1 2 3 9 7 4 5 6 8
 4 5 6 8 2 1 3 7 9
 7 8 9 3 5 6 4 1 2
 2 4 1 3 5 6 8 9 7
 9 6 3 1 8 7 5 4 2
 5 7 8 2 9 4 1 6 3
 6 8 2 4 1 9 7 3 5
 7 1 4 6 3 5 2 9 8
 9 3 5 8 2 7 6 4 1

So let me pose a further question. Is there such a square in which the graph with vertex set {1,...,9}, two vertices joined if they lie in five blocks, is the "window graph" (the line graph of K3,3, or the Paley graph of order 9)?

Added 05/12/2005: This too can be done. So one more test: is there a square in which the short rows and short columns are separately nearly balanced? Perhaps one could ask whether each pair of numbers lies in 2 or 3 short rows and 2 or 3 short columns, total 4 or 5? But a computation shows that this is not possible! In fact we cannot place more than five numbers subject to these constraints without getting stuck.

Also, one can find such a square where the block concurrences are 3 and 6, or 2 and 7, or 0 and 9, but not 1 or 8.

For more on this and related constructions see the preprint.

Problem 58. Let F be the set of sequences F of positive integers whose nth term is the number of orbits on n-tuples of distinct elements of an infinite permutation group.

Is F closed under pointwise multiplication?

I conjecture that the answer is "no". Specifically, let F be the sequence (1,2,4,10,26,...) whose nth term is the number of solutions of g2=1 in the symmetric group of degree n. This sequence belongs to F, but I conjecture that the sequence (1,4,16,100,676...) whose terms are the squares of the terms in this sequence is not in F.

Remark: The set of sequences counting orbits of permutation groups on all n-tuples is closed under pointwise multiplication. Moreover, the set of sequences counting orbits on n-tuples of distinct elements for groups with the property that the stabiliser of a finite set fixes no additional points is closed under pointwise multiplication.

Further remark: The answer in general is "no": if G is the stabiliser of a point in the symmetric group, the sequence begins 2, 3, 4, ..., but a group with 4 orbits on points must have at least 12 orbits on ordered pairs of distinct points. It is harder for transitive groups (where a possible counterexample is given in the question), and still more so for primitive groups.

Problem 59. Let Gamma be a (finite) graph, and G a group of automorphisms of Gamma. There is a polynomial P whose value at a positive integer k is the number of G-orbits on proper k-colourings of Gamma. (This is the orbital chromatic polynomial of Gamma and G.) For more information see
• P. J. Cameron, B. Jackson and J. Rudd, Orbit-counting polynomials for graphs and codes, Discrete Math. 308 (2008), 920-930; doi: 10.1016/j.disc.2007.07.108
• P. J. Cameron and K. K. Kayibi, Orbital chromatic and flow roots, Combinatorics, Probability and Computing 16 (2007), 401-407; doi: 10.1017/S0963548306008200
1. Is it true that the real roots of P(x)=0 are bounded above by the largest real root of the chromatic polynomial of Gamma?
2. Is it true that the roots of P, for Gamma 2-connected and G contained in the alternating group on the vertices, are dense in [1,infty)? (A result of Thomassen shows that they are dense in [32/27,infty).)

Problem 60. Henson's graph Hn, for n>2, is the unique countable homogeneous graph whose finite subgraphs are the finite graphs containing no complete graph of size n.
• Is Aut(Hn) simple? [Note added 13 August 2007: these groups have been shown to be simple by Macpherson and Tent.]
• Does Aut(Hn) have the small index property? (That is, is it the case that a subgroup of countable index contains the pointwise stabiliser of a finite set)?
• Are the groups Aut(Hn) and Aut(Hm) non-isomorphic for distinct n and m?
• Is Aut(Hn) a Cayley graph for n>3?

Problem 61. Consider the set of Lebesgue measurable subsets of [0,1] modulo null sets. This carries a natural metric, where the distance between two sets is the Lebesgue measure of their symmetric difference.

Prove that any isometry of this metric space is the product of the operation of symmetric difference with a fixed measurable set, and a measure-preserving transformation of [0,1].

Remark: This problem is now solved, using a theorem of Lamperti from 1958. (Thanks to Cho-Ho Chu for directing me to this!) See Cameron and Tarzi, Topology and its Applications 155 (2008), 1454-1461; doi: 10.1016/j.topol.2008.03.022

Problem 62. What is the computational complexity of the following "generalised Sudoku" problem?
• Instance: An n×n grid whose cells are partitioned into n "regions" S1,...,Sn with n cells in each.
• Problem: Is it possible to place the symbols 1,...,n into the cells in such a way that each symbol occurs just once in each row, column, and region?
This problem includes the problem of deciding whether a Latin square has an orthogonal mate. If we allow some cells to be pre-filled (consistently), then it includes the "ordinary" Sudoku puzzle of arbitrary size.

Added 6 September 2007: This problem has been shown to be NP-complete by Emil Vaughan. The complexity status in the case where the regions are polyominoes (or even rectangles) is unknown.

Problem 63. Fix a positive integer n. Let A(n) be the commutative algebra generated by indeterminates xi, for i running over the divisors of n, subject to the relations
xixj = xgcd(i,j)xlcm(i,j)
for all i,j.

Problem: What is the Hilbert series for A(n), the generating function for the sequence whose kth term is the dimension of the space of elements of degree k in the algebra?

Note: This problem has been solved by Daniele Gewurz and Francesca Merola, and by Pablo Spiga. Natalia Iyudu has also found results on it. I hope that a reference will be added soon.

Problem 64. Let n be a multiple of 8. Is there a finite group G with a homomorphism onto the symmetric group Sn such that no involution in G maps onto a fixed-point-free involution of Sn? If so, what is the smallest such group? (For n even but not divisible by 8, one or other of the double covers of Sn has this property.)
Problem 65. This problem is due to John McKay.

The first of the following sequences is the number of commuting triples of elements in the symmetric group Sn, divided by n! . The second is the number of non-zero elements in the character table of Sn.

 n 1 2 3 4 5 6 7 8 9 1st 1 4 8 21 39 92 170 360 667 2nd 1 4 8 21 39 92 170 331 593

Problem: What is going on here?

Problem 66. Let n be a positive integer. A linear car park has n spaces numbered 1,2,...,n. Each of n drivers independently chooses a favourite parking space. In turn, each driver enters the car park, goes to his chosen space, and parks there if it is free; if not, he takes the first available space. If he reaches the end of the car park without finding a space, he leaves in disgust. It is known that, of the nn possible choices by the drivers, exactly (n+1)n-1 result in all drivers parking successfully.

Problem: Given kn, what is the number of choices which result in exactly k drivers parking?

Added 19 November 2007: Pascal Schweitzer and Daniel Johannsen have found a formula (involving a single summation) for these numbers. Thomas Prellberg has shown that, after re-scaling by the square root of n, the probability density function for the number of drivers who fail to park successfully is 4x exp(-2x2). The paper is here.

Problem 67. For a graph G, let a°(G) be the greatest integer k such that, for any circular ordering of the vertices of G, there is a monotonic cycle with k vertices. (An edge counts as a cycle of length 2 here.) This parameter is related to the altitude of G investigated by Mynhardt et al. It is easy to see that a°(G) is bounded below by the clique number and above by the chromatic number of G. Moreover, either a°(G)=2, or a°(G) is bounded below by the girth of G.
Problem: Investigate this parameter. In particular, for which graphs does equality hold in any of the above bounds?
Remark: If we replace "circular order" by "linear order" and "cycle" by "path", the corresponding parameter is equal to the chromatic number. See notes here.
Problem 68. I conjectured in 1972 that there is a function f with the following property: Let G be a finite primitive permutation group, with rank r; let s be the subrank of G, the maximum rank of a point stabiliser on any of its orbits. Then either
• G has a base of size 2; or
• r <= f(s).
Perhaps the time has come to revisit this conjecture.

The most extreme example I know is an extension of a 2n-dimensional vector space over GF(2) by a dihedral group of order 2(2n+1); this has rank 2n and subrank 2n-1+1. So perhaps the conjecture holds with a linear function f.

Problem 69. A homomorphism of graphs is a mapping of vertices which carries edges to edges. Two graphs are homomorphism-equivalent if there are homomorphisms in both directions. Any homomorphism-equivalence class contains a unique (up to isomorphism) smallest graph called a core; a graph is a core if all its self-homomorphisms are automorphisms. For any graph G, the core of the equivalence class [G] is embeddable as an induced subgraph of G; any such subgraph is called a core of G.

A graph G is called core-transitive if any isomorphism between cores of G can be extended to an automorphism of G.

Problem: What can be said about core-transitive graphs?

Problem 70. Does there exist a countable group G with the following property:
• G has just two non-identity conjugacy classes, each inverse-closed;
• if C is one of these classes, then the Cayley graph Cay(G,C) is isomorphic to the countable random graph?

Problem 71. Do there exist infinitely many non-abelian finite simple groups whose order is a prime plus one?

The context is a theorem of Cauchy which states that a primitive permutation group of degree prime plus one is doubly transitive. Neumann, Sims and Wiegold pointed out in 1968 that this is false: if S is a non-abelian finite simple group, then S × S, acting on S by left and right multiplication, is primitive but not doubly transitive. The first few finite simple groups have order a prime plus one. So the question asks whether this construction gives infinitely many counterexamples to Cauchy's "theorem".

Problem 72 Let Gamma be a (finite) graph, and G a group of automorphisms of Gamma. There is a polynomial F whose value at a positive integer k coprime to the order of G is the number of G-orbits on nowhere-zero A-flows of Gamma, for any abelian group A of order k. (This is the univariate orbital flow polynomial of Gamma and G. To handle arbitrary A, we need a multivariate polynomial, since the answer depends on the structure of A.) The roots of these polynomials are called orbital flow roots. For more information see
• P. J. Cameron, B. Jackson and J. Rudd, Orbit-counting polynomials for graphs and codes, Discrete Math. 308 (2008), 920-930; doi: 10.1016/j.disc.2007.07.108
• P. J. Cameron and K. K. Kayibi, Orbital chromatic and flow roots, Combinatorics, Probability and Computing 16 (2007), 401-407; doi: 10.1017/S0963548306008200
1. Is there a universal upper bound for real orbital flow roots, as is conjectured to be the case for flow roots?
2. Are real orbital flow roots dense in [0,1]? (They are dense in the negative real line but the only limit points known between zero and one are reciprocals of positive integers.)

Problem 73

Conjecture: Let a be an algebraic integer. Then there exists a natural number n such that a + n is a root of the chromatic polynomial of a graph.

Remarks:

1. The conjecture is true in many cases, e.g. for all integers in quadratic number fields.
2. Conversely, if a is a chromatic root, then so is a + n for every natural number n.

Problem 74

This is perhaps a model for a network where channels silt up if not used. It is rather open-ended, so feel free to interpret or change the hypotheses.

Consider a network in which all edges have capacity 1. At unit time steps, perform the following operation:

• Choose a random maximal flow f in the network. (The maximal flows form a compact subset of a finite-dimensional Euclidean space; use the measure induced from the uniform measure on a suitable box.)
• Choose a random edge e.
• Delete e with probability 1-f(e).

Eventually the network will be reduced to c edge-disjoint paths from source to target, where c is the capacity. What can be said about the time required for this to happen?

For example, if the network is a cube and the source and target are antipodal vertices, the expected time required is 19.5.

Problem 75

This problem is due to Tatiana Gateva-Ivanova. The topic is set-theoretic solutions of the Yang-Baxter equation, but no background knowledge is needed to understand the problem.

Let X be a finite set. A solution is a pair of maps L and R from X to the symmetric group on X satisfying the three conditions (for all x, y in X), where the image of x under L is denoted by Lx:

1. Lx(x) = x;
2. LLx(y)Ry(x) = x;
3. LLx(y)LRy(x) = LxLy. (Unlike my usual convention, maps act on the left and compose right-to-left.)

Problem: Given any solution in which X has more than one element, show that there exist distinct points x, y in X such that Lx=Ly.

Problem 76

This problem is due to Josephine Kusuma. Let C be a set of binary n-tuples. The (Vapnik-Chervonenkis) dimension of C is the largest t such that, in every projection of C onto t coordinates, each binary t-tuple occurs; and the strength of C (as orthogonal array) is the largest t such that, in every projection of C onto t coordinates, each binary t-tuple occurs equally often. Clearly strength is not greater than dimension, and the two parameters are equal if C is a binary linear code.

Now suppose that C is a Gray map image of a linear code over Z4, and C has dimension t. What can be said about the strength of C?

Solution: It is at least 1+t/2 (rounded down), and this is the best possible lower bound.

Problem 77

Let S be a set of elements of the symmetric group Sn. It is not always true that every element in the group generated by S can be written as a word in S of length bounded by a polynomial in n. (Take S to be a singleton whose element has maximum possible order in Sn.)
Problem: If the group generated by S contains a fixed-point-free element, can we always find one which is a word of polynomially bounded length?

Problem 78

In connection with optimality of block designs, statisticians are interested in various functions of the Laplacian eigenvalues of a graph. If the graph is connected, then 0 is an eigenvalue with multiplicity 1; the other eigenvalues are called non-trivial, and are strictly positive. The most interesting are:

• the harmonic mean of the non-trivial eigenvalues (for A-optimality);
• the geometric mean of the non-trivial eigenvalues (for D-optimality);
• the smallest non-trivial eigenvalue (for E-optimality).
See my forthcoming paper with R. A. Bailey on "Combinatorics of optimal designs".

The geometric mean is determined by the Tutte polynomial of the graph -- it is essentially the number of spanning trees. Problem: Is it true that the other two are not determined by the Tutte polynomial, i.e. they may take different values for graphs with the same Tutte polynomial?

Solution: This is indeed true. Emil Vaughan pointed out to me that any tree on n vertices has Tutte polynomial xn, whereas trees certainly differ on the other criteria (the star being optimal).

In the reverse direction, the two strongly regular graphs on 16 points (the line graph of K4,4 and the Shrikhande graph) have the same Laplace eigenvalues (and so agree on all eigenvalue-based optimality criteria) but different Tutte polynomials (the first has 576 proper 4-colourings, the second 240).

Problem 79

The following problem in design theory comes (indirectly) from automata theory.

Let m be an integer greater than 3. Does there exist a t-(2m,m,λ) design, for some t>1 and some λ>0, with the properties

• the complement of a block is a block,
• the number of blocks properly divides the total number of m-subsets of the point set?

The Hadamard conjecture would imply that the answer is "yes" for all m>3; but perhaps there is an easier construction, since t and λ are not specified.

Problem 80

This elegant idea, and the first question, are due to Bill Kantor, in J. Algebraic Combinatorics 28 (2008), 351-363.

A family Gn of finite permutation groups is universal if every finite group is isomorphic to some two-point stabiliser of a group in the family. The motivating example: the fact that

every finite group is the automorphism group of a finite graph
(Frucht's Theorem) can be expressed as saying that the family of semidirect products Xn:Sn is universal, where Sn is the symmetric group of degree n and Xn the exterior square of its permutation module over the field of two elements.

• Find necessary and sufficient conditions for a "natural" family of permutation groups to be universal.
• In particular, which families Vn:Sn are universal, where Vn is a module for Sn defined in some "natural" way as above?

Problem 81

A permutation group is QI if the augmentation submodule of its permutation module over the rationals (the set of vectors with coordinate sum zero) is irreducible.

If G is not QI, then there exist vectors v and w in the permutation module such that

• the coordinates of v and w are non-negative integers, with at least one and at most n-2 coordinates zero, where n is the degree;
• the inner product of v and wg is constant for g in G.

Find an example of a permuation group for which this is the case but there is no pair of vectors satisfying these conditions and also

• the coordinate sum of v divides n;
• all coordinates of w are zero or one.

Remarkably, no such group is currently known.

Problem 82

This is Bulgarian solitaire; it is well-known, though I have only just learned about it. You may want to have fun playing with it before looking up references.

A library has n books, stacked up in piles, so there are p(n) possibilities for the sizes of the piles (the integer partition function). Every day, the librarian comes in and picks up the top book from each pile, making a new pile from these books. This defines a map on the set of integer partitions. Now many questions can be asked, such as

• How many connected components are there?
• What are the cycle lengths?
• What is the maximum number of days before a partition is repeated?
• How many periodic points are there?

Problem 83

Donald Preece and I have failed to solve the following problem.

Let p be an odd prime, and k an integer at least 3. A k-AP decomposition mod p is an arithmetic progression a1, . . . ak consisting of integers not congruent to 0 or 1 mod p such that the group of units of Zp is the direct product by the cyclic groups generated by the terms of the progression.

There are many examples of 3-AP decompositions, but we found no 4-AP decompositions; none exist for primes less than 20000.

Problem: Do k-AP decompositions exist for k>3?

(Note: we assume that each cyclic factor has order greater than 1. Without this assumption, the AP [3528,1148,2381,1] mod 3613 is an example.)

Problem 84

A group G is a B-group if every primitive permutation group containing the regular representation of G is doubly transitive. There are many finite B-groups (including cyclic groups of composite order), but no countably infinite B-groups are known.

• Does there exist a countably infinite B-group?
• Let G be the infinite dicyclic group, generated by two elements a and b, where b has order 4 and inverts a. Is G a B-group? (Note that the countable random graph is not a Cayley graph for G; so the standard method for showing a group is not a B-group fails!)

Problem 85

The power graph of a group is the undirected graph whose vertex set is the group, two elements being adjacent if one is a power of the other.

Two finite abelian groups with isomorphic power graphs must be isomorphic, but this is not true for arbitrary finite groups.

Conjecture: Two finite groups with isomorphic power graphs have the same number of elements of each order.

This problem has been solved in the affirmative. A stronger statement holds. If the power graphs are isomorphic, then the directed power graphs (with a directed edge from x to y if y is a power of x) are also isomorphic. The proof will appear in J. Group Theory, doi: 10.1515/JGT.2010.023

Problem 86

This problem is due to Josephine Kusuma.

It is well known that the strength (as an orthogonal array) of a linear code over a field is one less than the minimum Hamming weight of the dual code. Josephine showed that this is true over arbitrary commutative rings with identity.

Problem: Let C be a linear code over Z4, and let C' be its Gray map image. Is it true that the strength of C' is one less than the minimum Lee weight of the dual of C? (Josephine also showed that this holds with "is at most" replacing "is".)

(The Gray map from Z4 to Z22 is defined coordinatewise, and maps 0 to 00, 1 to 01, 2 to 11, and 3 to 10. The Lee distance on Z4 is given by dL(x,y)=min(x-y,y-x). The Gray map is an isometry from the Lee metric on Z4n to the Hamming metric on Z22n.)

Problem 87

Given n, what is the smallest number k such that any partial Latin square of order n can be broken into k pieces, each of which can be completed to a Latin square?

It is known that, for any n>1, we have k=2, 3 or 4; which value is correct?

See W. E. Opencomb, Discrete Math. 50 (1984), 71-97.

Problem 88

Which total orderings of a finite vector space have the property that the unique order-preserving bijection between two subspaces of the same dimension is linear?

The lexicographic ordering of GF(q)n has this property (if the field is ordered arbitrarily). There are other examples: how many?

Problem 89

Which finite groups G have the property that the number of isomorphisms between pairs of subgroups of G is equal to the number of endomorphisms of G?

Every abelian group has this property; no non-abelian group is known to do so.

Problem 90

Suppose that k is a proper divisor of n. Let S consist of all those integers between 2 and n–1 inclusive which are either a multiple of k, or at least n/k (or both). Let q(n) denote the minimum of |S|/n, over all divisors of n. If n is prime we set q(n)=n by default.)

Problem: Is it true that the lim inf of q(n), as n→∞, is 3/4?

Solution: This is an easy problem; the answer is "yes". For, if k≥4, then there are at least about (3/4)n numbers greater than n/k; for k=3, there are about (2/3)n numbers greater than n/3, and another about n/9 multiples of 3 smaller than n/3; and for k=2, there are about (1/2)n numbers greater than n/2, and another about n/4 multiples of 2 smaller than n/2.

Problem 91

A graph X is a hull if, for any two non-adjacent vertices v and w, there is an endomorphism of X (a homomorphism from X to itself) which maps v and w to the same place.

It is known that any countably infinite graph with infinite clique size is a hull.

Problem: Let X be a countably infinite hull with finite clique size ω(X). Is it true that χ(X)=ω(X) (where χ(X) is the chromatic number of X)?

Solution by Nick Gravin: Take any finite subgraph Y. If it is not a complete graph, we can collapse two of its vertices by an endomorphism of X. If the image is not complete, we can collapse two more. We end with a homomorphism from Y to a complete graph, so the chromatic number of Y is at most ω(X). Since this holds for all finite subgraphs, a compactness argument shows that χ(X)≤ω(X), and so equality holds.

Problem 92

(An update of Problem 85.) A magma (a set with a binary operation) is power-associative if the value of a power an is independent of the bracketing used to calculate it. The directed power graph of a power-associative magma is the digraph whose vertices are the elements of the magma, an edge from a to b if b is a power of a; the undirected power graph has an undirected edge connecting a and b if one is a power of the other.

It is known that if two groups have isomorphic undirected power graphs, then they have isomorphic directed power graphs. Does this hold for wider classes of power-associative magmas? (In particular, I conjecture that it holds for Moufang loops.)

Problem 93

A zero-one sequence is called universal if every finite zero-one sequence occurs as a (consecutive) subsequence of it.

Let s be the sequence whose nth term is 0 if the nth odd prime is congruent to 1 (mod 4), and to 1 if the nth odd prime is congruent to 3 (mod 4). Is s universal?

Unless I am missing something, this is probably a hard problem; but in view of the theorem of Green and Tao, it might be worth revisiting.

Problem 94

The theorem of Engeler, Ryll-Nardzewski and Svenonius asserts that, if T is a first-order theory in a countable language, then T is countably categorical (that is, all its countable models are isomorphic) if and only if the automorphism group of any countable model is oligomorphic (that is, has only finitely many orbits on n-tuples, for all n).

Sam Tarzi has asked whether an analogous result holds for homomorphisms and monoids. Let T have the property that all its countable models are hom-equivalent (that is, there exist homomorphisms in both directions between any two). What property do the endomorphism monoids of the models have? And does this monoid property imply that all countable models are hom-equivalent?

The theory of graphs in which every finite set of vertices has a common neighbour has the property that all its countable models are hom-equivalent.

Problem 95

This question is due to Sam Tarzi.

The countable random graph is characterised by the property that, given any two finite sets U and V of vertices, there is a vertex z joined to everything in U and nothing in V.

Does there exist a construction of the random graph in which the vertices and edges are computable but the witness z is not bounded by any provably computable function?

Presumably this would be a graph whose isomorphism to R would be unprovable in Peano arithmetic.

Problem 96

Consider a class of discrete minimization problems. Suppose that the cost of a solution is equal to the amount by which the objective function exceeds its true minimum value, and that the cost of computation is ε times the number of Turing machine steps reqired. What is the solution that minimizes the sum of these two costs? In particular, how does it depend on ε?

Problem 97

This problem was considered by Sharad Sane and me over 20 years ago: we failed to solve it. Sharad raised it again at the recent combinatorics conference in Cochin. It is connected with the Erdős–Lovász problem about maximal cliques of r-sets.

Given a 2-(v, k, 1) design (that is, a collection of k-subsets of a v-set with the property that any two points lie in exactly one of the subsets), the point set is covered by the r=(v-1)/(k-1) passing through a given point. Show that, if the design is not a projective plane (that is, if r>k), then the point set can be covered by a set of r blocks not of this form.

The assertion is easy to prove for k≤3.

Problem 98

This question was inspired by one of Stanislav Shkalin.

Anatoly Vershik and I, in Ann. Pure Appl. Logic 143 (2006), 70-78, gave a "random" construction of isometries of the Urysohn space such that every orbit is dense. The closure A of the group generated by such an isometry is abelian and transitive, and so gives the Urysohn space an abelian group structure.

Problem: Can we make the choice such that A has no non-trivial proper closed subgroup?

Problem 99

This question is due to Brendan McKay.

The rank of a function is the size of its image. A transformation monoid is synchronizing if it contains an element of rank 1.

Suppose that k transformations of {1,...,n} are chosen at random.

• What is the probability that the monoid they generate is synchronizing?
• Given that it is, what is the expected length of a shortest reset word (a word in the generators which has rank 1)?

Problem 100

Let H be a subgroup of the finite group G. Say that the pair (G,H) is good if G can be generated by a set of representatives of the right cosets of H in G.

• If coreG(H)=1 then G is good. Prove this without using the Classification of Finite Simple Groups.
• What can be said about the function f, where f(n) is the largest m such that if the index of H in G is n and coreG(H) can be generated by m elements, then (G,H) is good?

Problem 101

The power graph of a group G has as vertices the group elements, with two vertices adjacent whenever one is a power of the other.

It is known that the power graph of any group has clique number at most countably infinite. Is the same true for the chromatic number?

Problem 102

A submonoid of the full transformation monoid Tn on the set {1,...,n} is synchronizing if it contains a transformation whose image has size 1.

Is it true that two random transformations generate a synchronizing monoid with probability 1-o(1)?

Problem 103

Which graphs on n vertices have the property that they have at most i different induced subgraphs on i vertices, for some i<n/2 (where n is the number of vertices)?

To avoid uninteresting cases, assume that the graph is connected and not bipartite, and so is its complement. For i=2, every graph (except complete and null) has this property, and for i=3 every triangle-free graph and the complement of such; what about larger i?

Footnote: I didn't make the conditions strong enough. The graph should be vertex-transitive and edge-transitive.

Problem 104

This problem was suggested to me by Dennis Lin.

Let n be congruent to 2 mod 4. Define a cold matrix to be a skew-symmetric matrix of order n with (0 diagonal and) ±1 off-diagonal, and a hot matrix to be a matrix with +1 on the diagonal and otherwise skew-symmetric with entries ±1. Thus, C is cold if and only if C+I is hot. (The names arise because of the motivation from conference and Hadamard matrices.)

Conjecture: C has maximum determinant among cold matrices of order n if and only if C+I has maximum determinant among hot matrices of order n.

Problem 105

Characterise the primes p which have the property that there exists an element c of the multiplicative group of Z/(p) with the property that {c,c−1,−1} generates a proper subgroup of the multiplicative group.

Primes congruent to 1 (mod 4) have this property since −1 is a square and there are two consecutive squares. Also primes congruent to 1 (mod 3) have the property: take c to be a primitive 6th root of unity. There are others: the remaining primes less than 1000 with this property are 131, 191, 239, 251, 311, 419, 431 and 491.

This problem arose in my work with João Araújo on regular semigroups.

Problem 106

This is a conjecture of João Araújo.

Let G be a primitive permutation group on the finite set X, and let f be a map from X to itself whose kernel (the partition of X given by inverse images of points in the image) is non-uniform (has parts of different sizes).

Prove (or disprove) that the semigroup ⟨G,f⟩ contains a constant function.

Problem 107

This is a problem of Gregory Cherlin, slightly modified.

Is it true that any highly transitive permutation group G of countable degree which contains no finitary permutations has a subgroup H whose closure (in the topology of pointwise convergence) is the automorphism group of the random graph?

Problem 108

Let n be a positive integer, and c a vector in Rn whose components are linearly independent over Q. Is it true that any line with direction vector c passes arbitrarily close to a point with integer coordinates?

This is true for n = 2, by the simplest result about approximating irrationals by rationals. Maybe it is too much to ask for it to hold in general; if so, I'd like a specific example and a specific counterexample.

Solution: This is the multidimensional version of a theorem of Kronecker; it is proved in chapter 23 of Hardy and Wright.

Problem 109

Let p1 be a prime number. For every n, let pn+1 be the smallest prime divisor of p1...pn+1.
• Is it true that, for every n, there is a prime p1 for which none of the first n terms of the sequence is equal to 3?
• Is there a prime p1 for which no term of the sequence is equal to 3?
John Bray has done some substantial computation on this problem, which was originally suggested to me by Steve Donkin. John has not found any prime answering the second part (that is, it appears that 3 always occurs), but has observed empirically that the number of primes p1 for which none of p1, ..., pn is equal to 3 falls off by a factor greater than 3 when n increases by 1 (for n > 4).

Problem: Explain this!

Problem 110

Let G be a primitive permutation group of degree n, generated by a set S of permutations. Let x and y be distinct points of the domain. Form the directed graph D whose edges are all images of (x,y) under all words of length n−1 in elements of S.

Problem Is D necessarily strongly connected?

The cyclic group of prime order shows that the bound n−1 would be best possible.

Peter J. Cameron
p.j.cameron(AT)qmul.ac.uk
31 August 2013