In search of a counterexample to the Lovász conjecture

It is a celebrated result of John Dixon, (The probability of generating the symmetric group, (subscription) Math. Z. 110 (1969), 199–205.) that if one choose two random permutations in the symmetric group , uniformly (i.e. each with probability ), and independently, the probability that the two permutations generate the whole group tends to as . It is clear that this probability will never be greater than , since there is a probability that the two permutations will both be even, in which case you could only generate, at most, the alternating group. Interestingly enough, Dixon’s paper covers this possibility, and he actually shows that the probability that two permutations generate the alternating group tends to as .

Equivalently, if two random elements of the alternating group are chosen uniformly and randomly, the probability that they generate the group tends to as . This leads me to my question — what is the probability that the -regular Cayley graph with generators is not Hamiltonian, as ?

Showing that this probability is bounded away from would provide a counterexample for a notorious problem about vertex-transitive graphs. So we might expect that this is hard. But is it even possible that it is true, or is there some obvious reason that such graphs will tend to be Hamiltonian?

Another approach in the same spirit would be computational rather than asymptotic. Suppose we look at thousands of random Cayley graphs on the alternating groups and , for example. It is straightforward to check that they are connected. Is it within reach for a cleverly designed algorithm on modern computers to conclusively rule out Hamiltonicity for a -regular graph on or vertices? I would also be happy with a computer-aided proof that the conjecture is false.

Historical note: It is called the Lovász conjecture, even though he just asked the question (and perhaps conjectured the other way). I am under the impression that some prominent people in this field have felt that the answer should be no. In particular Babai does not believe it.

Advertisement