5
$\begingroup$

Fix any $k \geq 5$.

Does there exist a growing sequence of simple connected REGULAR graphs, each of girth $k$, where the number of vertices $n$ goes to infinity and where the diameter of each graph is uniformly bounded in $n$?

$\endgroup$
5
  • 1
    $\begingroup$ Do the Murty graphs help? I don't know their diameter. $\endgroup$ Jun 11 '20 at 16:41
  • $\begingroup$ I assume you mean Moore graph ? The problem is that there are finitely many Moore graphs. The idea here would be basically to find an explicit infinite sequence of regular graphs that are "near-Moore" with girth $k \geq 5$. $\endgroup$ Jun 12 '20 at 4:14
  • 1
    $\begingroup$ I mean the graphs in Section 3 of core.ac.uk/download/pdf/82145602.pdf, and perhaps those in Section 4. $\endgroup$ Jun 12 '20 at 9:03
  • $\begingroup$ This is really interesting, although the diameter is unclear. It doesn't look friendly to program either. $\endgroup$ Jun 12 '20 at 17:09
  • 1
    $\begingroup$ By digging deeper, I found an example on page 2 here : arxiv.org/pdf/1501.02448.pdf (girth 8, diameter 4) $\endgroup$ Jun 12 '20 at 18:07
3
+100
$\begingroup$

Sure: You can use generalized polygons. For instance, take incidence graphs ${\mathcal G}_q$ of the finite projective planes $P(q)$ of the finite fields $F_q$ of order $q$ (say, $q$ is prime, then the field is ${\mathbb Z}/q{\mathbb Z}$). Such incidence graph is the bipartite graph whose vertices are lines and planes in the 3-dimensional vector space $V=F_q^3$. Two vertices are connected by an edge precisely when the line is contained in the plane. Every such graph has valence $q+1$, diameter 3 and girth 6. The graphs ${\mathcal G}_q$ have many interesting properties, for instance, their symmetry group acts transitively on ${\mathcal G}_q$: The finite linear group $GL(3, F_q)$ acts transitively on the sets of lines and of planes but one can also switch lines and planes.

Let's prove that each ${\mathcal G}_q$ has diameter 3: One can think of this as an exercise either in linear algebra or in projective geometry. Via linear algebra: If, say, $P_1, P_2$ are distinct planes in $V$, their intersection in $V$ is a line, hence, the graph-distance $d(P_1,P_2)$ from $P_1$ to $P_2$ is 2. Similarly, if $L_1, L_2$ are distinct lines in $V$, their span is a plane, hence, again, $d(L_1, L_2)=2$. Lastly, if $P$ is a plane and $L$ is a line not in that plane, take a line $L'\subset P$. Then $d(P,L')=1, d(L,L')=2$, thus, $d(P,L)=3$ (it cannot be less than $3$).

Let's prove that girth is 6: Take three coordinate planes and three coordinate lines in $V=F_q^3$. Together, they form a cycle of length 6 in the incidence graph. (Geometrically, you draw a triangle in the projective plane and consider its set of edges and vertices, you get a hexagon which is the cycle of length 6 I just described.)

It is another linear algebra/projective geometry exercise to prove that ${\mathcal G}_q$ contains no cycles of length 4. (For any two distinct points in a projective plane there is exactly one projective line through these points.)

Edit. Similarly to Alex's answer, generalized polygons (of arbitrarily high but finite cardinality) and of fixed girth $g\ge 5$ (and diameter $d=g/2$) exist only for small values of the diameter: $d=3, 4, 6, 8$.

$\endgroup$
5
  • 1
    $\begingroup$ This is exactly the type of construction I need, but I'm not able to fully comprehend what $P(q)$ and $V$ even mean/represent. Most of all, I need an algorithm that can generate these graphs. $\endgroup$ Jun 19 '20 at 0:40
  • 1
    $\begingroup$ @FrédéricOuimet: You do not need to know what $P(q)$ is if you do not know projective geometry. I described the graph ${\mathcal G}_q$ in terms of linear algebra over finite field. Did you ever take a linear algebra class? You probably used real numbers but it works the same way over any field. Concretely, $V=F_q^3$ is what I said, the set of triples $(x,y,z)$ of elements of the finite field. These triples are usually called vectors in linear algebra. You can add them, multiply by scalars (from the same finite field, of course). This is not at all different from ${\mathbb R}^3$. $\endgroup$ Jun 19 '20 at 2:38
  • 1
    $\begingroup$ @FrédéricOuimet: I am absolutely sure that there are packages for doing linear algebra over finite fields. $\endgroup$ Jun 19 '20 at 2:41
  • 1
    $\begingroup$ @FrédéricOuimet: Here is a link to some random paper found by my search engine, which computes incidence matrices of finite projective planes for sufficiently small $q$. $\endgroup$ Jun 19 '20 at 2:52
  • $\begingroup$ Thanks. After rereading the 2nd paragraph, I now understand your proof visually. $\endgroup$ Jun 19 '20 at 3:24
2
$\begingroup$

$\newcommand{\diam}{\operatorname{diam}}$ The answer is positive for girth $g\in \{5,6,7,8,12\}$.

To show that the graphs from the references are examples, we use the following arguments.

Below $d\ge 2$, $g\ge 3$ are natural numbers, and $G$ is a $d$-regular graph $G$ of girth $g$, order $n$, and diameter $\diam G$. Put $g’=\lfloor (g-1)/2\rfloor$. Let $v$ be any vertex $v$ of $G$ let $B(u)$ be the set of vertices $u$ of $G$ such that the distance from $v$ to $u$ is at most $g’$. $$|B(u)|=1+d+d(d-1)+\dots +d(d-1)^{g’-1}=1+\frac {d(d^{g’}-1)}{d-1}.$$ Denote the latter value by $b(d,g)$.

Lemma. $\left\lfloor 1+\frac{\diam G}{2g’+1}\right\rfloor b(d,g)\le n$.

Proof. Let $m=\diam G$. Pick vertices $v_0$ and $v_m$ of the graph such that the distance between them equals $m$ and let $v_0-v_1-\dots-v_m$ be a shortest path from $v_0$ to $v_m$. Then sets $B(v_0), B(v_{2g’+1}), B(v_{4g’+2}), \dots$ are mutually disjoint, otherwise we can make a shortcut in the path. It follows the lemma’s claim. $\square$

A $(d, g)$-graph is a $d$-regular graph of girth $g$. Erdős and Sachs [ES] proved the existence of $(d,g)$-graphs for all $d\ge 2$ and $g\ge 3$. Let $n(d,g)$ be the minimum order of $(d, g)$-graph. Lemma follows if $n(d,g)\le 2(d,g)-1$ then there exists a $(d,g)$-graph of diameter at most $2g’\le g$.

By Theorem 16 from [EJ], when $5\le g\le 8$ and $d$ is an odd prime power then $n(d,g)\le m(d,g)$. Also I expect a lot of constructions of $d$-regular graphs of girth $g$ and order at most $2b(d,g)-1$ is listed in [EJ], Section 4.1.2 (for girth $5$) and Section 4.1.3 (for girths $6$, $8$, and $12$). For instance, Construction XX by Gács and Héger shows that $n(d,12)\le m(d,12)$, when $d$ is a prime power. See also Section 4.1.4.

In [AFLN] and [AA-PBL2] are listed results on $n(d,5)\le 2b(d,5)-1$, see also [AA-PBL2, Proposition 2]. In [AA-PBL] are presented similar results for $g=7$ (Theorems 3.1 and 3.2) and $g=8$ (Theorems 3.3, 3.4, possibly, 3.5, and the references after it). Maybe some references from Introduction of [AA-PBL2] and Section 3.5.2 of [MS] can be helpful.

References

[AFLN] M. Abreu, M. Funk M., D. Labbate, V. Napolitano,A family of regular graphs of girth 5, Discrete Mathematics 308 (2008) 1810–1815.

[AA-PBL] M. Abreu, G. Araujo-Pardo, C. Balbuena, D. Labbate, A formulation of a $(q+1,8)$-cage.

[AA-PBL2] M. Abreu, G. Araujo-Pardo, C. Balbuena, D. Labbate, Families of small regular graphs of girth 5, Discrete Mathematics 312 (2012) 2832–2842.

[EJ] Geoffrey Exoo, Robert Jajcay, Dynamic Cage Survey, The electronic jornal of combinatorics, dynamic survey 16.

[ES] P. Erdős, H. Sachs, Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Uni. Halle (Math. Nat.), 12 (1963) 251–257.

[MS] Mirka Miller, Jozef Širáň, Moore graphs and beyond: A survey of the degree/diameter problem, The electronic jornal of combinatorics 20:2, dynamic survey 14v2.

$\endgroup$
3
  • 1
    $\begingroup$ +1, nice ${}{}$ $\endgroup$ Jun 18 '20 at 14:24
  • $\begingroup$ Do you know an algorithm that generates arbitrarily many of these graphs with programming? $\endgroup$ Jun 19 '20 at 2:23
  • $\begingroup$ @FrédéricOuimet I didn’t think about that. Maybe some proposed constructions from [EJ] (for instance, Construction X) can be rather easily programmed. $\endgroup$ Jun 19 '20 at 2:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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