Computational topology for configuration spaces of hard disks

Here is a nice review by Randy Kamein of some recent work with Carlsson, Gorham, and Mason at the Journal Club for Condensed Matter Physics.



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 S_n, uniformly (i.e. each with probability 1 / n!), and independently, the probability that the two permutations generate the whole group tends to 3/4 as n \to \infty. It is clear that this probability will never be greater than 3/4, since there is a 1/4 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 1/4 as n \to \infty.

Equivalently, if two random elements x, y of the alternating group A_n are chosen uniformly and randomly, the probability that they generate the group tends to 1 as n \to \infty. This leads me to my question — what is the probability that the 4-regular Cayley graph with generators x, y , x^{-1}, y^{-1} is not Hamiltonian, as n \to \infty?

Showing that this probability is bounded away from 0 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 A_5 and A_6, 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 4-regular graph on 60 or 360 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.