Category Archives: open problems

unsolved mathematical problems

Endomorphism monoids of graphs

Posted on 25/04/2013 by

A monoid is, for me, a set of mappings on a finite domain which is closed under composition and contains the identity mapping. The composition is, of course, associative. Thus, it is “a group without the inverses”. A homomorphism from … Continue reading →

Posted in exposition, open problems | Tagged , , , | Leave a comment

Random synchronization

Posted on 24/04/2013 by

Mikhail Berlinkov posted a paper on the arXiv this week proving that two random transformations of an n-set generate a synchronizing semigroup with probability 1-o(1/n) for large n. His approach was quite different from the one I’d been taking, using … Continue reading →

Posted in mathematics, open problems | Tagged , , | Leave a comment

South-eastern

Posted on 08/03/2013 by

The South-Eastern International Conference on Combinatorics, Graph Theory and Computing has been going for 44 years. I am not sure of its early history. For some time it alternated between Boca Raton (Florida) and Baton Rouge (Louisiana), but now it … Continue reading →

Posted in events, open problems | Tagged , , , , , , , , , , | 2 Comments

Primitivity

Posted on 27/02/2013 by

The first mathematics book that I read really seriously was Helmut Wielandt’s Finite Permutation Groups. So I have known the definition of a primitive permutation group for more than forty years. But there is still more to learn. My recent … Continue reading →

Posted in exposition, open problems | Tagged , , , | Leave a comment

A thrifty algorithm

Posted on 20/01/2013 by

Two important classical parameters of a permutation group G of degree n are the base size, the smallest size of a collection of points whose pointwise stabiliser is the identity; and the minimal degree, the smallest number of points moved … Continue reading →

Posted in exposition, open problems | Tagged , , , , , | 4 Comments

Primitive graphs

Posted on 11/01/2013 by

A primitive graph is one whose automorphism group acts primitively on the vertices: that is, the group is transitive on the vertices, and there is no non-trivial equivalence relation which it preserves. This post is not about why primitive graphs … Continue reading →

Posted in open problems | Tagged , , | Leave a comment

A permutation group challenge, 3

Posted on 02/01/2013 by

“Then I will do it myself”, said the little red hen. And she did. Since nobody took up the challenge, I had to do it myself. Let λ be a partition of n. We say that a permutation group G … Continue reading →

Posted in open problems | Tagged , , | Leave a comment

A permutation group challenge, 2

Posted on 26/12/2012 by

The result in the preceding post can be formulated as follows: A permutation group of degree n = 2k which is transitive on partitions of shape (k,k) but not on ordered partitions of this shape, has a fixed point and is (k−1)-homogeneous … Continue reading →

Posted in open problems | Tagged , , | 1 Comment

A permutation group challenge

Posted on 19/12/2012 by

Long ago, in the distant past before the Classification of Finite Simple Groups, Peter Neumann, Jan Saxl and I investigated the class of permutation groups acting on sets of even cardinality n = 2k, with the following interchange property: Any subset of … Continue reading →

Posted in exposition, open problems | Tagged , , , | 1 Comment

A prime problem

Posted on 05/10/2012 by

Euclid’s proof that the set of primes is infinite is well known. Given primes p1, … pk, let N = p1…pk+1. Then no prime factor of N is in the list p1, … pk. Some years ago, Steve Donkin set a challenge … Continue reading →

Posted in open problems | Tagged , | 2 Comments