Analogues of Bermond-Bollobás conjecture for cages yield expander families - Leonard Chidiebere Eze; Robert Jajcay (GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB, 2026)
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.