Babai's motion conjecture for primitive distance-regular graphs

About 8 years old · traced to

Let d≥3d\geq 3, and let XX be a primitive distance-regular graph of diameter dd on nn vertices. Write motion⁡(X)\operatorname{motion}(X) for the minimum number of vertices moved by a nonidentity automorphism of XX.

Babai's motion conjecture. There exists an α>0\alpha>0 such that either

motion⁡(X)≥αn,\operatorname{motion}(X)\geq \alpha n,

or XX is a Hamming graph, or a Johnson graph.

This is the specialization of Babai's coherent-configuration conjecture to primitive distance-regular graphs. The paper discusses partial results, including the rank-33 and rank-44 cases, but the general statement remains open.

References

Primary source

Bohdan Kivva, “A characterization of Johnson and Hamming graphs and proof of Babai's conjecture”, arXiv:1912.11427 (2019).

Additional references

3 papers in this index state this conjecture (2018–2019). The statement above is taken from the most recent of them; the others are arXiv:1912.10571, arXiv:1802.06959.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.