Progress on the GFR Problem

Mark E. Watkins
Syracuse University

Marston Conder
University of Auckland

John Kevin Doyle
Benedictine University

Thomas Tucker
Colgate University

PDF

Minisymposium: APPLICATIONS OF GROUPS IN GRAPH THEORY

Content: We describe our progress during the past year on the so-called ``GFR problem.'' A {\em GFR}, or {\em graphical Frobenius representation}, is a graph whose automorphism group acts as a Frobenius permutation group, that is, it acts vertex-transitively but not regularly and only the identity automorphism fixes more than one vertex. We ask, which abstract groups can be isomorphic to the automorphism group of a GFR? Group theoretical conditions are surprisingly not less, but more restrictive than in the GRR problem (solved over the period between 1958 and 1982) which succeeded in characterizing the finitely generated abstract groups $G$ admitting a graphical regular representation (GRR), namely a graph $\Gamma$ whose automorphism group is isomorphic to $G$ and acts as a regular permutation group on the vertex set of $\Gamma$. In both problems, the graph $\Gamma$ under consideration must be a Cayley graph: of the given group $G$ in the GRR problem, while of the Frobenius kernel of $G$ in the GFR problem. Graphical requirements for ``GFR-hood'' are also more restrictive. For example, while almost all Cayley graphs of an odd-order nilpotent group are GRRs without categorically forbidden valences (Babai \& Godsil, 1982), we now know that there exists no $p$-valent GFR if $p$ is a prime such that $2$ is a primitive element of $\mathbb{Z}_p$. No group of odd order $<1029$ admits a GFR, but we have found this bound to be sharp by constructing an $18$-valent GFR on 343 vertices and vertex-stabilizers of order 3. We have also constructed infinite GFRs, both $1$-ended and infinitely-ended, and of every even valence $\geq6$.

Back to all abstracts