Leonard Chidiebere Eze, Robert Jajcay

Department of Algebra and Geometry, Faculty of Mathematics, Physics and Informatics, Comenius University, Bratislava, Slovakia

leonard.eze@fmph.uniba.sk, robert.jajcay@fmph.uniba.sk

This paper presents a possible link between Cages and Expander Graphs by introducing three interconnected variants of the Bermond and Bollobás Conjecture, originally formulated in 1981 within the context of the Degree/Diameter Problem. We adapt these conjectures to cages, with the most robust variant posed as follows: Does there exist a constant c such that for every pair of parameters k, g there exists a k-regular graph of girth g and order not exceeding M(k, g) + c?; where M(k, g) denotes the value of the so-called Moore bound for cages. We show that a positive answer to any of the three variants of the Bermond and Bollobás Conjecture for cages considered in our paper would yield for all k ≥ 3 the existence of k-regular expander graphs with Cheeger constant asymptotically bounded below by 1/(k − 1) (expander families); thereby establishing a connection between Cages and Expander Graphs.

Keywords: cages, Moore bound, expander graphs, multipoles, girth, (k, g)-graphs Mathematics Subject Classification : 05C35, 05C40, 05C48

DOI: 10.5614/ejgta.2026.14.1.9

1. Introduction

Cages and expander graphs are two seemingly distinct classes of graphs that have been the focus of research in theoretical computer science and mathematics for the past five decades (see,

Received: 3 August 2025, Revised: 18 January 2026, Accepted: 11 February 2026.

e.g., the surveys [7, 12]). Nevertheless, both classes share common use in building robust, high-performance communication networks, and play a crucial role in a host of other applications, from complexity theory to coding theory.

The Cage Problem is the problem of finding (k,g)-cages, which are the smallest k-regular graphs of girth g, for each \(k \geq 3\) and \(g \geq 3\). The problem has been widely studied since the pioneering works of Erdős and Sachs [6] and of Hoffman and Singleton [10] in the 1960's. It is well-known that for any given pair of integers \(k \geq 3\) and \(g \geq 3\), there exist infinitely many (k,g)-graphs (k-regular graphs of girth g) [6], but the problem of determining the orders of the smallest (k,g)-regular graphs, denoted by n(k,g), is wide open for the majority of parameter pairs (k,g) [7].

The second problem considered in our paper, the Expander Graph Problem, asks for constructions of infinite families of finite regular graphs that are sparse and highly connected (with the precise definition involving either spectral or combinatorial properties of the graphs). Determination of cages (or even devising constructions of small (k,g)-graphs) and constructions of expander graphs are challenging combinatorial and computational problems. Although many individual graphs, such as complete graphs and some (k,g)-cages, are known to have good expansion properties, but constructing explicit infinite families of expander graphs has proven to be a challenge. In this paper, we explore a connection to an expander family from the perspective of the Cage Problem by extending the Bermond-Bollobás Conjecture to cages and assuming positive answers to any of the three variants presented herein.

Margulis [15] first proved the existence of an expander family. An infinite family of k-regular graphs \(\{\Gamma_n\}_{n=1}^\infty\) is said to be an expander family if there exists a positive number c such that \(h(\Gamma_n) > c\), for all \(n \in \mathbb{N}\), where \(h(\Gamma_n)\) is the Cheeger constant of \(\Gamma_n\) defined in Equation 1. The Cheeger constant of a graph measures the connectivity of the graph, and we describe it as follows. Let \(\Gamma\) be a finite graph, and \(\emptyset \neq S \subset V(\Gamma)\). Define \(\sigma(S) = \{\{u,v\} \in E(\Gamma) : u \in S, v \in V(\Gamma) \setminus S\}\). Then, the Cheeger constant \(h(\Gamma)\) of the graph \(\Gamma\) is defined as

\[h(\Gamma) = \min\left\{\frac{|\sigma(S)|}{|S|} : S \subset V, \ 0 < |S| \le \frac{|V|}{2}\right\}. \tag{1}\]

For obvious reasons, we require that our graphs be connected, since the Cheeger constant of a disconnected graph is zero. With this requirement in place, the pursuit of constructing expander families has led to the investigation of various types of graphs, including extremal graphs of given maximal degree and diameter [8], as well as regular graphs with a fixed second largest eigenvalue [18].

The Cage Problem is also related to the well-known problem in Extremal Graph Theory – the \(Degree/Diameter\ Problem\) – in which one asks for maximal orders of graphs of given maximum degree and diameter [16]. A quick comparison of the Cage and Degree/Diameter Problems shows that both problems are related through the so-called Moore bound (see definition below; note that the original Moore bound was stated only for the case of odd girth). For the Degree/Diameter Problem, we denote the order of the largest graphs of maximum degree \(\Delta\) and diameter D by \(n(\Delta, D)\). This order is bounded from above by the Moore bound \(M(\Delta, D)\) expressed as

\[M(\Delta, D) = 1 + \Delta + \Delta(\Delta - 1) + \dots + \Delta(\Delta - 1)^{D-1}.\]

Any ∆-regular graph that achieves this bound must be of girth 2D + 1. Therefore, the Moore bound M(∆, D) is a lower bound on the order of (k, g)-graphs with k = ∆ and g = 2D + 1. Consequently, for k = ∆ and g = 2D + 1, M(∆, D) = M(k, g) ≤ n(k, g), for all k ≥ 3 and g ≥ 3, where M(k, g) denotes the Moore bound for the order of a k-regular graph of girth g. Considering both the odd and even girths g, the order |V (Γ)| of any (k, g)-graph satisfies the following inequalities:

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Graphs that achieve the Moore bound are called Moore graphs. Clearly, all Moore graphs are cages. It is important to note however, that even though there exist graphs whose orders precisely match the Moore bound (and thus the bound is sharp in the usual meaning of the term), beside the very few cases when this happens, the Moore bound M(k, g) is considered a very poor predictor of the order of the (k, g)-cages. Even the best known constructions of small (k, g)-graphs produce graphs whose orders are mutliples (or even powers) of the corresponding Moore bound. In the cases where the order of a k-regular graph Γ of girth g exceeds the Moore bound, we call the difference between its order and the Moore bound its excess e(Γ).

In 1981, Bermond and Bollobás [2] raised the following question:

Is it true that for each integer c > 0 there exist ∆ > 2 and D ≥ 2 such that the order of the largest graph of maximum degree ∆ and diameter D is at most M(∆, D) − c?

More than forty years later, we still do not know the answer to this question. While studying this question (possibly trying to prove a positive answer), Filipovski and Jajcay [8] linked the possibility of a negative answer to the existence of a class of expander graphs called Ramanujan graphs by showing that a negative answer to the question of Bermond and Bollobás would yield for any fixed ∆ and all sufficiently large even D a family of expander graphs called Ramanujan graphs defined in the next paragraph via the use of spectral properties of graphs.

Let Γ be a k-regular graph of order n. It is known that eigenvalues of the adjacency matrix of Γ are of the form λ⁰ ≥ λ¹ ≥ λ² ≥ · · · ≥ λn−¹ with λ⁰ = k and |λⁱ | ≤ k for i = 1, 2, . . . , n − 1. If the absolute value of the second largest eigenvalue of Γ is λ (i.e., λ = max{|λ1|, |λn−1|}), then we say that Γ has a λ-expansion, and we refer to Γ as an (n, k, λ)-graph. An (n, k, λ)-graph Γ is called a Ramanujan graph if λ ≤ 2 √ k − 1 [1, 13]. It is well known that Ramanujan graphs are expander graphs [13]. We also know that it is not difficult to construct small Ramanujan graphs. For example, complete graphs Kk+1 have been shown to be Ramanujan graphs. However, the main challenge is to determine whether there exist infinite families of k-regular Ramanujan graphs for all degrees k. This question has been partly answered for every prime k − 1. In 1988, Lubotzky, Phillips, and Sarnak [13] proved that if k − 1 is a prime, there are infinite families of k-regular Ramanujan graphs. In 1994, Morgenstern [17] proved the existence and explicit constructions of (q + 1)-regular Ramanujan graphs for every prime power q. In a later development, Friedman [9] showed that for every ϵ > 0 almost all k-regular graphs satisfy λ(Γ) ≤ 2 √ k − 1 + ϵ. In 2013,

Marcus, Spielman, and Srivastava [14] showed that bipartite Ramanujan expanders exist for all degrees \(k \geq 3\).

Interestingly, the second largest eigenvalue and the Cheeger constant of a graph are related by the following Cheeger inequality.

Theorem 1.1 ([1]). Let \(\Gamma\) be a k-regular connected graph, then

\[\frac{k-\lambda}{2} \le h(\Gamma) \le \sqrt{2k(k-\lambda)},\tag{2}\]

where \(\lambda\) is the second largest eigenvalue of \(\Gamma\).

In our paper, we study the analogue of the Bermond and Bollobás question in the context of cages. We state the question in three gradually more relaxed forms (with the first, strictest form, being the closest to the original question as stated by Bermond and Bollobás in the context of extremal degree/diameter graphs), and show that a positive answer to even the most relaxed form of the question would yield the existence of infinite families of k-regular graphs the Cheeger constant of which would be asymptotically greater than or equal to \(\frac{1}{k-1}\). This parallels the results of Filipovski and Jajcay in [8], who have, in the context of the Degree/Diameter Problem, only considered the strongest version of the Bermond and Bollobás question, but were able to prove the conditional existence of a specific family of expanders, namely the Ramanujan graphs.

2. Variants of Bermond-Bollobás Conjecture for Cages

A positive answer to the Bermond and Bollobás question in the Degree/Diameter Problem would not necessarily rule out the existence of interesting infinite families of graphs of maximal degree k and increasing diameter d or of families of fixed diameter d>2 and increasing maximum degree k whose orders are meaningfully close to the Moore bound.

For this reason, we pose three related variants of the Bermond and Bollobás question in the case of cages; with the first one being the closest analogue of the original Bermond and Bollobás question as stated in the context of the Degree/Diameter Problem.

• BB1 Does there exist a constant c such that for every pair of parameters (k, g) there exists a (k, g)-graph of order not exceeding M(k, g) + c?
• BB2 Does there exist for every \(k \geq 3\) a constant \(c_k\) such that for every \(g \geq 3\) there exists a (k,g)-graph of order not exceeding \(M(k,g) + c_k\)?
• BB3 Does there exist for every \(k \geq 3\) a constant \(c'_k\) such that there exist infinitely many \(g \geq 3\) with the property that there exists a (k,g)-graph of order not exceeding \(M(k,g) + c'_k\)?

As already observed in the introductory section, the first variant, BB1, is the exact equivalent of the original question posed by Bermond and Bollobás. While a single constant c required in this form may not exist, it may be caused by the fact that increasing the degree may have an impact on the orders of the extremal graphs and push them away from the Moore bound. Thus, it still might

be the case that separate constants exist for all k ≥ 3 (or at least for some k's; even though the existence for some k's and non-existence for other k's feels counterintuitive). Such situation would be captured by a positive answer to BB2. The weakest variant of this series of questions simply asks about the existence of infinite families of k-regular graphs whose orders do not differ from the Moore bound by more than a constant. Even a positive answer to this much weaker version is generally considered unlikely, and there is no evidence toward a result of this kind in the existing literature.

Thus, a positive answer to BB1 would imply a positive answer to BB2 and BB3 while a negative answer to BB1 might still allow for a positive answer to BB2 and BB3. Furthermore, a positive answer to BB2 would imply a positive answer to BB3 while a negative answer to BB2 might still allow for a positive answer to BB3.

Notably, questions BB2 and BB3 could also be stated in the form where one would fix the girth and allow the degree to vary. These kinds of variants would also be interesting, but we chose not to state them explicitly, as we do not address them in this paper. It is known that infinite families of k-regular graphs of girths 6, 8, and 12 of orders exactly equal to the Moore bound exist on generalized polygons of type (q, q) for prime powers q + 1 with k = q + 1 [7]. However, nothing similar is known for odd or larger even girths.

We also wish to point out that in the more specialized case of vertex-transitive cages, the first two variants of this question have been answered in negative, and the excess of vertex-transitive (k, g)-cages can be arbitrarily large. This result is due to Biggs:

Theorem 2.1 ([3]). For each odd integer k ≥ 3, there is an infinite sequence of values of g such that the excess e(Γ) of any vertex-transitive graph Γ of degree k and girth g satisfies e(Γ) > g k .

In [8], the authors show that Biggs' result in [3] holds not only for infinitely many g's, but, in fact, holds for almost all g's, for any fixed k ≥ 4. Specifically, they show that for any given excess e(Γ) and degree k ≥ 4, the set of g's for which nvt(k, g)−M(k, g) < e(Γ), is of asymptotic density 0 (when compared to the set of all girths g ≥ 3), where nvt(k, g) is the order of the smallest vertex-transitive (k, g)-graphs. The main technique used in the paper relies on counting cycles in vertex-transitive graphs whose orders are close to the Moore bound.

In this paper, we consider hypothetical (k, g)-graphs of orders smaller than M(k, g)+ck, where c^k is a positive constant. We prove that for every fixed k ≥ 3 and every c^k there exists a positive constant N(k, ϵ) such that the Cheeger constant of any (k, g)-graph of order less than or equal to M(k, g) + c^k is greater than or equal to N(k, ϵ). This implies that if either of BB1, BB2, or BB3 were true, then for each k ≥ 3 there would exist an expander family of (k, g)-graphs with increasing g.

3. Odd Girth

In what follows, we repeatedly refer to a complete k-regular tree of depth s which is a tree rooted in a vertex of degree k, all the vertices of this tree that are of distance smaller than s from the root are of degree k, and all the leaves are of distance s from the root. The order of this tree is equal to M(k, 2s + 1), and for obvious reasons we shall call it the Moore tree of degree k and depth s, and denote it by Tk,s.

The following two lemmas are of technical nature, and will provide us with the key averaging arguments used later to bound the Cheeger constants. The first of them is an easy consequence of the well-known fact that every vertex u of a (k,g)-graph \(\Gamma\) with odd g=2s+1 is a root of a Moore tree of depth s contained in \(\Gamma\). We denote this Moore tree by \(\mathcal{T}_{k,s}^u\).

Lemma 3.1. Let g = 2s + 1, \(g \ge 3\), and let \(\Gamma\) be a (k, g)-graph. For every vertex \(v \in V(\Gamma)\) and every \(0 \le s' \le s\) there exist exactly M(k, 2s' + 1) vertices \(u \in V(\Gamma)\) such that the Moore tree \(\mathcal{T}^u_{k,s'}\) contains v.

Proof. A vertex \(v \in V(\Gamma)\) is contained in \(\mathcal{T}^u_{k,s'}\), for some \(u \in V(\Gamma)\), if and only if, \(d_{\Gamma}(v,u) \leq s'\). Since these are exactly the vertices contained in \(\mathcal{T}^v_{k,s'}\), there are M(k,2s'+1) vertices \(u \in V(\Gamma)\) with this property, and the result follows.

The above argument yields the following.

Lemma 3.2. Let \(g=2s+1\geq 3\), \(\Gamma\) be a (k,g)-graph, and \(\beta=\frac{M(k,g-2)}{|V(\Gamma)|}\). If \(\emptyset\neq S\subseteq V(\Gamma)\), then there exists a vertex \(u\in V(\Gamma)\) whose Moore tree \(\mathcal{T}^u_{k,s-1}\) contains at least \(\beta|S|\) vertices from S, i.e., \(|V(\mathcal{T}^u_{k,s-1})\cap S|\geq \beta|S|\).

Proof. The proof proceeds via contradiction. Suppose the lemma is not true and for every \(u \in V(\Gamma)\) we have the inequality \(|V(\mathcal{T}^u_{k,s-1}) \cap S| < \beta |S|\). Then,

\[\sum_{u \in V(\Gamma)} |V(\mathcal{T}_{k,s-1}^u) \cap S| < \beta \cdot |V(\Gamma)| \cdot |S|.\]

On the other hand, Lemma 3.1 yields that each vertex \(v \in S\) appears in exactly M(k, g-2) trees \(\mathcal{T}^u_{k,s-1}\), \(u \in V(\Gamma)\). Therefore,

\[\sum_{u \in V(\Gamma)} |V(\mathcal{T}_{k,s-1}^u) \cap S| = |S| \cdot M(k, g-2).\]

Combining the two results yields the inequality

\[|S| \cdot M(k, g-2) < \beta \cdot |V(\Gamma)| \cdot |S|\]

which implies the desired contradiction

\[M(k, g-2) < \frac{M(k, g-2)}{|V(\Gamma)|} \cdot |V(\Gamma)|.\]

Throughout the rest of this section, we will use a generalized concept of a graph that allows semi-edges; edges incident with one vertex only. Such generalized graphs are called multipoles. The degree of a vertex u in a multipole is the number of edges and semi-edges incident to u. Furthermore, the concept of an induced subgraph in a multipole is also slightly different from the usual usage of induced subgraphs of simple graphs. Namely, for a non-empty subset S of vertices

of a finite multipole \(\Gamma\) (which may or may not contain semi-edges), the induced multipole of \(\Gamma\) determined by the subset S, \(\Gamma^M(S)\), is the multipole with vertex set S in which each vertex \(u \in S\) is adjacent to all the vertices \(v \in S\) to which u was adjacent in \(\Gamma\) (the 'usual' induced edges) while u is also incident to a semi-edge for each edge \(\{u,v\}\) of \(\Gamma\) with \(v \notin S\) and u is incident to each semi-edge of \(\Gamma\) incident with u. Thus, unlike the case of an induced subgraph of a graph, all the vertices in an induced multipole \(\Gamma^M(S)\) are of the same degree as they were in \(\Gamma\).

The main result of this section, which is also the most important result we obtain for graphs of odd girths, now follows from Lemma 3.2.

Theorem 3.1. Let \(k \geq 3\), and suppose that there exists a constant \(c_k\) and an infinite increasing sequence of odd girths \(\{g_i\}_{i\in\mathbb{N}}\) such that for each \(g_i\) in the sequence there exists a \((k,g_i)\)-graph \(\Gamma_{k,g_i}\) of order not exceeding \(M_c(k,g_i)+c_k\). Then, for every \(\epsilon \geq 0\), there exists \(N_\epsilon\) such that \(\{\Gamma_{k,g_i}\}_{i\geq N_\epsilon}\) is an expander family with the Cheeger constant of each of the graphs \(\Gamma_{k,g_i}\), \(i\geq N_\epsilon\), greater than or equal to

\[\frac{1}{k-1} - \epsilon.\]

Proof. Let \(g_i=2s_i+1\), and \(\Gamma_{k,g_i}\) be a \((k,g_i)\)-graph of order not exceeding \(M_c(k,g_i)+c_k\), (where \(M_c(k,g_i)+c_k=\frac{k(k-1)^{s_i-2}}{k-2}+c_k\)). Let S be a non-empty subset of \(V(\Gamma_{k,g_i})\) with size at most \(\frac{|V(\Gamma_{k,g_i})|}{2}\), and let \(\beta_{k,g_i}=\frac{M_c(k,g_i-2)}{|V(\Gamma_{k,g_i})|}\geq \frac{k(k-1)^{s_i-1}-2}{k(k-1)^{s_i+c_k}(k-2)}\). Lemma 3.2 asserts the existence of a vertex \(u\in V(\Gamma_{k,g_i})\) such that the set \(S=V(T_{k,g_i-1}^u)\cap S\) is of cardinality at least \(\beta_{k,g_i}|S|\). Suppose \(\tilde{S}_u\) denote the set \(S=S_u\), then the lower bound on the order of \(|S_u|\) yields an upper bound on \(|\tilde{S}_u|\), namely, \(|\tilde{S}_u|=|S|-|S_u|\leq |S|-\beta_{k,g_i}|S|=(1-\beta_{k,g_i})|S|\). Consider the multipole \(\Gamma_{k,g_i}^M(S_u)\). Since \(\Gamma_{k,g_i}\) is k-regular, the induced multipole \(\Gamma_{k,g_i}^M(S_u)\) is also k-regular. Moreover, \(S_u\) is a subset of \(V(T_{k,s_{i-1}}^u)\). Therefore \(\Gamma_{k,g_i}^M(S_u)=(T_{k,g_i}^u)^M(S_u)\), where \(T_{k,s_i}^u\) is a tree (and thus contains no cycles). It follows that \(\Gamma_{k,g_i}^M(S_u)\) contains no cycles. Hence, the number of edges with both end-vertices contained in \(\Gamma_{k,g_i}^M(S_u)\) is at most \(|V(\Gamma_{k,g_i}^M(S_u))|-1=|S_u|-1\), and all other (semi-)edges of \(\Gamma_{k,g_i}^M(S_u)\) are in fact true semi-edges; each incident with exactly one vertex in \(S_u\). Furthermore, all semi-edges of \(\Gamma_{k,g_i}^M(S_u)\) stem from edges of \(\Gamma_{k,g_i}^M(S_u)\) incident with a vertex in \(S_u\) and a vertex in \(S_u\) and \(S_u\). Recalling again that \(T_{k,g_i}^u\) is a tree, it follows that no two distinct edges in \(\Gamma_{k,g_i}^M(S_u)\) and \(S_u\). Recalling again that \(T_{k,g_i}^u\) can be incident to the same vertex in \(S_u\) as this would form a cycle of length less than \(g_i=2s_i+1\). Thus, the number of edges of \(\Gamma_{k,g_i}^M\) incident to a vertex in \(S_u\) and \(S_u\) is bounded from above by \(|\tilde{S}_u|\leq (1-\beta_{k,g_i})|S|\). This bound also yields a lower bound on the number of edges of \(\Gamma_{k,g_i}^M(S_u)\) of the second kind, i.e., edges incident to a vertex in \(S_u\) and \(V(\Gamma_{k,g_i})-S\):

\[k|S_u| - |S_u| + 1 - (1 - \beta_{k,g_i})|S| = |S_u|(k-1) + 1 - (1 - \beta_{k,g_i})|S|;\]

the total number of edges and semi-edges in the multipole \(\Gamma_{k,g_i}(S_u)\) minus an upper bound on the number of edges in \(\Gamma_{k,g_i}(S_u)\) minus an upper bound on the number of edges between \(S_u\) and \(\tilde{S}_u\). If we recall that the number of edges \(\Gamma_{k,g_i}\) incident to a vertex in \(S_u\) and \(V(\Gamma_{k,g_i}) - S\) is a lower bound on the number \(|\sigma(S)|\) of edges incident to a vertex in S and \(V(\Gamma_{k,g_i}) - S\), then for every

non-empty subset S of \(V(\Gamma_{k,g_i})\),

\[|\sigma(S)| \ge |S_u|(k-1) + 1 - (1 - \beta_{k,g_i})|S|\] \[\ge \beta_{k,g_i}|S|(k-1) + 1 - (1 - \beta_{k,g_i})|S|\] \[= |S|(\beta_{k,g_i}k - 1) + 1.\] (3)

This yields a lower bound on the Cheeger constant of \(\Gamma_{k,q_i}\):

\[\begin{split} \min_{0<|S|\leq \frac{|V(\Gamma_{k,g_i})|}{2}} \{\frac{|\sigma(S)|}{|S|}\} &\geq \min_{0<|S|\leq \frac{|V(\Gamma_{k,g_i})|}{2}} \{\beta_{k,g_i}k - 1 + \frac{1}{|S|}\} \\ &\geq \beta_{k,g_i}k - 1 + \frac{2}{|V(\Gamma_{k,g_i})|} \\ &\geq \frac{k(k-1)^{s_i-1} - 2}{k(k-1)^{s_i-1} - 2} k - 1 + \frac{2}{\frac{k(k-1)^{s_i-2} + c_k}{k-2} + c_k} \\ &= \frac{k(k-1)^{s_i-1} - 2}{k(k-1)^{s_i} - 2 + c_k(k-2)} k - 1 + \frac{2(k-2)}{k(k-1)^{s_i} - 2 + c_k(k-2)} \\ &= \frac{k^2(k-1)^{s_i-1} - 2k - k(k-1)^{s_i} + 2 - c_k(k-2) + 2k - 4}{k(k-1)^{s_i} - 2 + c_k(k-2)} \\ &= \frac{k^2(k-1)^{s_i-1} - 2k - k(k-2)}{k(k-1)^{s_i} - 2 + c_k(k-2)} - \frac{k(k-1)^{s_i} + 2c_k(k-2)}{k(k-1)^{s_i} - 2 + c_k(k-2)}. \end{split}\]

Since,

\[\lim_{s_i \to \infty} \left( \frac{k^2(k-1)^{s_i-1} + c_k(k-2)}{k(k-1)^{s_i} - 2 + c_k(k-2)} - \frac{k(k-1)^{s_i} + 2c_k(k-2)}{k(k-1)^{s_i} - 2 + c_k(k-2)} \right) = \lim_{s_i \to \infty} \frac{k^2(k-1)^{s_i-1} - 2 + c_k(k-2)}{k(k-1)^{s_i} - 2 + c_k(k-2)} - \lim_{s_i \to \infty} \frac{k(k-1)^{s_i} + 2c_k(k-2)}{k(k-1)^{s_i} - 2 + c_k(k-2)} = \frac{k}{k-1} - 1 = \frac{1}{k-1},\]

the result follows. \(\Box\)

By proving the above theorem we have established our claim that for graphs of odd girths a positive answer to even the weakest variant of the Bermond and Bollobás question adapted to cages yields families of expanders.

4. Even Girth

Having resolved the case of odd girth, the next natural case to study is that of even girth. Fortunately, essentially the same counting argument as the one used for odd girth can also be applied here. This similarity allows us to compress our arguments somewhat and make them less detailed than those used in the case of odd girth. However, it is important to emphasize that for

even girth g=2s, instead of using a Moore tree \(\mathcal{T}^u_{k,s}\) (rooted at a vertex u), we use a Moore tree \(\mathcal{T}^e_{k,s}\) associated with two vertices u and v that are connected by an edge e, the root edge. The reason is that a Moore tree for a (k,g)-graph of even girth g=2s consists of two trees of depth s-1 rooted at two vertices of degree k-1, incident to the root edge e. The reader familiar with the most common proof of the Moore bound has already seen this situation, as that proof is also divided into the odd and even girth cases, with the even girth case relying on a tree consisting of two subtrees of equal depth connected via an edge between their roots and edges pairing their leaves. It is then easy to see that the order of \(\mathcal{T}^e_{k,s}\) corresponds to the Moore bound for cages of even girth given in the Introduction.

Lemma 4.1. Let \(g=2s\geq 4\), and let \(\Gamma\) be a (k,g)-graph. For every vertex \(v\in V(\Gamma)\) and every \(0\leq s'\leq s-1\), there exist exactly M(k,2s'+1)-1 edges \(e\in E(\Gamma)\) such that the Moore tree \(\mathcal{T}^e_{k\,s'}\) contains v.

Proof. A vertex \(v \in V(\Gamma)\) is contained in \(\mathcal{T}^e_{k,s'}\), for some \(e \in E(\Gamma)\), if and only if the distance of v to at least one of the endpoints of e is less than or equal to s'-1. Since the number of such edges is equal to the number of edges contained in the tree \(\mathcal{T}^v_{k,s'}\) (rooted at a vertex v), there are M(k, 2s'+1)-1 edges \(e \in E(\Gamma)\) with this property (recall that \(\mathcal{T}^v_{k,s'}\) is a tree), and the result follows. Here, it is important to emphasize that the tree \(\mathcal{T}^v_{k,s'}\) is a vertex-rooted tree (just like the trees in the previous section) which is not necessarily a subtree of \(\Gamma\), since \(\Gamma\) is of girth g=2s and the depth of \(\mathcal{T}^v_{k,s'}\) is \(s' \leq s\). The extra -1 in the expression M(k, 2s'+1)-1 is due to the fact that we are counting edges and not vertices in the tree \(\mathcal{T}^v_{k,s'}\).

Lemma 4.2. Let \(g=2s\geq 4\), let \(\Gamma\) be a (k,g)-graph, and let \(\beta=\frac{M(k,2s-1)-1}{|E(\Gamma)|}=\frac{2M(k,2s-1)-2}{k|V(\Gamma)|}\). Suppose \(\emptyset\neq S\subseteq V(\Gamma)\). Then, there exists an edge \(e\in E(\Gamma)\) whose Moore tree \(\mathcal{T}^e_{k,s-1}\) contains at least \(\beta|S|\) vertices from S, i.e., \(|V(\mathcal{T}^e_{k,s-1})\cap S|\geq \beta|S|\).

Proof. Suppose for contradiction that the claim in Lemma 4.2 is not true, that is, for every \(e \in E(\Gamma)\) the inequality \(|V(\mathcal{T}^e_{k,s-1}) \cap S| < \beta |S|\). Then,

\[\sum_{e \in E(\Gamma)} |V(\mathcal{T}^e_{k,s-1}) \cap S| < \beta \cdot |E(\Gamma)| \cdot |S|.\]

Applying Lemma 4.1, we observe that for each vertex \(v \in S\) there are exactly M(k, 2s - 1) - 1 trees \(\mathcal{T}_{k,s-1}^e\), \(e \in E(\Gamma)\), that contain v. Thus,

\[\sum_{e \in E(\Gamma)} |V(\mathcal{T}_{k,s-1}^e) \cap S| = |S| \cdot (M(k, 2s - 1) - 1).\]

Combining the two results yields the inequality

\[|S| \cdot (M(k, 2s - 1) - 1) < \beta \cdot |E(\Gamma)| \cdot |S|\]

which implies the desired contradiction

\[M(k, 2s - 1) - 1 < \frac{M(k, 2s - 1) - 1}{|E(\Gamma)|} \cdot |E(\Gamma)|.\]

In the sequel, we apply Lemma 4.2 to prove the main result of this section.

Theorem 4.1. Let \(k \geq 3\), and suppose that there exists a constant \(c_k\) and an infinite increasing sequence of even girths \(\{g_i\}_{i\in\mathbb{N}}\) such that for each \(g_i\) in the sequence there exists a \((k,g_i)\)-graph \(\Gamma_{k,g_i}\) of order not exceeding \(M_c(k,g_i)+c_k\). Then, for every \(\epsilon \geq 0\), there exists \(N_\epsilon\) such that \(\{\Gamma_{k,g_i}\}_{i\geq N_\epsilon}\) is an expander family with the Cheeger constant of each of the graphs \(\Gamma_{k,g_i}\), \(i\geq N_\epsilon\), greater than or equal to

\[\frac{1}{k-1} - \epsilon.\]

Proof. Let \(g_i = 2s_i\), and \(\Gamma_{k,q_i}\) be a \((k,g_i)\)-graph such that

\[|\Gamma_{k,g_i}| \le M_c(k,g_i) + c_k = \frac{2(k-1)^{s_i} - 2}{k-2} + c_k.\]

Let \(\varnothing \neq S \subseteq V(\Gamma_{k,g_i})\) be of cardinality at most \(\frac{|V(\Gamma_{k,g_i})|}{2}\), and let \(\beta_{k,g_i}\) be the ratio of the size of \(\mathcal{T}^e_{k,s_i-1}\) to the size of \(\Gamma_{k,g_i}\), i.e.,

\[\beta_{k,g_i} = \frac{M_c(k,2s_i-1)-1}{|E(\Gamma_{k,2s_i-1})|} = \frac{2M_c(k,2s_i-1)-2}{k|V(\Gamma_{k,2s_i-1})|} \geq \frac{2M_c(k,2s_i-1)-2}{k(M_c(k,2s_i)+c_k)} = \frac{\frac{2k(k-1)^{s_i-1}-4-2(k-2)}{k-2}}{\frac{2k(k-1)^{s_i}-2k+c_kk(k-2)}{k-2}} = \frac{2k(k-1)^{s_i-1}-2k}{2k(k-1)^{s_i}-2k+c_kk(k-2)}.\]

By Lemma 4.2, there exists a vertex \(u \in V(\Gamma_{k,g_i})\) with the set \(S_u = V(\mathcal{T}_{k,s_i-1}^e) \cap S\) and \(|S_u| \geq \beta_{k,g_i}|S|\). Now, if we let \(\tilde{S}_u\) denote the set \(S - S_u\), then it follows from the proof of Theorem 3.1 that \(|\tilde{S}_u| \leq (1 - \beta_{k,g_i})|S|\). Consider the multipole \(\Gamma_{k,g_i}^M(S_u)\). Since \(\Gamma_{k,g_i}\) is k-regular, the induced multipole \(\Gamma_{k,g_i}^M(S_u)\) is also k-regular. Furthermore, \(S_u\) is a subset of \(V(\mathcal{T}_{k,s_i-1}^e)\), and therefore \(\Gamma_{k,g_i}^M(S_u) = (\mathcal{T}_{k,s_i}^e)^M(S_u)\), where \(\mathcal{T}_{k,s_i}^e\) is a tree with root edge e. It follows that \(\Gamma_{k,g_i}^M(S_u)\) contains no cycles, and hence the number of edges with both end-vertices contained in \(\Gamma_{k,g_i}^M(S_u)\) is at most \(|V(\Gamma_{k,g_i}^M(S_u))| - 1 = |S_u| - 1\), and all other (semi-)edges of \(\Gamma_{k,g_i}^M(S_u)\) are in fact true semi-edges; each incident with exactly one vertex in \(S_u\). Moreover, all semi-edges of \(\Gamma_{k,g_i}^M(S_u)\) stem from edges of \(\Gamma_{k,g_i}\) incident with a vertex in \(S_u\) and \(V(\Gamma_{k,g_i}) - S_u\); which also come in two kinds. First, there are edges of \(\Gamma_{k,g_i}\) incident to a vertex in \(S_u\) and \(\tilde{S}_u\). Recalling again that \(\mathcal{T}_{k,s_i}^e\) is a tree, it follows that no two distinct edges in \(\Gamma_{k,g_i}\) incident to a vertex in \(S_u\) and a vertex in \(\tilde{S}_u\) can be incident to the same vertex in \(\tilde{S}_u\) as this would cause the existence of a cycle of length less than \(g_i = 2s_i\). Thus, the number of edges of \(\Gamma_{k,g_i}\) incident with a vertex in \(S_u\) and \(\tilde{S}_u\) is bounded from above by \(|\tilde{S}_u| \leq (1 - \beta_{k,g_i})|S|\). This yields a lower bound on the number of edges of \(\Gamma_{k,g_i}\) of the second kind, i.e., edges incident to a vertex in \(S_u\) and \(V(\Gamma_{k,g_i}) - S\):

\[k|S_u| - |S_u| + 1 - (1 - \beta_{k,g_i})|S| = |S_u|(k-1) + 1 - (1 - \beta_{k,g_i})|S|;\]

the total number of edges and semi-edges in the multipole \(\Gamma_{k,g_i}(S_u)\) minus an upper bound on the number of edges in \(\Gamma_{k,g_i}(S_u)\) minus an upper bound on the number of edges between \(S_u\) and \(\tilde{S}_u\). By observing that the number of edges of \(\Gamma_{k,g_i}\) incident to a vertex in \(S_u\) and \(V(\Gamma_{k,g_i}) - S\) is a

lower bound on the number \(|\sigma(S)|\) of edges incident to a vertex in S and \(V(\Gamma_{k,g_i}) - S\), we obtained that for every non-empty subset S of \(V(\Gamma_{k,g_i})\),

\[|\sigma(S)| \ge |S_u|(k-1) + 1 - (1 - \beta_{k,g_i})|S|\] \[\ge \beta_{k,g_i}|S|(k-1) + 1 - (1 - \beta_{k,g_i})|S|\] \[= |S|(\beta_{k,g_i}k - 1) + 1.\] (4)

This yields a lower bound on the Cheeger constant of \(\Gamma_{k,g_i}\):

\[\begin{split} \min_{0<|S|\leq \frac{|\sigma(S)|}{2}} \{\frac{|\sigma(S)|}{|S|}\} &\geq \min_{0<|S|\leq \frac{|V(\Gamma_{k,g_i})|}{2}} \{\beta_{k,g_i}k - 1 + \frac{1}{|S|}\} \\ &\geq \beta_{k,g_i}k - 1 + \frac{2}{|V(\Gamma_{k,g_i})|} \\ &\geq \frac{2k(k-1)^{s_i-1} - 2k}{2k(k-1)^{s_i} - 2k + c_kk(k-2)}k - 1 + \frac{2}{\frac{2(k-1)^{s_i-2} + c_k}{k-2} + c_k} \\ &= \frac{2k(k-1)^{s_i-1} - 2k}{2(k-1)^{s_i} - 2 + c_k(k-2)} - 1 + \frac{2(k-2)}{2(k-1)^{s_i} - 2 + c_k(k-2)} \\ &= \frac{2k(k-1)^{s_i-1} - 2k}{2(k-1)^{s_i-1} - 2k - 2(k-1)^{s_i} + 2 - c_k(k-2) + 2k - 4} \\ &= \frac{2k(k-1)^{s_i-1} - 2 + c_k(k-2)}{2(k-1)^{s_i} - 2 + c_k(k-2)} - \frac{2(k-1)^{s_i} + 2c_k(k-2)}{2(k-1)^{s_i} - 2 + c_k(k-2)}. \end{split}\]

Since,

\[\lim_{s_i \to \infty} \left( \frac{2k(k-1)^{s_i-1} - 2 + c_k(k-2)}{2(k-1)^{s_i} - 2 + c_k(k-2)} - \frac{2(k-1)^{s_i} + 2c_k(k-2)}{2(k-1)^{s_i} - 2 + c_k(k-2)} \right) = \lim_{s_i \to \infty} \frac{2k(k-1)^{s_i} - 2 + c_k(k-2)}{2(k-1)^{s_i} - 2 + c_k(k-2)} - \lim_{s_i \to \infty} \frac{2(k-1)^{s_i} + 2c_k(k-2)}{2(k-1)^{s_i} - 2 + c_k(k-2)} = \frac{k}{k-1} - 1 = \frac{1}{k-1},\]

the result follows.

5. Concluding Remarks

The results of the previous two sections assert our key claim both for the odd as well as for the even girth cases. Combined into a single theorem, they establish the main result of our paper:

Theorem 5.1. Let \(k \geq 3\), and let \(c_k\) be a positive constant for which there exists an infinite increasing sequence of girths \(\{g_i\}_{i\in\mathbb{N}}\) and an infinite family of \((k,g_i)\)-graphs \(\{\Gamma_{k,g_i}\}_{i\in\mathbb{N}}\) of orders not exceeding \(M_c(k,g_i)+c_k\). Then, for every \(\epsilon \geq 0\), there exists an infinite subsequence \(\{g_{i_j}\}_{j\in\mathbb{N}}\) of the sequence \(\{g_i\}_{i\in\mathbb{N}}\) such that \(\{\Gamma_{k,g_{i_j}}\}_{j\in\mathbb{N}}\) is an expander family with the Cheeger constant greater than or equal to \(\frac{1}{k-1}-\epsilon\).

Proof. An infinite increasing sequence of girths \(\{g_i\}_{i\in\mathbb{N}}\) necessarily contains an infinite subsequence of odd or an infinite subsequence of even girths. Applying the appropriate theorem of Theorems 3.1 and 4.1 yields the desired results.

Let us reiterate the fact that even though we did not explicitly mention any of the three variants BB1, BB2, or BB3 in the statement of the above theorem, it asserts exactly the fact that a positive answer to any of these three yields expander families. In fact, it asserts even more. Even if BB3 does not hold for all all \(k \geq 3\), should there exist a \(k \geq 3\) for which there exists a \(c_k\) and an infinite family of (k, g)-graphs whose excesses are smaller than \(c_k\), this family necessary contains k-regular expander families.

Interestingly, a careful analysis of the proofs of Theorems 3.1 and 4.1 suggests the possibility of further strengthening the results in a way that would assure the existence of an expander subfamily of k-regular graphs even in a sequence of \((k,g_i)\)-graphs whose orders do not exceed \(M_c(k,g_i)+f(g_i)\) for a sufficiently slowly increasing function f. Since we wanted to keep our investigation in line with the original question of Bermond and Bollobás, we did not pursue this direction. Instead, before concluding our article, we wish to point out that it is not even known whether there exists a \(k \geq 3\) and a corresponding constant \(C_k\) such that there exist infinitely many \(g_i \geq 3\) with the property that there exists a \((k,g_i)\)-graph of order not exceeding \(C_k M_c(k,g_i)\); a constant multiple of the Moore bound. In view of this, one might be tempted to ask whether a similar result to that of Theorem 5.1 might exist for constant multiples of \(M_c(k,g_i)\), i.e., whether any family of \((k,g_i)\)-graphs whose orders do not exceed \(C_k M_c(k,g_i)\), for any given constant \(C_k\), must contain a subfamily of expanders.

The answer to such question stated in this most general form is negative. It is not true that any family of \((k, g_i)\)-graphs whose orders do not exceed \(C_k M_c(k, g_i)\), for any given constant \(C_k\), necessarily contains a family of expanders. The argument for this claim goes as follows.

Let \(k\geq 3\), and suppose the existence of an infinite family of \((k,g_i)\)-graphs \(\Gamma_{k,g_i}\), \(i\in\mathbb{N}\), of orders not exceeding \(\alpha_k M_c(k,g_i)\) for some fixed \(\alpha_k>1\) (if no such family and no such \(\alpha_k\) exist, the above question is obviously moot). Let \(\overline{\Gamma}_{k,g_i}\) be a family of graphs constructed from the graphs \(\Gamma_{k,g_i}\) by taking two disjoint copies \(\Gamma^1_{k,g_i}\) and \(\Gamma^2_{k,g_i}\) of \(\Gamma_{k,g_i}\), selecting the same edge \(\{u^1,v^1\}\) and \(\{u^2,v^2\}\) in each of the copies, removing the edges \(\{u^1,v^1\}\) and \(\{u^2,v^2\}\) and replacing them with edges \(\{u^1,v^2\}\) and \(\{u^2,v^1\}\). It is not hard to see that the resulting family \(\overline{\Gamma}_{k,g_i}\), \(i\in\mathbb{N}\), is a family of \((k,g_i)\)-graphs of orders not exceeding \(2\alpha_k M_c(k,g_i)\). Moreover, it is also not hard to see that this new family does not contain a subfamily of expanders: The number of edges between the two complementary subsets of vertices belonging to \(\Gamma^1_{k,g_i}\) and \(\Gamma^2_{k,g_i}\) of \(\overline{\Gamma}_{k,g_i}\) is always 2 regardless of the order of \(\Gamma_{k,g_i}\). Thus, even if the family \(\Gamma_{k,g_i}\), \(i\in\mathbb{N}\), contained a family of expanders, the family \(\overline{\Gamma}_{k,g_i}\), \(i\in\mathbb{N}\), would not.

Since the above 'trick' of connecting two copies of a vertex-transitive graph does not necessarily produce a vertex-transitive graph, it still might be the case that any infinite family of vertex-transitive \((k,g_i)\)-graphs \(\Gamma_{k,g_i}\) of orders not exceeding \(\alpha_k M_c(k,g_i)\), for any constant \(\alpha_k > 1\), necessarily contains a subfamily of expanders. However, a similarly simple trick preserving the vertex-transitivity of the constructed graphs (possibly creating graphs of orders which are a constant multiple of the orders of the original graphs where the constant is larger than 2) may also resolve this question in negative. Therefore, we leave this question for further investigation.

Another interesting aspect of Theorem 5.1 is that the lower bound stated in there decreases with increasing k. Some readers might find it counterintuitive. Nevertheless, no part of our proof appears to suggest the possibility of improving the bound for large degrees.

We also feel that we should stress the fact that no explicit construction of an infinite family of graphs satisfying BB3 even for a single \(k \geq 3\) has ever been found. Acknowledging this fact, Biggs defined a family of graphs of large girth to be an infinite sequence of k-regular graphs \(\{\Gamma_i\}_{i=1}^{\infty}\) of increasing orders \(n_i\) and girths \(g_i\) satisfying the inequality \(g_i \geq \gamma \log_{k-1}(n_i)\), for all i and some positive constant \(\gamma\) [4]. Due to the Moore bound, \(\gamma \leq 2\), and the best constructions to this date have brought us families of graphs with \(\gamma\) roughly equal to \(\frac{4}{3}\) [15, 13, 11]. Any infinite family of k-regular graphs satisfying BB3 would certainly yield a family of graphs of large girth with \(\gamma > \frac{4}{3}\).

Finally, in view of the results obtained in [8] where the authors have shown that the existence of an infinite family of graphs of fixed degree and increasing diameters of orders differing from the Moore bound by at most a constant would necessarily lead to a family of Ramanujan graphs, one should ask whether it might be possible to prove a similar result in case of cages. If such a result were possible, it would probably have to be proven by radically different techniques. Invoking the Cheeger inequality (2) and using the Cheeger constant determined in Theorem 5.1, one only obtaines the inequalities

\[\frac{k - \lambda(\Gamma_{k,g_i})}{2} \le \frac{1}{k} \le \sqrt{2k(k - \lambda(\Gamma_{k,g_i}))}\]

implying the inequalities

\[k - \frac{2}{k} \le \lambda(\Gamma_{k,g_i}) \le k - \frac{1}{2k^3},\]

which is quite far from being able to prove that \(\lambda(\Gamma_{k,g_i}) \leq 2\sqrt{k-1}\). The only way to remedy this approach would depend on finding a better (larger) Cheeger constant for the considered families, which we were not able to do, and which might not even exist.

Acknowledgement

Both authors acknowledge support from VEGA 1/0437/23 and the second author is also supported by APVV-23-0076, and SK-AT-23-0019.

References

• [1] N. Alon, Eigenvalues and expanders, Combinatorica 6(2) (1986), 83–96.
• [2] J.C. Bermond and B. Bollobás, The diameter of graphs: A survey, Congressus Numerantium 32 (1981), 3–27.
• [3] N.L. Biggs, Excess in vertex-transitive graphs, Bull. London Math. Society 14 (1982), 52–54.
• [4] N.L. Biggs, Graphs with large girth, Ars Comb. 25C (1988), 73–80.
• [5] N.L. Biggs, Constructions for cubic graphs of large girth, Electron. J. Combin. 5 (1998).

• Analogues of Bermond-Bollobás conjecture for cages yield expander families | L. C. Eze and R. Jajcay
  • [6] P. Erdos and H. Sachs, Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl, ˝ Wiss. Z. Uni. Halle (Math. Nat.) 12 (1963), 251–257.
  • [7] G. Exoo and R. Jajcay, Dynamic cage survey, Electron. J. Comb., Dynamic Survey 16 (2013).
  • [8] S. Filipovski and R. Jajcay, A connection between a question of Bermond and Bollobás and Ramanujan graphs, Acta Appl. Math. 175(1) (2021), 1–10.
  • [9] J. Friedman, A proof of Alon's second eigenvalue conjecture and related problems, Mem. Amer. Math. Soc. 195(910) (2008).
• [10] A. J. Hoffman and R. R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. Res. Develop. 4 (1960), 497–504.
• [11] F. Lazebnik, S. Sun, and Y. Wang, Some families of graphs, hypergraphs and digraphs defined by systems of equations: a survey, in Labbate, Domenico (ed.), Selected topics in graph theory and its applications, Lecture Notes of Seminario Interdisciplinare di Matematica 14 (2017), 105–142.
• [12] S. Hoory, N. Linial, and A. Wigderson, Expander graphs and their applications, Bull. Am. Math. Soc., New Ser. 43(4) (2006), 439–561.
• [13] A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8(3) (1988), 261– 277.
• [14] A.W. Marcus, D.A. Spielman, and N. Srivastava, Interlacing families I: Bipartite Ramanujan graphs of all degrees, Ann. Math. (2) 182, No. 1, (2015), 307–325.
• [15] G.A. Margulis, Explicit constructions of concentrators, Problemy Peredachi Informatsii 9 no. 4 (1973), 71–80.
• [16] M. Miller and J. Širán, Moore graphs and beyond: A survey of the degree/diameter problem, ˇ Electron. J. Combin., Dynamic Survey 14 (2005).
• [17] M. Morgenstern, Existence and explicit constructions of q + 1 regular Ramanujan graphs for every prime power q, J. Comb. Theory B 62 no. 1 (1994), 44–62.
• [18] J.Y. Yang and J.H. Koolen, On the order of regular graphs with fixed second largest eigenvalue, Linear Algebra and its Applications 610 (2021), 29–39.