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 n^{2}/4 edges with the maximum number of acyclic orientations (among such graphs) is the complete bipartite graph K_{n/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) = f_{k,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)n^{a−b}. So we might guess that f(n)/n^{a−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 E_{6}, E_{7} and E_{8} 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 = q^{2}+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 ≥ n_{0}(k) in 1983.
Problem 18: A reciprocity question
The cycle polynomial F_{G}(x) of a permutation group G is the polynomial ∑{x^{c(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|F_{G}(−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?
Peter J. Cameron
10 December 2020