Problem 1: Random synchronization
Choose two maps from the set {1,…,n} to itself at random. Does the probability that the semigroup they generate is synchronizing (i.e. contains an element of rank 1) tend to 1 as n→∞?
A paper by Mikhail Berlinkov in Algorithms and Discrete Applied Mathematics, LNCS 9602 (2016), 73-84, gives an affirmative solution to this question (the preprint is arXiv 1304.5774).
Problem 2: Hot and cold matrices
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 3: Symmetry of switching classes
Here are three problems on switching of graphs and tournaments (two of them solved). This replaces Problems 3, 8 and 9 on the original list, resulting in some re-numbering.
Let X be a graph on the vertex set V. The operation of switching X with respect to a subset A of V involves changing all edges between A and its complement into non-edges, and all non-edges into edges, while leaving adjacency within A or its complement unaltered. Switching is an equivalence relation on the set of graphs on V, whose equivalence classes are called switching classes.
We can define the automorphism group of a switching class in the obvious way; it contains the automorphism groups of the graphs in the class as subgroups.
For tournaments, switching is very similarly defined, but instead of switching edges and non-edges, we reverse the directions of edges. Switching classes and automorphism groups work in the same way.
Problem: Show that, with the exception of the switching classes of the complete and null graphs and finitely many others, a switching class whose automorphism group is primitive contains a graph whose automorphism group is trivial. Find all the finitely many exceptions.
Solution: This problem has been solved by Pablo Spiga and me, see Australas. J. Combinatorics 62 (2015), 76-90: full text here. There are just six exceptions up to complementation.
Problem: Is it true that, with the exception of the switching classes of the complete and null graphs and finitely many others, a switching class whose automorphism group is primitive contains a graph with trivial endomorphism monoid, with finitely many exceptions?
This is likely to be more difficult.
Now we turn to switching classes of tournaments.
It is known that a necessary condition for a permutation group G to be the automorphism group of a switching class of tournaments is that the Sylow 2-subgroups of G are cyclic or dihedral and act semiregularly.
Problem: Can one classify, for example, the primitive groups for which this condition is not sufficient?
Solution: Yes. A primitive group fixes a switching class of tournaments if and only if either it has odd degree and odd order (and so fixes a tournament), or it has degree q+1 and lies between PSL(2,q) and PΣL(2,q), where q is a prime congruent to 3 (mod 4).
Problem 4: Acyclic orientations
(with Celia Glass and Robert Schumacher) Is it true that, for n even, the graph with n vertices and n2/4 edges with the maximum number of acyclic orientations (among such graphs) is the complete bipartite graph Kn/2,n/2? (We know the number for complete bipartite graphs: it is a poly-Bernoulli number with negative index.)
Problem 5: A curious recursion
Given positive integers k,a,b, with a>b, define a function f(n) = fk,a,b(n) by the recursion
f(0) = k, f(n) = ⌈f(n−1)(a+n)/(b+n)⌉ for n>0.
How does this function behave for large n? If it were not for the ceilings, it would grow like (k/(b+1)…a)na−b. So we might guess that f(n)/na−b tends to a limit. For a=4, b=2, and k=1,…,12, the limit appears to be 1/6, 1/4, 1/3, 1/2, 1/2, 1/2, 2/3, 3/4, 5/6, 1, 1, 1; then adding 12 to k appears to add 1 to the limit.
Problem 6: Endomorphisms and partial isomorphisms
Given a finite group G, let End(G) be the semigroup of endomorphisms of G, and PIso(G) the semigroup of partial isomorphisms of G (isomorphisms between subgroups of G).
If G is abelian, then |End(G)| = |PIso(G)|. Does the converse hold?
Problem 7: Connection number and Möbius function
There is a well-known connection between the three polyhedral groups 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|/μ(1,G), where μ 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)? Or is there a natural explanation? The numbers are 3, 2, 1 respectively.
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 8: A diameter question
Given n and k with k < n, what is the smallest number d with the following property: given a set S of permutations of an n-set X generating a group G, and two k-subsets A and B of X in the same G-orbit, there is a product of at most d elements of S mapping A to B.
For k = 1, it is clear that n−1 suffices, and it is easy to construct examples showing this to be best possible.
I'm really interested in k = 2. Here n(n−1)/2−1 suffices, but I conjecture that the true value is much smaller (maybe a factor of 2 smaller?)
Problem 9: Groups generated by random loops
A quasigroup is a finite set with a binary operation satisfying the cancellation laws; that is, one whose Cayley table is a Latin square. A loop is a quasigroup with an identity element. The multiplication group of a quasigroup or loop is the group generated by the left and right translations (which are permutations).
It is known that almost every quasigroup (that is, a proportion tending to 1 as n → ∞) has multiplication group the symmetric group.
Problem: Does the same statement hold for loops?
Problem 10: Exchange for generating sets
This is a modification of the original Problems 12 and 13. See a forthcoming preprint by me, Andrea Lucchini and Colva Roney-Dougal for context.
The problem is in two parts.
⟨x,S⟩ = G if and only if ⟨y,S⟩ = G
holds for any d-element subset S of G, then it holds for any subset of arbitrary size?
Let G be a finite group. Suppose that every non-identity element is contained in a 2-element generating set for G. Are the following two properties equivalent for any pair x,y of elements of G?
Problem 11: Trees and cycles
Given a tree T on vertex set {1,…,n}, the edges form a set of n−1 transpositions whose product (in any order) is an n-cycle. If T is a star, then the (n−1)! orderings of the edges give rise to the (n−1)! cycles, each exactly once; but for any other shape of tree, we do not have a bijection. e.g. for the path on 4 vertices, of the six 4-cycles we obtain two twice, two once, and two not at all.
Problem: What is the distribution of frequencies of occurrence of cycles arising from orders of a given tree T?
Problem 12: Beyond Keevash's theorem
Let k be a positive integer, and I a subset of {0,…, k−1} such that neither I nor its complement is empty. For n ≥ 2k+1, let G(n,k,I) be the graph whose vertex set is the set of k-subsets of {1,…n}, two subsets joined if the cardinality of their intersection is in I.
Problem Show that, with finitely many exceptions (for given k), G(n,k,I) has clique number and chromatic number equal if and only if there exists t < k such that
Remark The second bullet point above gives the divisibility conditions necessary for the existence of a Steiner system S(t,k,n). According to the recent result of Peter Keevash, these conditions are also asymptotically sufficient. This fact will be relevant for the proof!
Problem 13: Counterexamples to Cauchy's theorem
Cauchy stated a theorem asserting that a primitive permutation group (one preserving no non-trivial partition of its domain) of degree a prime plus one is doubly transitive.
A century later, Neumann, Sims and Wiegold pointed out that this theorem is false: if S is a simple group of order prime plus one, then the group S×S, acting on S by left and right multiplication, is primitive but not doubly transitive.
Between 4 and 1000 there are 167 numbers of the form prime plus one; of these, five are orders of simple groups (60, 168, 360, 504, 660), and seven more are counterexamples to the "theorem" because of other types of primitive group (68, 84, 102, 234, 462, 620, 840). Continuing to 2500 there are two more simple group orders (1092 and 2448) and five further counterexamples (1040, 1320, 1550, 1584 and 2162).
Problem: Are there infinitely many numbers which provide counterexamples to Cauchy's "theorem"? If so, what is the density of the Neumann–Sims–Wiegold examples among them?
Problem 14: Agrawal's Conjecture
Let B be a block of a symmetric 2-(v,k,λ) design. Construct a k×(v−k) array as follows: first label the blocks different from B with the numbers 1,…, v−1. The rows of the array are indexed by the points of B and the columns by the points outside B. In the cell in row p and column q, we put the labels of the blocks which contain q but not p. Thus each entry is a set of size k−λ; the union of the entries in a row has size v−k, while the union of the entries in a column has size k.
The problem is to produce a new array with a single entry in each cell, that entry being chosen from the set in that position in the first array, in such a way that the entries in any row, and the entries in any column, are all distinct.
It is known that this is impossible for the Fano plane.
Conjecture: The construction above is possible in all other cases.
Problem 15: A universal sequence from the primes?
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 16: Random sum-free sets
A set S of natural numbers is sum-free if it contains no solution {x,y,z} to x+y = z.
We can choose a random sum-free set as follows: Consider the natural numbers in turn. When considering n, if n is the sum of two members of S, then n is not in S; otherwise decide whether to put n in S by tossing a fair coin.
A little is known, but much is not. Let S be a random sum-free set.
Problem 17: Forbidding intersection size 1
A very specific problem. Let n = q2+q+1, k = q+1. If it helps, suppose that a projective plane of order q exists. Let S be a collection of k-subsets of an n-set X, with the property that the intersection of two members of S does not have cardinality 1. The size of such a set is at most {n choose k}/n. Suppose that S attains this bound.
Problem: Is it true that, if q > 2, then the cardinality of the intersection of two members of S must be at least 2?
Note that Frankl and Füredi proved an analogous result under the assumption n ≥ n0(k) in 1983.
Problem 18: A reciprocity question
The cycle polynomial FG(x) of a permutation group G is the polynomial ∑{xc(g) : g∈G}, where c(g) is the number of cycles of g (including fixed points).
The orbital chromatic polynomial PΓ,G(x) of the graph Γ and subgroup G of Aut(Γ) is the polynomial whose value at the positive integer x is the number of G-orbits on proper colourings of Γ with x colours.
We call the pair (Γ,G) a reciprocal pair if PΓ,G(x) = (−1)n|G|FG(−x).
Problem: Find all reciprocal pairs.
For more information, see Peter J. Cameron and Jason Semeraro, The cycle polynomial of a permutation group, Electronic J. Combinatorics 25(1) (2018), Paper P1.14
Problem 19: Graphs and groups
Given a finite group G, we define four graphs with vertex set G, ordered by inclusion (i.e. the spanning subgraph relation):
(Note that Γ4 is complete if G is not 2-generated, and contains the commuting graph if G is 2-generated and non-abelian.)
There are classifications of finite groups where two of these graphs are equal (for the third and fourth, these are 2-generated non-abelian groups with all proper subgroups abelian, whose classification is folklore; for the others, it is in the paper of Aalipour et al [1].)Problems:
Reference:
Problem 20: Cliques and cocliques in Cayley graphs
Let G be a primitive permutation group with a regular subgroup H; then we can identify the set of points permuted with H so that H acts on itself by right multiplication. In particular, any G-invariant graph is a Cayley graph for H. Suppose that Γ is such a graph (not complete or null), and A a clique and B an independent set in Γ such that |A|·|B| = |H|.
Problem. Is it true that A−1 is also a clique?
This is true if G contains also H acting by left multiplication, so in particular if H is abelian. Its truth in general would resolve a problem in synchronization theory.
Problem 21: Random walks on graphs on groups
The commuting graph of a group G is the graph with vertex set G in which two elements are joined whenever they commute. (This specification includes a loop at every vertex.) The uniform random walk on this graph has the property that its limiting distribution is uniform on conjugacy classes.
To say that two elements commute is equivalent to saying that they generate an abelian group. So we could generalise the above graph by putting different specifications on the group generated by the two elements: for example, it is cyclic (this gives the enhanced power graph), or it is the whole group (this gives the generating graph).
Problem: What can be said about the uniform random walk on one of these graphs?
Problem 22: Finiteness conditions for oligomorphic groups
A group G is said to satisfy the finiteness condition Fn if it acts geometrically (that is, properly and cocompactly) on an (n−1)-connected CW-complex. It satisfies F∞ if it satisfies Fn for all n. Here, F1 is equivalent to being finitely generated, and F2 to being finitely presented. Finitely generated free groups satisfy F∞.
The Houghton group Hn satisfies Fn but not Fn+1. Also, this group contains the finitary symmetric group, so it is highly transitive.
Problem: Given a natural number n, does there exist a group G such that
Problem 23: A universality question for graphs on groups
The power graph of a group G has an edge {x,y} if one of x and y is a power of the other; the enhanced power graph has an edge {x,y} if both x and y are powers of an element z (in other words, the group generated by x and y is cyclic.
It is known that the power graph is the comparability graph of a partial order (and power graphs are universal for this class: that is, for any partial order, the comparability graph is embeddable as induced subgraph in the power graph of some group). Moreover, enhanced power graphs of groups form a universal class: every finite graph can be embedded as induced subgraph in the enhanced power graph of some group.
Problem: Suppose we are given a colouring of the edges of a finite complete graph with three colours, red, green, and blue. Under what conditions is it the case that the vertices can be embedded in a finite group in such a way that red edges belong to the power graph, green edges to the enhanced power graph but not the power graph, and blue edges to neither?
Some conditions are necessary. The red edges must form the comparability graph of a partial order; and if {x,y} is green then there must exist z such that {x,z} and {y,z} are red. Are these two conditions sufficient?
Problem 24: Orderings of vector spaces
A (total) ordering of a finite vector space is called compatible if every order-preserving bijection between subspaces of the same dimension is linear.
It is straightforward to show that every finite vector space has a compatible ordering: for example, choose any ordering of the finite field F; then the lexicographic ordering of Fn is compatible, for any n.
Problem: How many compatible orderings does the n-dimensional vector space over the field of order q have? (Formulae are known for the cases n = 1 and n = 2.)
Problem 25: Some design theory problems
A talk by Peter Keevash in the Pure Maths colloquium reported his successes on formerly untouchable problems in combinatorial design theory, including the existence of t-(n,k,λ) designs (collections of k-subsets of an n set such that any t-subset lies in exactly λ of them) for all values of the parameters such that the necessary divisibility conditions are satisfied and n is sufficiently large compared with the other parameters. Also, a similar result if "set", "subset" and "cardinality" are replaced by "vector space", "subspace" and "dimension" (over a fixed finite field). And even better, an estimate for how many such designs exist. A modification of the method deals with resolvable designs.This led me to wonder what the big remaining challenges are. Keevash's method tends to work if the blocks are of bounded size while the number of points is large. So probably the major problem now in combinatorial design theory is:
1. Which numbers n are the orders of finite projective planes?
It is widely conjectured that the answer is "prime powers, and these only", though a few years ago John Thompson proposed an alternative conjecture, that the answer is "orders of characteristically simple groups (that is, powers of orders of simple groups), and these only. In this case the number of points is about n2, while the block size is about n.
The smallest value which would distinguish between the two conjectures is of course 60, and I do not expect to see this resolved any time soon!
One can ask about the ultimate generalisation of resolvability. I will restrict myself to Steiner systems here (the case λ=1), though the problem is easily generalised.
2. Given t1<…<tm<k, suppose that the divisibility conditions for S(ti,k,n) are satisfied for 1≤i≤m, and that n is sufficiently large. Does there exist a partition of the k-sets into S(tm,k,n) systems, each partitionable into S(tm−1,k,n) systems, and so on all the way down?
Finally, here is an ABC problem, named after the proposers, not the parameters in the problem. This comes from the synchronization project; the authors are Mohammed Aljohani, John Bamberg and I.
3. Suppose that I is a nonempty proper subset of {0,1,…,k−1}, and that A and B are are sets of k-subsets of an n-set, with sizes of pairwise intersections of sets in A belonging to I and those of B to the complement of I. Suppose further that |A|·|B| is equal to the total number of k-sets, and that n is sufficiently large. Is it true that I or its complement must be {1,2,…,t−1)?
Note that, if this holds for I, then A is a Steiner system S(t,k,n), and B an EKR family. By Keevash's result, the Steiner system exists if the divisibility conditions hold (and n is sufficiently large).
Peter J. Cameron
5 March 2024