8
$\begingroup$

Consider the infinite 3-regular tree. Pick a vertex $C$, the "center". For any integer $L\ge 1$ consider the closed ball, in the graph distance, of radius $L$ around $C$. Let $T_L$ be the induced subgraph on the set of vertices given by this ball. The finite tree $T_L$ rooted at $C$ has $L+1$ layers or generations. It has $3\times 2^L-2$ vertices and they all have degree $3$ except the $3\times 2^{L-1}$ leaves in the top layer. My question is:

Q1: Is it possible to add $3\times 2^{L-1}$ edges between the leaves in order to get a graph $G_L$ with spanning tree $T_L$ such that $G_L$ is vertex-transitive? (Edit: now solved in the negative, see below)

For $L=1$ and $L=2$, I can do that which gives me the tetrahedron and the Petersen graph respectively. Does this kind of problem arise in geometric group theory and the study of locally finite graphs?

Also, when looking at OEIS A032355, the relevant numbers of vertex-transitive graphs seems abnormally low. Even more surprising, they immediately precede a big surge (look at the values for $n=2,5,11,23,47,95$ in that list). Is there a known explanation for this phenomenon?

Edit in view of the awesome answers by Aaron and Gordon: I still have to digest the theory around Moore graphs and bound. My motivation for this question comes from statistical mechanics on the widest possible class of lattices. In particular it has to do with the question of defining "periodic boundary conditions" for given finite subsets. In this regard, an equally useful (for me) weakening of my question is as follows:

Q2: Is there a constant $c\in (0,1)$ independent of $L$ such that one can build $G_L$ as above to make the size of the orbit of the center $C$ no smaller than $c\times(3\times 2^{L}-2)$?

In other words I want to make this orbit of macroscopic size. The orbit is of course wih respect to the action of the automorphism group of $G_L$. A quick remark is that if one adds no edges, i.e., one takes $T_L$ itself, this orbit is the singleton $\{C\}$ and the automorphims group is a wreath product $\mathbb{Z}_2\wr\cdots\wr\mathbb{Z}_2\wr\mathbb{Z}_3$ with $\mathbb{Z}_2$ appearing $L-1$ times.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Usually people start a new question rather than change an existing one. It is a wild guess, but I wouldn't be surprised if the center $C$ has to be a fixed point. It shouldn't be that hard to verify if this is the case with $22$ points. We know that a cubic graph on $3\times 2^L-2$ points has short cycles. $C$ has the property of being far from the points of such a cycle. There is certainly a literature on cubic graphs with large girth $g$ including those with as few vertices as possible given $g$. Locally such a thing looks like a $3$-ary tree. I'd look there. $\endgroup$
    – Aaron Meyerowitz
    Commented Aug 21, 2017 at 4:51
  • $\begingroup$ @Aaron: I didn't know there was a rule about not changing an existing questions. I actually started a new more general question in mathoverflow.net/questions/279166/… Thank you for your new remarks about the center ability to move the center. $\endgroup$
    – Abdelmalek Abdesselam
    Commented Aug 21, 2017 at 14:45

2 Answers 2

Reset to default
9
$\begingroup$

These graphs do not exist except for the cases you mention.

Your conditions imply that your graph has girth $2L+1$ and that it meets the Moore bound for the minimum number of vertices in a graph of valency 3 and girth $2L+1$.

Such graphs are known to exist only for $L=1, 2$.

For example, when $L=3$, you would need a $22$-vertex cubic graph, but the smallest cubic graph of girth $7$ has $24$ vertices (and it gets worse from there onwards).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Hi Gordon. I suspected you might come out with a spot on answer. Friday night here, but I will have a careful look at your answer tomorrow. BTW any thoughts one the surges? $\endgroup$
    – Abdelmalek Abdesselam
    Commented Aug 19, 2017 at 0:14
  • 2
    $\begingroup$ @Malek (Hi Malek) There are simply more transitive groups when the degree has a lot of small prime divisors. Other than groups whose degree is a power of $2$, the next most "productive" degrees are those whose degree is $3$ times a power of $2$. Of course, the automorphism group of a graph can contain many transitive subgroups, so the connection is not absolutely forced. But in practice, give me a new transitive group and I'll find some new transitive graphs. $\endgroup$
    – Gordon Royle
    Commented Aug 19, 2017 at 1:27
  • $\begingroup$ I see. So the surges are not that surprising. I just amended my question. $\endgroup$
    – Abdelmalek Abdesselam
    Commented Aug 19, 2017 at 17:03
7
$\begingroup$

The two you give are the only cubic examples. There are various ways to weaken your requirements which give very small families.

One is Moore Graphs which take a $k$-ary tree of diameter $L$ and connect the leaves so that the girth is $2L+1.$ Other than odd cycles $k=2$ and complete graphs (diameter $1$) they must have diameter $2$. There are uniques examples for $k=3,7$ which turn out to be distance transitive. The only other open case is $k=57$ which would be distance regular but could not be distance transitive.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Many thanks Aaron. I will have a careful look at your answer tomorrow. $\endgroup$
    – Abdelmalek Abdesselam
    Commented Aug 19, 2017 at 0:13
  • 3
    $\begingroup$ +1 for the precision and right emphasis in "for $k=3,7$ which turn out to be distance transitive". To inexperienced readers: it is indeed somewhat 'special', justifying the use of the phrase 'turn out to be' that the unique examples for $k=3,7$ are distance transitive, in the following sense: for general reasons (see e.g. Godsil-Royle, Algebraic Graph Theory, 1st ed, Theorem 5.8.2, every Moore graph must be distance regular, for general reasons, yet 'distance regular' does not abstractly imply 'distance transitive', as first proved in the 1960s by Adel'son-Vel'skii et al $\endgroup$
    – Peter Heinig
    Commented Aug 19, 2017 at 12:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .