3
$\begingroup$

For $d \geq 3$ (degree) and $r \geq 3$ (radius), say that a $d$-regular (finite, simple, non-oriented) graph $G$ is $r$-almost-tree if it contains no cycle of length $\leq 2 r$: in other words, we want our graph to look locally like a $d$-regular tree, in the sense that its restriction to any ball of radius $r$ always has exactly the (local) structure of a $d$-regular tree. Denote by $N(d, r)$ the minimum possible of vertices for a $r$-almost-tree $d$-regular graph. What can one tell about $N(d, r)$?

A first observation is that $N(d, r)$ is always finite. [Proof: For $n$ large, consider $d$ random involutions without fixed point of $\mathfrak{S}_{2 n}$; then the Cayley graph of the subgroup that they generate will be $r$-almost-tree with a probability tending to $1$ as $n \to \infty$]. But what about sharp upper bounds? In particular, a trivial lower bound on $N(d, r)$ is given by the size of a ball of radius $d$ in a tree, i.e. $1 + d + (d - 1) d + \cdots + (d - 1)^{r - 1} d =: N_0(d, r)$. In view of this, two natural questions are the following:

  • In which cases does one have $N(d, r) = N_0(d, r)$? In particular, for fixed $d$, are there intinitely many $r$'s such that $N(d, r) = N_0(d, r)$? (Note: I investigated the case $d = 3$: then $r = 1$ and $r = 2$ fit, but not $r = 3$ nor $r = 4$).
  • For fixed $d$, is the ratio $N(d, r) / N_0(d, r)$ bounded as $r$ tends to infinity?…
$\endgroup$
4
  • 4
    $\begingroup$ The answer to your first question is the Hoffman-Singleton Theorem, and the second question, I believe, is largely open. The best constructions known now has $N(d,r)/N_0(d,r)$ exponential in $r$. $\endgroup$ Nov 18, 2020 at 15:53
  • 1
    $\begingroup$ Just a few more links that may be helpful: en.wikipedia.org/wiki/Degree_diameter_problem en.wikipedia.org/wiki/… combinatorics.org/ojs/index.php/eljc/article/view/DS14 $\endgroup$
    – Louis D
    Nov 18, 2020 at 16:26
  • $\begingroup$ Many thanks @LeechLattice and LouisD for your links :-D And sorry for having asked a question about something which was actually classical: I had done a preliminary research over the web before asking on MO; but, as I am not a specialist of these topics, I guess that I looked at the wrong keywords… :-S $\endgroup$ Nov 18, 2020 at 17:58
  • 3
    $\begingroup$ The keyword you are missing is "girth", which is the lengh of a shortest cycle in a graph. Your quetion asks for graphs with girth greater than $2r$. $\endgroup$
    – David Wood
    Nov 18, 2020 at 21:00

1 Answer 1

5
$\begingroup$

The problem of determining the smallest regular graphs with degree $k$ and girth $g$ is normally known as the cage problem.

It has a large literature which is nicely summarised in the Dynamic Cage Survey in the Electronic Journal of Combinatorics.

https://www.combinatorics.org/ojs/index.php/eljc/article/download/DS16/pdf/

(Apparently this is about to be updated)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.