These are problems which have been on my homepage and are now put out to grass. See also permutation group problems.
I have just learned (December 1998) that this problem is older: it is the "original Collatz problem" from the 1930s (before the famous 3x+1 problem). A paper by Jeff Lagarias gives details.
Solution by Peter Johnson.
Let r be the maximum number of edges from a vertex on one level to the next level, in a tree with n vertices at level k. Then rk is at least n, so r is at least n1/k.
From any tree of height k+1, we obtain at most k different trees of height k by suppressing one level (replacing the paths of length 2 crossing this level by single edges).
But there is some tree of height k from which at least p(n1/k) trees of height k+1 can be recovered by introducing a new level. (Choose a level where some vertex has at least n1/k upward edges; if the number of such edges is r, then we can split the r edges in p(r) ways giving non-isomorphic trees. (Treat all the other vertices on this level alike.)
So f(k+1,n)/f(k,n) is at least p(n1/k)/k.
For motivation, see On the probability of connectedness in Discrete Mathematics 167/168 (1997), 173-185.
Is it true that, if the ratio cn/an tends to a positive limit as n tends to infinity, then c(r) converges?
For further information, see papers in Discrete Mathematics 167/168 (1997), 173-185; and Electronic J. Combinatorics 7(1) (2000), article #R33.
For example, when n=2, the collections of necklaces are (R)(R), (R)(B), (B)(B), and (RB); (RR) and (BB) are not allowed. The strings are RR, RB, BR, BB.
Problem: find a bijective proof of this fact.
Solutions were given by Dima Fon-Der-Flass, Rosemary Bailey, and Robin Chapman. Then Roger Bryant drew my attention to C. Reutenauer, Free Lie Algebras, London Math. Soc. Monographs (New Series) 7, Oxford University Press, 1993, which contains this and more.
An account of my secret agenda in asking this question is in the paper The algebra of an age, in Model Theory of Groups and Automorphism Groups (ed. David M. Evans), London Math. Soc. Lecture Notes 244, Cambridge University Press, 1997, pp. 126-133.
For example, if G is the path of length 3, then the probability of connectedness in n-vertex graphs in X(G) is 1/2 for all n>1.
Solution by Jeannette Janssen:
Use the terms S-sequence and U-sequence for the sequences counted by s(n) and u(n). The left-hand side of the equality counts U-sequences ending in n; removing the last term gives a U-sequence with sum less than n.
Given an S-sequence, we can add or remove 1 without changing the S-sequence property. So the right-hand side counts S-sequences containing 1.
Now take one of these U-sequences, say u1, u2, ...; the corresponding S-sequence is 1, 1+u1, 1+u1+u2, ...
Note: this problem is from my combinatorics textbook, for which a Web page now exists.
There are obviously some points of detail in the physics to discuss. Dima Fon-Der-Flaass has an argument to show that, if the loss of energy is infinitesimally slow, and the triangle has unequal sides, then the probabilities are either 1/2, 1/4, 1/4 or 1/2, 1/2, 0.
This assumption is not physically realistic. Paul Glendinning found the even more surprising result that there is a collection of non-trivial intervals, arbitrarily close to 0, such that if the dissipation rate d lies in one of these intervals, then the probabilities are 1, 0, 0 for almost all initial conditions; that is, there is one face on which the prism is almost certain to land. See P. Glendinning, Inaccessible attractors of weakly dissipative systems, Nonlinearity 10 (1997), 507-522.
Franco Vivaldi pointed out that, if instead the prism is turned to a random orientation and dropped onto a plane covered with glue, then the probabilities are proportional to the angles subtended by the sides at the centroid of the triangle.
For an infinite oligomorphic group (one with Fi finite for all i), the alternating sum may make sense (i.e. it may converge, or some other summation method may apply), even though the proportion of derangements does not. Problem: What does this mean?
For example, in the infinite symmetric group, Fi=1 for all i, and the sum is 1/e, which is just the limiting proportion of derangements in finite symmetric groups.
A more mysterious example is the group of order preserving permutations of the rational numbers. Here, fi=i! for all i, and the sum is 1-1+1-1...=1/2 (according to Euler). In what sense are half of the order-preserving permutations derangements?
For a closely related problem, see here.
The conjecture is true if the degrees are all equal, or if every degree is either 2 or 3.
This problem is also Problem 16.15 in the list of BCC16 problems (PostScript file). See also Discrete Math. 197/198 (1999), 799-812.
This problem has been solved by Rong Luo, Wen-An Zang and Cun-Quan Zhang, Combinatorica 24 (2004), 641-657; doi: 10.1007/s00493-004-0039-2
Problem: Find a formula for, or an efficient means of calculating, an.
The number an has other combinatorial interpretations:
Solution: yes; I found one by hand:
(b) Do there exist twelve subsets of the set 1..15 with the above properties?
Solution: no (by a combination of case analysis and computer search).
Remark. The next interesting open case is eighteen subsets of 1..21. This has been settled in the negative by Pablo Spiga (personal communication).
Clearly this problem should be updated to ask for some analysis of configurations satisfying the two conditions 1 and 2 above!
A simple argument with generating functions shows that
A0An + A1An-1 + ... + AnA0 = 4n.
(The generating function ∑Antn is equal to (1-4t)-1/2, by the binomial theorem.)
Problem. Find a "counting proof" of this identity.
This problem is due to Alastair King and Andrew Swann. I heard it from Geoff Smith. A solution was found by Omer Egecioglu. Subsequently, Robin Chapman told me that the result is due to Daniel J. Kleitman, A note on some subset identites, Studies in Applied Mathematics LIV 289-293 (1975). Then an even earlier `proof' was unearthed in W. Feller's classic An Introduction to Probability Theory and its Applications, by Alastair King. Here are his comments (with an addition by Robin Chapman):
Solution: As observed by Kleitman, the "central binomial convolution identity" amounts to the fact that the number of balanced +1/-1 sequences (random walks) is equal to the number of never balanced ones of the same length.
A simple combinatorial proof of this fact can be extracted from the probability literature:
W. Feller, An Introduction to Probability Theory and its Applications, Wiley, New York, 1950.
The result plays a fundamental role in the analysis of random walks (Main Lemma III.3.1). The proof given in the text is not strictly combinatorial, but Problem III.10.7 asks for a purely combinatorial proof and sketches the construction of a bijection which is attributed to E. Nelson. Confusingly, the sketch appears to construct a bijection with another set of random walks of the same size, namely those which are non-negative. However, a small modification yields the following:
Identify the "initial" segment of a walk as being:
Note: the first and last steps in an initial segment have the same sign. Thus balanced walks that start -1 correspond to never balanced ones that start +1 (and vice versa).
Among the ordered pairs of monic polynomials of degree n over GF(2), exactly half consist of relatively prime polynomials. Find a nice bijection between the relatively prime pairs and the non-relatively-prime pairs.
Added 3/12/2007: This problem has been solved by
1. Is it possible to partition the 4-subsets of a 16-set into 13 sets of 140 subsets, each set isomorphic to the set of planes in the affine space AG(4,2)?
Solution: Rudi Mathon informs me that Luc Teirlinck has shown the non-existence of such a partition. I will add the reference when I find it.
Of course, one can now ask for a partition of the 4-subsets of a 32-set into 29 copies of AG(5,2).
2. Is there a Steiner system S(3,5,26) (a set of 5-subsets of a 26-set with the property that any 3 points lie in just one of them) having the property that there are no three of the blocks which have pairwise intersections of size 2 but the intersection of all three is empty? Such a design would give rise to a strongly regular graph on 352 vertices and hence to a biplane with 352 points and the same number of blocks.
1. Call a row of a Latin square even or odd according as it is an even or an odd permutation of the set {1,2,...,n}. Prove that the number of even rows of a random Latin square of order n is approximately binomial B(n,1/2). (The best result in this direction is due to R. Häggkvist and J. Janssen, Discrete Mathematics 157 (1996), 199-206: the probability that all rows are even is exponentially small.)
2. Define a probability measure on permutations of {1,2,...,n} as follows: the probability of a permutation is the proportion of Latin squares with first row (1,2,...,n) in which it occurs as the second row. What can be said about this distribution? (For example, a permutation has non-zero probability if and only if it is a derangement.) In particular, prove that the probability that a permutation lies in no transitive proper subgroup of the symmetric group except possibly the alternating group tends to 1 as n approaches infinity.
(The analogous result for the uniform distribution was proved by T. Luczak and L. Pyber, Combinatorics, Probability and Computing 2 (1993), 505-512. Their result gives a simple deduction that the group generated by the rows of a random Latin square is almost surely the symmetric group. A solution to this problem would give the same conclusion for a random "normalised" Latin square.)
Note added 28 July 2005: I now believe that the distribution defined here "approaches" the uniform distribution on derangements as n grows. For example, when n=7, the numbers of ways of extending a two-rowed Latin rectangle corresponding to each type of derangement (with cycle lengths 7, 2+5, 2+2+3, and 3+4 respectively) are 6566400, 6604800, 6635520, and 6543360 respectively.
This would imply that the density of the set of numbers with no such representation is 1/2. It would also imply that there exist integers with arbitrarily many such representations. Either of these assertions would be a nice result!
Any positive integer can be written uniquely as the sum of non-consecutive Fibonacci numbers. Hence we can define the Fibonacci successor function on the natural numbers by taking this expression and "moving each Fibonacci number along one". So, for example, 40 = 34 + 5 + 1; its Fibonacci successor is 55 + 8 + 2 = 65.
Now produce a table in which each row begins with the smallest number which doesn't occur in any earlier row, and all further entries are obtained by applying the Fibonacci successor function. (So the top row consists of the Fibonacci numbers 1, 2, 3, 5, 8, ...; the next begins 4, 7, 11, ...) It turns out that if we extrapolate each row back two steps using the recurrence relation for the Fibonacci numbers, we obtain the natural numbers 0, 1, 2, 3, ...; this gives a convenient numbering of the rows. Every positive integer occurs exactly once in this table, and every sequence of positive integers satisfying the Fibonacci recurrence relation agrees from some point on with a row of the table.
Now let xn denote the fractional part of n times the golden ratio. Let an and bn be the number of earlier terms of this sequence to the left and the right respectively of xn (including 0 and 1). The sequence of pairs (an, bn) begins (1,1), (1,2), (3,1), (2,3), (1,5), (5,2), ...
If we look at the pairs occurring in the Fibonacci-numbered positions, we see (1,1), (1,2), (3,1), (1,5), ... In other words, one number in the pair is 1, and it bounces from side to side as we progress along the sequence. This follows from well-known properties of the continued fraction expansion of the golden ratio.
Problems. If we consider the pairs in the positions numbered by any fixed row in the table, show that there is a "bouncing number" which alternates sides in the pairs. Which numbers occur as "bouncing numbers"?
For example: row number 1 of the table is 4, 7, 11, 18, 29, ...; the pairs in these positions are (2,3), (3,5), (9,3), (3,16), (27,3), ...; so the "bouncing number" is 3. The "bouncing numbers" for rows 0, 1, 2, 3, 4, ... appear to be 1, 3, 2, 5, 8, 5, 9, ...
Further information here, in DVI or PostScript.
If P is a 2-group which is not elementary abelian, then some non-identity element of the centre of P is a square.Solution: The answer to this question is negative. The smallest counterexamples have order 128, and there are two of them. This was found by Alexander Hulpke and Andreas Caranti. Alexander provided the following example in GAP:
gap> g:=SmallGroup(128,36);If not, is the following weaker statement true?gap> z:=Centre(g); Group([ f6, f7 ]) gap> r:=List(ConjugacyClasses(g),Representative);; gap> s:=Filtered(r,i->Order(i)>2);; gap> List(s,Order); [ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 ] gap> Set(List(s,i->i^2)); [ f4, f5, f4*f7, f5*f6, f3*f4*f5, f3*f4*f5*f6, f3*f4*f5*f7, f3*f4*f5*f6*f7 ] gap> List(last,i->i in z); [ false, false, false, false, false, false, false, false ]
If P is a 2-group which is not elementary abelian, and Q is a core-free subgroup of P, then there is an element lying in no conjugate of Q which is a square.Avinoam Mann also suggested the above group as a possible counterexample to the second question. However, Steve Linton and John Murray both checked that there is no core-free subgroup Q for which it is a counterexample. So the question is still open.
Solution (13 September 2004): The answer to the second question is also negative. Pablo Spiga found that the group of order 128 with generators (1,2,7,3)(4,8)(5,11)(6,9)(10,14)(12,16,13,15), (1,4,7,5)(2,8)(3,11)(6,13,14,12)(9,15)(10,16), and (1,6)(2,9,3,10)(4,12,5,13)(7,14)(8,15)(11,16) is a counterexample. Indeed, in this group the set of elements with fixed points coincides with the set of squares. This group is SmallGroup(128,836) in the GAP library.
This was motivated by the question of whether a vertex-transitive cubic graph necessarily has a semiregular group of automorphisms of order greater than 3 (see Problem 50), which is now solved in the affirmative.
Problem: Does condition 2 follow from 1 and 3 in general? Does 3 follow from 1 and 2? Does 1 follow from 2 and 3? (Assume that λ is greater than 1.)
Dima Fon-Der-Flaass has shown that condition 1 does not follow from 2 and 3. An example for λ=2: it is easy to find n subgraphs of Kn, each having n-1 edges, in such a way that every edge belongs to exactly two of them, and every two subgraphs have a single edge in common. The subgraphs can be arbitrary.
Santi Spadaro points out that 3 does not follow from 1 and 2, essentially because we can take a symmetric graph design and choose an arbitrary subset of the graphs Xi. Moreover, 2 does not follow from 1 and 3: take all graphs on n vertices isomorphic to a fixed graph X; then 1 and 3 hold but 2 usually fails. This problem is now completely settled in the negative. (11 June 2002)
For example, when k=2, the groups are the tetrahedral, octahedral and icosahedral groups, acting on the vertices, edges and faces of the corresponding polyhedra. (Every rotation has an axis, so has just two fixed points in this action.) So the correct bound is 60. (This is a theorem of Iwahori, J. Fac. Sci., Univ. Tokyo 11 (1964), 47-64.)
C. Franchi, in European J. Combinatorics 22 (2001), 821-837; doi: 10.1006/eujc.2001.0508, solved this by giving the bound max{60,a!a(a!a-1)}. I don't know whether this can be improved.
It follows that the centraliser of a in G is a p-group. Let its order be pm.
A theorem of Kegel (Math. Z. 75 (1961), 373-376) shows that G is nilpotent. Then a theorem of Khukhro (Mat. Zametki 38 (1985), 652-657) shows that G has a normal subgroup whose nilpotency class and index are bounded by functions of p and m.
Is it true that the nilpotency class of G is bounded by a function of p and m?
Solution: This question has been settled in the affirmative by Andrei Jaikin, using a theorem of E. Khukhro, On locally nilpotent groups admitting a splitting automorphism of prime order, Mat. sb. 130 (1986), 120-127.
It is known that a quaternary relation is a separation relation if and only if its restriction to every 5-element set is a separation relation.
Let P be an inversive plane, C a circle of P. Define a relation S on C by the rule that S(a,b,c,d) holds if every circle through a and b meets every circle through c and d.
Problem: What does it mean for P if, for every circle C of P, the above relation S is a separation relation?
(a) Is there an efficient method to decide whether a set of partitions is the image under F of a subgroup of Sn?
(b) If G and H are subgroups of Sn such that F(G)=F(H), then G and H have the same order. Are they necessarily isomorphic?
Note added 19 May 2000: The answer to (b) is negative. Eamonn O'Brien has shown that there are two pairs of groups of order 64 (numbers 19 and 111, and 94 and 249, in the lists in MAGMA and GAP), which act transivitely on 16 points, such that the two groups in each pair give rise to the same sets of cycle partitions. You can find a GAP program to verify this.
For further details see a paper in Discrete Math. 291 (2005), 45-54; doi: 10.1016/j.disc.2004.04.019
Which graphs have the property that, for any partition of the vertex set into three parts, the induced subgraph on the union of some two of the parts is isomorphic to the original graph?
Note 26/6/2000: This problem is solved: see the paper by Bonato, Cameron, Delic and Thomassé in European J. Combinatorics 23 (2002), 257-274; doi: 10.1006/eujc.2002.0574
F(x) = P(x+1).
Now consider the linear analogue. Let G be a subgroup of the general linear group GL(n,q). For i = 0, ..., n, let pi be the probability that the fixed points of a random element form precisely an i-dimensional subspace, and let Fi be the number of orbits of G on linearly independent i-tuples. Again the two sequences determine each other.
Problem: Express the relation between these two sequences in terms of generating functions.
Note: This problem is now solved (2 August 2000). It is just a case of finding the right definitions of the q-analogues! See my paper with Shahn Majid in Communications in Algebra 31 (2003), 2003-2013.
Let G be a permutation group on the infinite set X. Assume that G is oligomorphic, that is, G has only finitely many (say fn) orbits on the set of n-element subsets of X. Dugald Macpherson, Proc. London Math. Soc. (3) 46 (1983), 471-486, showed that, if G is primitive on X (preserves no non-trivial equivalence relation) but not highly set-transitive ((that is, fn > 1 for some n), then the sequence (fn) grows exponentially, that is, limsup (fn)1/n > 1. These two assumptions apply throughout this problem, though analogous problems can be posed with primitivity relaxed.
Further information on such sequences is available in my survey article.
if (1/x1) + ... + (1/xn) < a, then (1/x1) + ... + (1/xn) <= a-b.Problem: If a is an integer, find an explicit lower bound for b in terms of n and a.
Added 12 March 2001: The problem of bounding k has been solved by my colleague R. A. Bailey. For a non-abelian group G, the value of k is at most 2 for the first question, 5 for the second. These bounds are best possible. The problem of classifying all groups attaining the bounds (or, indeed, having one of these properties for a positive k) remains open.
Added 22 March 2004: Pablo Spiga has pointed out that such a group must be a p-group of Frattini class 2.
∏n>0(1-qn)-c(n) = 1 - q + 2∑n>0c(n)qn.This somewhat resembles in form the denominator identity of a Kac-Moody Lie algebra.
Problem: Is there a nice connection?
If (1), (2), (3+) and (4) hold, we have an association scheme. Conditions (1), (2), (3) and (4) define a homogeneous coherent configuration. Conditions (1), (2), (3+) and (4-) define a Jordan scheme (so-called because the span of the matrices is a Jordan algebra).
The operation of symmetrizing involves, for each non-symmetric matrix Ai, replacing it and its transpose by their sum (a symmetric zero-one matrix). It is easy to see that symmetrizing a homogeneous coherent configuration gives a Jordan scheme.
Problem: Is there a Jordan scheme which is not obtained by symmetrizing a homogeneous coherent configuration?
Problem: What is the relation between the Tutte polynomial of the matroid and the cycle index of the permutation group?
It is known that sometimes the first determines the second and sometimes vice versa. Perhaps there is a gadget which generalises both! See my paper in Electronic J. Combinatorics 9(1) (2002), #N2 (10pp).
Combinatorics Study Group notes on primitive lambda-roots are available. For reasons explained therein, the number can be counted in principle by inclusion-exclusion, but there is unlikely to be a neat formula ...
Note: The quaternion group Q8 shows that we cannot make the least element of B(n) correspond to the identity in general.
Let A be an affine plane of order q. Is it possible to find, for each point x of A, a permutation px of the set of parallel classes of A with the properties
There is no solution for q=2, since there are only two derangements and four points. For q=3, there is a solution. It is conjectured that a solution exists for all larger q.
What is the size of the largest sum-free set (one not containing two points and their vector sum) in the square {1,...,n}×{1,...,n}? In particular, show that the number is cn2+O(n), and find the constant c.
Upper and lower bounds for c are e-1/2=0.6065... and 3/5=0.6 respectively. The lower bound for the number is the integer part of 3n(n+1)/5. Proofs can be found here.
Let G and H be permutation groups acting on sets X and Y respectively. We consider G×H as a permutation group on X×Y. We have
Solution: Solved by Daniele Gewurz. See a paper by Daniele Gewurz, Francesca Merola and me in Discrete Mathematics 308 (2008), 386-394; doi: 10.1016/j.disc.2006.11.054
For k=0, the value of m is the integer part of n/2. For k=1 and even n, it does not exceed n-1, but I do not know whether this is the exact value. (Note: Kézdy and Snevily conjectured that n-1 is the correct value in this case, and that the value is at least n for odd n. This conjecture implies two celebrated conjectures by Ryser and Brualdi on Latin squares: Ryser conjectured that any Latin square of odd order has a transversal, and Brualdi that any Latin square has a partial transversal of size n-1.)
A related question: Is it true that, if S is the set of rows of a Latin square of order n, there is a permutation agreeing with each element of S in at most two places? Note: The answer is "yes": see my paper with Ian Wanless in Discrete Math. 293 (2005), 91-109.
Following Carmichael, a primitive lambda-root of n is a unit in the integers modulo n which has the largest possible order. Let F(n) be the number of primitive lambda-roots of n. If primitive roots of n exist (that is, if n is an odd prime power, or twice an odd prime power, or 4), then F(n)=phi(phi(n)), where phi is Euler's totient function. However, this equation holds for other numbers too; indeed, it is true for more than half of the integers up to a million. In general, the left-hand side is at least as large as the right-hand side.
Problem: Is it true that the proportion of natural numbers for which the equation F(n)=phi(phi(n)) holds tends to a non-zero limit? If so, what is the limit?
See our notes on primitive lambda-roots for more details.
Solution: This problem has been solved by T. W. Müller and J.-C. Puchta: the limiting proportion is zero (though it tends to zero rather slowly). I will give the reference when the paper appears.
Pablo Spiga points out that, if q is congruent to 1 mod 4, then the stabiliser of an unordered pair of points has the above property, and has size q-1.
Let p1, ..., pm be partial permutations of a finite set A (that is, bijections between subsets). Suppose thatWhat is the computational complexity of this problem? How is this affected if we insist that B=A?Does there exist a finite set B containing A, and permutations fi of B extending pi for i=1,...,m, such that, if pk extends pi o pj, then fi o fj = fk?
- p1 is the identity map on A, and
- for any i,j, there is at most one k such that pk extends pi o pj.
Some notes about this question are here.
Problem: Find a pair (X',T') realizing each of these sequences, in terms of the pair (X,T) realizing the original sequence.
The first sequence is not likely to be easy. For example, let p be a prime. The constant sequence with value p is realized by the identity permutation of a set of size p. An obvious realization of the sequence (pn) is (X,T), where X is the algebraic closure of the field with p elements and T is the Frobenius map T(x)=xp.
The second, however, is reasonably straightforward. Indeed, let f be a function on the natural numbers such that n divides f(n), and suppose that there is a function g such that g(m) divides n if and only if m divides f(n). Then a realization of (u(f(n))) can be constructed directly from a realization of (u(n)). The function f(n)=nk has these properties. The proof is here.
A graph G is said to be homomorphism-homogeneous, or HH, if any homomorphism from a finite subgraph of G into G can be extended to an endomorphism of G.
All finite HH graphs are known. The countable examples we know are disjoint unions of complete graphs of the same size, and graphs which contain the random graph R as an induced subgraph.
Problem: Are there any others?
Note: The analogous problem for posets has been solved by D. Lockett.
What can be said about the asymptotics of a sequence a for which b(n) ~ c·a(n) for some constant c > 1?
Many interesting sequences (e.g. chains in the partition lattice, zero-one matrices with n ones and no non-zero rows or columns) have this property.
Is it true that
∑k XikXkj = nXij+h(h-1)J,where J is the all-one matrix?
Solution: This problem is now solved in the affirmative (but I have lost the solution . . .)
Problem: Find the best bound. In particular, there a polynomial (or even a quadratic) bound?
Is it true that a vertex-transitive trivalent graph has a semiregular automorphism (one with all cycles of the same size) of order greater than 2?
Note: This has now been settled affirmatively: see P. J. Cameron, J. Sheehan and P. Spiga, Europ. J. Combinatorics 27 (2006), 924-930; doi: 10.1080/00927870701404812, and a stronger result has been given by Cai Heng Li, Proc. Amer. Math. Soc. 136 (2008), 1905-1910.
For a finite group G, let n(G) denote |G|/mu(1,G), where mu 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)? The numbers are 3, 2, 1 respectively.
The coincidence becomes sharper if we include the correspondence between cyclic and dihedral groups and the root lattices An and Dn, for which the numbers also agree up to sign if n+1 is squarefree. (This requires some charity about the interpretation of the McKay correspondence.)
A subsidiary question: If there is a natural explanation, what is the interpretation for root lattices of the sign of the Möbius function?
Clearly b(G) <= s(G). Is it true that, if G is primitive but not 2-transitive, then s(G) <= b(G) log n?
See Combinatorics Study Group notes on this problem (PDF file).
Let p be a prime congruent to 3 mod 4, and let r=(p+1)/2. Let (x/p) denote the Legendre symbol (taking the values +1, -1, or 0 according as x is congruent to a nonzero square, a non-square, or zero mod p. Show that the r×r matrix with (i,j) entry ((j-i)/p) has determinant 1.
This is true for primes less than 1000.
Problem: Find a bijective proof!
A permutation (represented by a n × n permutation matrix P) is said to be binary if no two 1s in P are on the same northeast-southwest diagonal. The shadow of a binary permutation is the (2n-1)-tuple (indexed from 2 to 2n) with 1 in position i+j if Pij=1, and other entries 0.
C. Bebeacua, T. Mansour, A. Postnikov, and S. Severini conjecture that the number of score sequences of n-vertex tournaments is equal to the number of shadows of binary permutations on n elements.
Problems: Prove (or refute) this conjecture! If it is true, find a bijective proof.
Now suppose that a Su Doku puzzle is given. (By definition, a Su Doku must have a unique solution.) Consider the following algorithm:
First, for each blank cell, calculate the "free set" consisting of numbers not appearing in the row, column, or subsquare containing that cell. Now repeat the following until no further progress occurs:
Remark: Daniele Gewurz and Francesca Merola have pointed out that solutions to this problem can be found on Gordon Royle's Sudoku page.
Given a completed Su Doku design (a 9×9 Latin square divided into nine 3×3 subsquares each of which contains the numbers 1,...,9 once), consider the following block design:
Added 26/11/2005: A solution has been found by Emil Vaughan:
|
|
|
|||||||||||||||||||||||||||
|
|
|
|||||||||||||||||||||||||||
|
|
|
So let me pose a further question. Is there such a square in which the graph with vertex set {1,...,9}, two vertices joined if they lie in five blocks, is the "window graph" (the line graph of K3,3, or the Paley graph of order 9)?
Added 05/12/2005: This too can be done. So one more test: is there a square in which the short rows and short columns are separately nearly balanced? Perhaps one could ask whether each pair of numbers lies in 2 or 3 short rows and 2 or 3 short columns, total 4 or 5? But a computation shows that this is not possible! In fact we cannot place more than five numbers subject to these constraints without getting stuck.
Also, one can find such a square where the block concurrences are 3 and 6, or 2 and 7, or 0 and 9, but not 1 or 8.
For more on this and related constructions see the preprint.
Is F closed under pointwise multiplication?
I conjecture that the answer is "no". Specifically, let F be the sequence (1,2,4,10,26,...) whose nth term is the number of solutions of g2=1 in the symmetric group of degree n. This sequence belongs to F, but I conjecture that the sequence (1,4,16,100,676...) whose terms are the squares of the terms in this sequence is not in F.
Remark: The set of sequences counting orbits of permutation groups on all n-tuples is closed under pointwise multiplication. Moreover, the set of sequences counting orbits on n-tuples of distinct elements for groups with the property that the stabiliser of a finite set fixes no additional points is closed under pointwise multiplication.
Further remark: The answer in general is "no": if G is the stabiliser of a point in the symmetric group, the sequence begins 2, 3, 4, ..., but a group with 4 orbits on points must have at least 12 orbits on ordered pairs of distinct points. It is harder for transitive groups (where a possible counterexample is given in the question), and still more so for primitive groups.
Prove that any isometry of this metric space is the product of the operation of symmetric difference with a fixed measurable set, and a measure-preserving transformation of [0,1].
Remark: This problem is now solved, using a theorem of Lamperti from 1958. (Thanks to Cho-Ho Chu for directing me to this!) See Cameron and Tarzi, Topology and its Applications 155 (2008), 1454-1461; doi: 10.1016/j.topol.2008.03.022
Added 6 September 2007: This problem has been shown to be NP-complete by Emil Vaughan. The complexity status in the case where the regions are polyominoes (or even rectangles) is unknown.
xixj = xgcd(i,j)xlcm(i,j)for all i,j.
Problem: What is the Hilbert series for A(n), the generating function for the sequence whose kth term is the dimension of the space of elements of degree k in the algebra?
Note: This problem has been solved by Daniele Gewurz and Francesca Merola, and by Pablo Spiga. Natalia Iyudu has also found results on it. I hope that a reference will be added soon.
The first of the following sequences is the number of commuting triples of elements in the symmetric group Sn, divided by n! . The second is the number of non-zero elements in the character table of Sn.
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1st | 1 | 4 | 8 | 21 | 39 | 92 | 170 | 360 | 667 |
| 2nd | 1 | 4 | 8 | 21 | 39 | 92 | 170 | 331 | 593 |
Problem: What is going on here?
Problem: Given k≤n, what is the number of choices which result in exactly k drivers parking?
Added 19 November 2007: Pascal Schweitzer and Daniel Johannsen have found a formula (involving a single summation) for these numbers. Thomas Prellberg has shown that, after re-scaling by the square root of n, the probability density function for the number of drivers who fail to park successfully is 4x exp(-2x2). The paper is here.
The most extreme example I know is an extension of a 2n-dimensional vector space over GF(2) by a dihedral group of order 2(2n+1); this has rank 2n and subrank 2n-1+1. So perhaps the conjecture holds with a linear function f.
A graph G is called core-transitive if any isomorphism between cores of G can be extended to an automorphism of G.
Problem: What can be said about core-transitive graphs?
The context is a theorem of Cauchy which states that a primitive permutation group of degree prime plus one is doubly transitive. Neumann, Sims and Wiegold pointed out in 1968 that this is false: if S is a non-abelian finite simple group, then S × S, acting on S by left and right multiplication, is primitive but not doubly transitive. The first few finite simple groups have order a prime plus one. So the question asks whether this construction gives infinitely many counterexamples to Cauchy's "theorem".
Conjecture: Let a be an algebraic integer. Then there exists a natural number n such that a + n is a root of the chromatic polynomial of a graph.
Remarks:
This is perhaps a model for a network where channels silt up if not used. It is rather open-ended, so feel free to interpret or change the hypotheses.
Consider a network in which all edges have capacity 1. At unit time steps, perform the following operation:
Eventually the network will be reduced to c edge-disjoint paths from source to target, where c is the capacity. What can be said about the time required for this to happen?
For example, if the network is a cube and the source and target are antipodal vertices, the expected time required is 19.5.
This problem is due to Tatiana Gateva-Ivanova. The topic is set-theoretic solutions of the Yang-Baxter equation, but no background knowledge is needed to understand the problem.
Let X be a finite set. A solution is a pair of maps L and R from X to the symmetric group on X satisfying the three conditions (for all x, y in X), where the image of x under L is denoted by Lx:
Problem: Given any solution in which X has more than one element, show that there exist distinct points x, y in X such that Lx=Ly.
This problem is due to Josephine Kusuma. Let C be a set of binary n-tuples. The (Vapnik-Chervonenkis) dimension of C is the largest t such that, in every projection of C onto t coordinates, each binary t-tuple occurs; and the strength of C (as orthogonal array) is the largest t such that, in every projection of C onto t coordinates, each binary t-tuple occurs equally often. Clearly strength is not greater than dimension, and the two parameters are equal if C is a binary linear code.
Now suppose that C is a Gray map image of a linear code over Z4, and C has dimension t. What can be said about the strength of C?
Solution: It is at least 1+t/2 (rounded down), and this is the best possible lower bound.
Let S be a set of elements of the symmetric group Sn.
It is not always true that every element in the group generated by S
can be written as a word in S of length bounded by a polynomial in
n. (Take S to be a singleton whose element has maximum possible
order in Sn.)
Problem: If the group generated by S contains a fixed-point-free
element, can we always find one which is a word of polynomially bounded length?
In connection with optimality of block designs, statisticians are interested in various functions of the Laplacian eigenvalues of a graph. If the graph is connected, then 0 is an eigenvalue with multiplicity 1; the other eigenvalues are called non-trivial, and are strictly positive. The most interesting are:
The geometric mean is determined by the Tutte polynomial of the graph -- it is essentially the number of spanning trees. Problem: Is it true that the other two are not determined by the Tutte polynomial, i.e. they may take different values for graphs with the same Tutte polynomial?
Solution: This is indeed true. Emil Vaughan pointed out to me that any tree on n vertices has Tutte polynomial xn, whereas trees certainly differ on the other criteria (the star being optimal).
In the reverse direction, the two strongly regular graphs on 16 points (the line graph of K4,4 and the Shrikhande graph) have the same Laplace eigenvalues (and so agree on all eigenvalue-based optimality criteria) but different Tutte polynomials (the first has 576 proper 4-colourings, the second 240).
The following problem in design theory comes (indirectly) from automata theory.
Let m be an integer greater than 3. Does there exist a t-(2m,m,λ) design, for some t>1 and some λ>0, with the properties
The Hadamard conjecture would imply that the answer is "yes" for all m>3; but perhaps there is an easier construction, since t and λ are not specified.
This elegant idea, and the first question, are due to Bill Kantor, in J. Algebraic Combinatorics 28 (2008), 351-363.
A family Gn of finite permutation groups is universal if every finite group is isomorphic to some two-point stabiliser of a group in the family. The motivating example: the fact that
every finite group is the automorphism group of a finite graph(Frucht's Theorem) can be expressed as saying that the family of semidirect products Xn:Sn is universal, where Sn is the symmetric group of degree n and Xn the exterior square of its permutation module over the field of two elements.
A permutation group is QI if the augmentation submodule of its permutation module over the rationals (the set of vectors with coordinate sum zero) is irreducible.
If G is not QI, then there exist vectors v and w in the permutation module such that
Find an example of a permuation group for which this is the case but there is no pair of vectors satisfying these conditions and also
Remarkably, no such group is currently known.
This is Bulgarian solitaire; it is well-known, though I have only just learned about it. You may want to have fun playing with it before looking up references.
A library has n books, stacked up in piles, so there are p(n) possibilities for the sizes of the piles (the integer partition function). Every day, the librarian comes in and picks up the top book from each pile, making a new pile from these books. This defines a map on the set of integer partitions. Now many questions can be asked, such as
Donald Preece and I have failed to solve the following problem.
Let p be an odd prime, and k an integer at least 3. A k-AP decomposition mod p is an arithmetic progression a1, . . . ak consisting of integers not congruent to 0 or 1 mod p such that the group of units of Zp is the direct product by the cyclic groups generated by the terms of the progression.
There are many examples of 3-AP decompositions, but we found no 4-AP decompositions; none exist for primes less than 20000.
Problem: Do k-AP decompositions exist for k>3?
(Note: we assume that each cyclic factor has order greater than 1. Without this assumption, the AP [3528,1148,2381,1] mod 3613 is an example.)
A group G is a B-group if every primitive permutation group containing the regular representation of G is doubly transitive. There are many finite B-groups (including cyclic groups of composite order), but no countably infinite B-groups are known.
The power graph of a group is the undirected graph whose vertex set is the group, two elements being adjacent if one is a power of the other.
Two finite abelian groups with isomorphic power graphs must be isomorphic, but this is not true for arbitrary finite groups.
Conjecture: Two finite groups with isomorphic power graphs have the same number of elements of each order.
This problem has been solved in the affirmative. A stronger statement holds. If the power graphs are isomorphic, then the directed power graphs (with a directed edge from x to y if y is a power of x) are also isomorphic. The proof will appear in J. Group Theory, doi: 10.1515/JGT.2010.023
This problem is due to Josephine Kusuma.
It is well known that the strength (as an orthogonal array) of a linear code over a field is one less than the minimum Hamming weight of the dual code. Josephine showed that this is true over arbitrary commutative rings with identity.
Problem: Let C be a linear code over Z4, and let C' be its Gray map image. Is it true that the strength of C' is one less than the minimum Lee weight of the dual of C? (Josephine also showed that this holds with "is at most" replacing "is".)
(The Gray map from Z4 to Z22 is defined coordinatewise, and maps 0 to 00, 1 to 01, 2 to 11, and 3 to 10. The Lee distance on Z4 is given by dL(x,y)=min(x-y,y-x). The Gray map is an isometry from the Lee metric on Z4n to the Hamming metric on Z22n.)
Given n, what is the smallest number k such that any partial Latin square of order n can be broken into k pieces, each of which can be completed to a Latin square?
It is known that, for any n>1, we have k=2, 3 or 4; which value is correct?
See W. E. Opencomb, Discrete Math. 50 (1984), 71-97.
Which total orderings of a finite vector space have the property that the unique order-preserving bijection between two subspaces of the same dimension is linear?
The lexicographic ordering of GF(q)n has this property (if the field is ordered arbitrarily). There are other examples: how many?
Which finite groups G have the property that the number of isomorphisms between pairs of subgroups of G is equal to the number of endomorphisms of G?
Every abelian group has this property; no non-abelian group is known to do so.
Suppose that k is a proper divisor of n. Let S consist of all those integers between 2 and n–1 inclusive which are either a multiple of k, or at least n/k (or both). Let q(n) denote the minimum of |S|/n, over all divisors of n. If n is prime we set q(n)=n by default.)
Problem: Is it true that the lim inf of q(n), as n→∞, is 3/4?
Solution: This is an easy problem; the answer is "yes". For, if k≥4, then there are at least about (3/4)n numbers greater than n/k; for k=3, there are about (2/3)n numbers greater than n/3, and another about n/9 multiples of 3 smaller than n/3; and for k=2, there are about (1/2)n numbers greater than n/2, and another about n/4 multiples of 2 smaller than n/2.
A graph X is a hull if, for any two non-adjacent vertices v and w, there is an endomorphism of X (a homomorphism from X to itself) which maps v and w to the same place.
It is known that any countably infinite graph with infinite clique size is a hull.
Problem: Let X be a countably infinite hull with finite clique size ω(X). Is it true that χ(X)=ω(X) (where χ(X) is the chromatic number of X)?
Solution by Nick Gravin: Take any finite subgraph Y. If it is not a complete graph, we can collapse two of its vertices by an endomorphism of X. If the image is not complete, we can collapse two more. We end with a homomorphism from Y to a complete graph, so the chromatic number of Y is at most ω(X). Since this holds for all finite subgraphs, a compactness argument shows that χ(X)≤ω(X), and so equality holds.
(An update of Problem 85.) A magma (a set with a binary operation) is power-associative if the value of a power an is independent of the bracketing used to calculate it. The directed power graph of a power-associative magma is the digraph whose vertices are the elements of the magma, an edge from a to b if b is a power of a; the undirected power graph has an undirected edge connecting a and b if one is a power of the other.
It is known that if two groups have isomorphic undirected power graphs, then they have isomorphic directed power graphs. Does this hold for wider classes of power-associative magmas? (In particular, I conjecture that it holds for Moufang loops.)
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.
Sam Tarzi has asked whether an analogous result holds for homomorphisms and monoids. Let T have the property that all its countable models are hom-equivalent (that is, there exist homomorphisms in both directions between any two). What property do the endomorphism monoids of the models have? And does this monoid property imply that all countable models are hom-equivalent?
The theory of graphs in which every finite set of vertices has a common neighbour has the property that all its countable models are hom-equivalent.
This question is due to Sam Tarzi.
The countable random graph is characterised by the property that, given any two finite sets U and V of vertices, there is a vertex z joined to everything in U and nothing in V.
Does there exist a construction of the random graph in which the vertices and edges are computable but the witness z is not bounded by any provably computable function?
Presumably this would be a graph whose isomorphism to R would be unprovable in Peano arithmetic.
Consider a class of discrete minimization problems. Suppose that the cost of a solution is equal to the amount by which the objective function exceeds its true minimum value, and that the cost of computation is ε times the number of Turing machine steps reqired. What is the solution that minimizes the sum of these two costs? In particular, how does it depend on ε?
This problem was considered by Sharad Sane and me over 20 years ago: we failed to solve it. Sharad raised it again at the recent combinatorics conference in Cochin. It is connected with the Erdős–Lovász problem about maximal cliques of r-sets.
Given a 2-(v, k, 1) design (that is, a collection of k-subsets of a v-set with the property that any two points lie in exactly one of the subsets), the point set is covered by the r=(v-1)/(k-1) passing through a given point. Show that, if the design is not a projective plane (that is, if r>k), then the point set can be covered by a set of r blocks not of this form.
The assertion is easy to prove for k≤3.
This question was inspired by one of Stanislav Shkalin.
Anatoly Vershik and I, in Ann. Pure Appl. Logic 143 (2006), 70-78, gave a "random" construction of isometries of the Urysohn space such that every orbit is dense. The closure A of the group generated by such an isometry is abelian and transitive, and so gives the Urysohn space an abelian group structure.
Problem: Can we make the choice such that A has no non-trivial proper closed subgroup?
This question is due to Brendan McKay.
The rank of a function is the size of its image. A transformation monoid is synchronizing if it contains an element of rank 1.
Suppose that k transformations of {1,...,n} are chosen at random.
Let H be a subgroup of the finite group G. Say that the pair (G,H) is good if G can be generated by a set of representatives of the right cosets of H in G.
The power graph of a group G has as vertices the group elements, with two vertices adjacent whenever one is a power of the other.
It is known that the power graph of any group has clique number at most countably infinite. Is the same true for the chromatic number?
A submonoid of the full transformation monoid Tn on the set {1,...,n} is synchronizing if it contains a transformation whose image has size 1.
Is it true that two random transformations generate a synchronizing monoid with probability 1-o(1)?
Which graphs on n vertices have the property that they have at most i different induced subgraphs on i vertices, for some i<n/2 (where n is the number of vertices)?
To avoid uninteresting cases, assume that the graph is connected and not bipartite, and so is its complement. For i=2, every graph (except complete and null) has this property, and for i=3 every triangle-free graph and the complement of such; what about larger i?
Footnote: I didn't make the conditions strong enough. The graph should be vertex-transitive and edge-transitive.
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.
Characterise the primes p which have the property that there exists an element c of the multiplicative group of Z/(p) with the property that {c,c−1,−1} generates a proper subgroup of the multiplicative group.
Primes congruent to 1 (mod 4) have this property since −1 is a square and there are two consecutive squares. Also primes congruent to 1 (mod 3) have the property: take c to be a primitive 6th root of unity. There are others: the remaining primes less than 1000 with this property are 131, 191, 239, 251, 311, 419, 431 and 491.
This problem arose in my work with João Araújo on regular semigroups.
This is a conjecture of João Araújo.
Let G be a primitive permutation group on the finite set X, and let f be a map from X to itself whose kernel (the partition of X given by inverse images of points in the image) is non-uniform (has parts of different sizes).
Prove (or disprove) that the semigroup ⟨G,f⟩ contains a constant function.
This is a problem of Gregory Cherlin, slightly modified.
Is it true that any highly transitive permutation group G of countable degree which contains no finitary permutations has a subgroup H whose closure (in the topology of pointwise convergence) is the automorphism group of the random graph?
Let n be a positive integer, and c a vector in Rn whose components are linearly independent over Q. Is it true that any line with direction vector c passes arbitrarily close to a point with integer coordinates?
This is true for n = 2, by the simplest result about approximating irrationals by rationals. Maybe it is too much to ask for it to hold in general; if so, I'd like a specific example and a specific counterexample.
Solution: This is the multidimensional version of a theorem of Kronecker; it is proved in chapter 23 of Hardy and Wright.
Problem 19 asked:
Let p1 be a prime number. For every n, let pn+1 be the smallest prime divisor of p1...pn+1.John Bray has done some substantial computation on this problem, which was originally suggested to me by Steve Donkin. John has not found any prime answering the second part (that is, it appears that 3 always occurs), but has observed empirically that the number of primes p1 for which none of p1, ..., pn is equal to 3 falls off by a factor greater than 3 when n increases by 1 (for n > 4).
- Is it true that, for every n, there is a prime p1 for which none of the first n terms of the sequence is equal to 3?
- Is there a prime p1 for which no term of the sequence is equal to 3?
Problem: Explain this!
Let G be a primitive permutation group of degree n, generated by a set S of permutations. Let x and y be distinct points of the domain. Form the directed graph D whose edges are all images of (x,y) under all words of length n−1 in elements of S.
Problem Is D necessarily strongly connected?
The cyclic group of prime order shows that the bound n−1 would be best possible.
Peter J. Cameron
p.j.cameron(AT)qmul.ac.uk
31 August 2013