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?

    (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

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.

Peter J. Cameron
20 September 2016