## Old problems from my St Andrews web page

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.

1. 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.

2. 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.

3. 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.

1. Suppose that G is a finite group which can be generated by d elements. Is it true that, for any two elements x and y of G, if

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?

2. 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?

• For any element z of G, G = ⟨x,z⟩ if and only if G = ⟨y,z⟩;
• For any subset S of G, G = ⟨x,S⟩ if and only if G = ⟨y,S⟩.
(It is clear that the second condition implies the first. The second holds if and only if x and y lie in the same maximal subgroups 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

• I = {t,…k−1};
• Binom(ki,ti) divides Binom(ni,ti) for i ∈ I.

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×(vk) 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 vk, 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.

• Does S have a density almost surely?
• Is the spectrum of densities discrete above 1/6?
• Does it have a continuous part below 1/6?
• Is the set of universal sum-free sets (those for which the Cayley graph Cay(Z,S) is isomorphic to Henson's universal triangle-free graph) a null 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) : gG}, 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):

• Γ1 is the power graph, in which g and h are joined if one is a power of the other;
• Γ2 is the enhanced power graph, in which g and h are joined if the group they generate is cyclic;
• Γ3 is the commuting graph, in which g and h are joined if they commute;
• Γ4 is the complement of the generating graph, in which g and h are joined if they do not generate G.

(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:

1. Which finite groups have the property that Γi \ Γi−1 is connected (after isolated vertices are deleted)?
2. What can be said for infinite groups?

Reference:

1. Ghodratallah Aalipour, Saieed Akbari, Peter J. Cameron, Reza Nikandish and Farzad Shaveisi) On the structure of the power graph and the enhanced power graph of a group, Electronic J. Combinatorics 24(3) (2017), P3.16.

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

• G is oligomorphic but not highly transitive (and/or contains no finitary permutation);
• G satisfies Fn but not Fn+1?

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?

Peter J. Cameron
21 November 2022