Peter Cameron's Conjectures

Some conjectures of mine which have been proved include:

• A conjecture that a random element of the symmetric group belongs to no proper transitive subgroup except the symmetric and possibly the alternating group was proved by Tomasz Łuczak and László Pyber, Comb. Probab. Comput. 2 (1993), 505-512.
• A conjecture with Masao Kiyota on sharp characters whose values are zero and a family of algebraic conjugates was proved by Masao Kiyota and Sôhel Nozawa, J. Algebra 161 (1993), 216-229; Dean Alvis has generalised their result in Commun. Algebra 21 (1993), 535-554.
• A conjecture that universal sum-free sets have density zero was proved by Tomasz Schoen, Combin. Probab. Comput. 8 (1999), 277-280.
• A conjecture with Cheryl Praeger on parameters of block-transitive, point-imprimitive 3-designs has been proved by Avinoam Mann and Ngo Dac Tuan, Geom. Dedicata 88 (2001), 81-90.
• The Cameron-Erdős conjecture has two different proofs: by Ben Green, Bull. London Math. Soc. 36 (2004), 769-778; and by Alexander Sapozhenko, Discrete Math. 308 (2008), 4361-4369. [The conjecture stated that, if f(n) denotes the number of sum-free subsets of {1,...,n}, then f(n)/2^n/2 tends to a limit c_e or c_o when n tends to infinity through even or odd values respectively, and also gave formulae for the two constants.] A related Cameron–Erdős conjecture on the number of maximal sum-free sets has been proved by József Balogh, Hong Liu, Maryam Sharifzadeh and Andrew Treglown, J. Europ. Math. Soc. 20 (2018), 1885–1911.
• A conjecture (really Donald Keedwell's, refined by me) on simultaneous edge-colouring has been proved by Rong Luo, Wenan Zang, and Cun-Quan Zhang, Combinatorica 24 (2004), 641-657.
• An old conjecture that an algebra associated with the action on finite sets of an infinite permutation group with no finite orbits is an integral domain has been proved by Maurice Pouzet, Theor. Inform. Appl. 42 (2008), 83-103.
• A conjecture with Robert Liebler on collineation groups of projective spaces with equally many point and line orbits has been proved by John Bamberg and Tim Penttila, Commun. Algebra 36 (2008), 2503-2543.
• A conjecture with John Sheehan that a vertex-transitive cubic graph has a large semiregular group of automorphisms has been proved by Cai Heng Li, Proc. Amer. Math. Soc. 136 (2008), 1905-1910.
• A conjecture on the base size of primitive permutation groups has been proved by Tim Burness and various co-authors (R. M. Guralnick and J. Saxl, E. A. O'Brien and R. A. Wilson, M. W. Liebeck and A. Shalev): J. London Math. Soc. (2) 75 (2007), 545-562; Proc. London Math. Soc. (3) 98 (2009), 116-162; Israel J. Math. 177 (2010), 307–333; Bull. Lond. Math. Soc. 43 (2011), 386–391.
• A conjecture with C. Y. Ku on the second-largest set of intersecting permutations has been proved by David Ellis, J. London Math. Soc. 85 (2012), 165-190.
• A conjecture on polynomially bounded orbit growth for oligomorphic groups (and much more besides) has recently been proved by Justine Falque and Nicolas Thiéry.
• An infinite primitive permutation group which is not highly set-transitive has at least 2ⁿ/p(n) orbits on the set of n-element subsets, for some polynomial p. After results by Dugald Macpherson, Francesca Merola, and Pierre Simon, this was proved by Sam Braunfeld, arXiv 1910.04380.
• Not a conjecture, but a question answered affirmatively. Tim Wall conjectured that the number of maximal subgroups of a group of order n is at most n−1, and proved this for soluble groups. The conjecture turned out to be false in general; but Martin Liebeck, Laci Pyber and Aner Shalev gave a bound of cn^3/2. I asked whether similar results would hold for the number of systems of maximal blocks of imprimitivity for transitive permutation groups of degree n. This has now been proved (with the same numbers in both cases) by Andrea Lucchini, Mariapia Moscatiello and Pablo Spiga, arXiv 1907.08477.
• The Cameron–Fon-Der-Flaass conjecture on the cycle lengths of the "rowmotion" map on the set of antichains in the product of three chains was proved by Rebecca Patrias and Oliver Pechenik.

On the other hand, here are some refuted conjectures:

• A conjecture on the local compactness of cofinitary subgroups of the infinite symmetric group was refuted by Greg Hjorth, J. Algebra 200 (1998), 439-448.
• A strengthening of Isbell's conjecture: Given a prime p and a natural number d, there is a number k such that a finite p-group of permutations with d orbits, each of size at least p^k, contains a fixed-point-free element. This has been disproved by Eleonora Crestani and Pablo Spiga, Israel J. Math. 180 (2010), 413-424.

And here are some conjectures I would like to see settled:

• Suppose that a sum-free set of natural numbers is generated by the following procedure: start with an arbitrary sum-free subset of [1..m]; proceed greedily (that is, if an integer n is not the sum of two numbers already in the set, then include it). The resulting set is ultimately periodic.
• In a finite primitive permutation group, either the rank is bounded by a function of the subrank (the maximum rank of a point stabiliser on its orbits), or there is a base of size 2.
• The second row of a (uniform) random Latin square of order n tends to a (uniform) random derangement of the first as n tends to infinity.
• Cheryl Praeger and I showed that a non-trivial block-transitive t-design exists only if t < 8, and conjectured that 8 can be replaced by 6.
• There are only six positive integers greater than 2 which can be written as the sum of two powers of the same prime in more than two ways.
• There are infinitely many finite simple groups whose order is a prime plus one. (Despite appearances, this is a number theory conjecture!)
• The "α + n conjecture" (devised by participants at the Isaac Newton Institute programme on Combinatorics and Statistical Mechanics, along with David Wallace and Vladimir Dokchitser): if α is any algebraic integer, there is a natural number n such that α + n is a root of the chromatic polynomial of a graph.
• This one is not a conjecture, but a challenge: Prove, without using the Classification of Finite Simple Groups, that a finite transitive permutation group of degree greater than 1 contains a fixed-point-free element of prime power order. (This was proved using CFSG by Fein, Kantor and Schacher.)
• And closely related to the last is Isbell's Conjecture: for any prime p, there is a function g_p such that, if n = p^a.b where p does not divide b and a ≥ g_p(b), then any transitive group of degree n contains a fixed-point-free element of p-power order. (In other words, if one prime "dominates" n, then it is the prime which occurs in the last result.) Isbell conjectured this in the case p = 2.
• The road closure conjecture: Let G be a transitive permutation group. Then G is said to have the "road closure property" if, given any orbit O of G on 2-sets, and any proper block of imprimitivity B for G acting on O, the graph with edge set O\B is connected. Such a group must be primitive and basic, and cannot have an imprimitive subgroup of index 2; there is a family of groups derived from triality which also fail to have the property. The conjecture asserts that any other group satisfies the property. More details on arXiv 1611.80233.
• A conjecture with Mohammed Aljohani and John Bamberg: For n > 2k and I ⊆ {0,…,k−1}, let G(n,k,I) be the graph whose vertices are the k-subsets of {1,…,n}, two vertices adjacent if the cardinality of their intersection belongs to I. The conjecture asserts that there is a function F such that, if n > F(k) and the product of the clique number and independence number of the graph is equal to the number of vertices, then either I = {0,…,t−1} or I = {t,…,k−1} for some t such that a Steiner system S(t,k,n) exists. See Portugaliae Mathematica 74 (2018), 213-232.
• The "hanging curtains conjecture" first appeared in Rob Schumacher's thesis, after I worked on it with him and Celia Glass. Fix a value of n, and let a(m) be the greatest number of acyclic orientations of a graph with n vertices and m edges, as m runs from 0 to n(n−1)/2. The conjecture is in several parts: (a) if m is the number of edges of a Turán graph on n vertices, then this graph achieves the maximum; (b) the function a(m) is convex between successuve points corresponding to Turán graphs; and (c) if m is the number of edges of a Turán graph, then a(m)−a(m−1) > a(m+1)−a(m). (So the graph looks like curtains hanging from the Turán points.)

Peter J. Cameron
14 November 2022