Description
Véges Geometria szeminárium
Absztrakt:
The motion of a graph is the minimal degree of its full automorphism
group. Babai conjectured that the motion of a primitive distance-regular
graph on n vertices of diameter greater than two, is at least n/C for
some
universal constant C > 0, unless the graph is a Johnson or Hamming
graph. We prove that the motion of a primitive distance-regular graph
of diameter
d ≥ 3 on n vertices is at least n/C(logn)^6
for some universal constant C > 0, unless it is a Johnson, a Hamming
graph.
This improves an earlier result by Kivva who gave a lower bound on
motion of the form
n/c_d, where c_d depends exponentially on d.
The proof uses elementary combinatorial arguments and basic notions and
results
concerning permutation groups.