pith. sign in

arxiv: 1907.11568 · v1 · pith:WT2IJLVZnew · submitted 2019-07-26 · 🧮 math.CO

Bipartite Biregular Cages and Block Designs

Gabriela Araujo-Pardo , Alejandra Ramos-Rivera , Robert Jajcay This is my paper

Pith reviewed 2026-05-24 15:36 UTC · model grok-4.3

classification 🧮 math.CO
keywords Steiner systemsbipartite biregular graphsMoore cagesgirthblock designscombinatorial constructionsincidence graphs
0
0 comments X

The pith

Steiner systems S(2,k,v) produce bipartite biregular Moore cages of girth 6.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that any Steiner system S(2,k,v) can be turned into a bipartite graph with partite degrees k and (v-1)/(k-1) that has girth exactly 6 and meets the Moore lower bound on the number of vertices. In the special case of Steiner triple systems the construction settles the existence of all (3,m;6) cages for m at least 4. The same approach links generalized polygons to Moore cages of girths 8, 12 and 16, and supplies new upper bounds on cage orders for those girths. The link mirrors the classical correspondence between projective planes and regular Moore graphs of girth 6.

Core claim

The existence of an S(2,k,v)-Steiner system yields the existence of a bipartite biregular (k,(v-1)/(k-1);6)-Moore cage. For Steiner triple systems the (3,m;6)-bipartite biregular cages exist for every integer m greater than or equal to 4. Generalized polygons likewise produce Moore cages of girths 8, 12 and 16, and these constructions improve the known upper bounds on the orders of bipartite biregular cages for girths 8, 12 and 14.

What carries the argument

The incidence graph of the Steiner system (points versus blocks) that realises the required degrees and attains the Moore bound at girth 6.

If this is right

  • Every S(2,k,v) Steiner system supplies a (k,(v-1)/(k-1);6) Moore cage.
  • Bipartite biregular (3,m;6) cages exist for every m greater than or equal to 4.
  • Generalized quadrangles, hexagons and octagons supply Moore cages of girths 8, 12 and 16 respectively.
  • New explicit upper bounds hold for the orders of bipartite biregular cages of girths 8, 12 and 14.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Infinite families of Steiner systems immediately give infinite families of these cages.
  • Design-theoretic counting arguments could be reused to bound cage orders in other degree-girth combinations.
  • Small known Steiner systems can be checked directly to confirm the girth and order claims of the construction.
  • The same incidence-graph technique may adapt to other 2-designs that are not Steiner systems.

Load-bearing premise

The incidence graph built from the Steiner system has girth exactly 6 and exactly the Moore number of vertices.

What would settle it

A concrete S(2,k,v) Steiner system whose incidence graph either contains a 4-cycle or has more vertices than the Moore lower bound for those degrees.

Figures

Figures reproduced from arXiv: 1907.11568 by Alejandra Ramos-Rivera, Gabriela Araujo-Pardo, Robert Jajcay.

Figure 1
Figure 1. Figure 1: A sketch of how to obtain G. For an example, consider [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Part of the (6,3;6)-cage. hence 32 ≤ |V (G)|. On the other hand, it follows from [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
read the original abstract

A bipartite biregular $(n,m;g)$-graph $G$ is a bipartite graph of even girth $g$ having the degree set $\{n,m\}$ and satisfying the additional property that the vertices in the same partite set have the same degree. An $(n,m;g)$-bipartite biregular cage is a bipartite biregular $(n,m;g)$-graph of minimum order. In their 2019 paper, Filipovski, Ramos-Rivera and Jajcay present lower bounds on the orders of bipartite biregular $(n,m;g)$-graphs, and call the graphs that attain these bounds {\em bipartite biregular Moore cages}. In parallel with the well-known classical results relating the existence of $k$-regular Moore graphs of even girths $g = 6,8 $ and $12$ to the existence of projective planes, generalized quadrangles, and generalized hexagons, we prove that the existence of $S(2,k,v)$-Steiner systems yields the existence of bipartite biregular $(k,\frac{v-1}{k-1};6)$-Moore cages. Moreover, in the special case of Steiner triple systems (i.e., in the case $k=3$), we completely solve the problem of the existence of $(3,m;6)$-bipartite biregular cages for all integers $m\geq 4$. Considering girths higher than $6$ and prime powers $s$, we relate the existence of generalized polygons (quadrangles, hexagons and octagons) with the existence of $(n+1,n^2+1;8)$, $(n+1,n^3+1;12)$, and $(n+1,n^2+1;16)$-bipartite biregular Moore cages, respectively. Using this connection, we derive improved upper bounds for the orders of bipartite biregular cages of girths $8$, $12$ and $14$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript claims that the existence of an S(2,k,v) Steiner system implies the existence of a bipartite biregular (k, (v-1)/(k-1);6)-Moore cage via its incidence graph, and that Steiner triple systems completely solve the existence of (3,m;6)-bipartite biregular cages for all m≥4. It further relates generalized polygons to the existence of (n+1,n²+1;8), (n+1,n³+1;12), and (n+1,n²+1;16)-Moore cages and derives improved upper bounds on cage orders for girths 8, 12, and 14.

Significance. A correct connection between Steiner systems and Moore cages would furnish explicit constructions and resolve an infinite family of cage problems, complementing the classical links to projective planes and generalized polygons. The higher-girth results would also be of interest if the bounds are new. The (3,m;6) solution claim, if valid, would be a substantial contribution to the area.

major comments (2)
  1. [Abstract] Abstract: the central claim that any S(2,k,v) yields a (k,r;6)-Moore cage with r=(v-1)/(k-1) is false except when v=k²-k+1. The incidence graph has partite sets of sizes v and b=v(v-1)/(k(k-1)), meeting the point-side Moore count 1+r(k-1)=v but exceeding the block-side count 1+k(r-1) unless v=k²-k+1. For the affine plane of order 3 (S(2,3,9)), the graph has 21 vertices while the Moore lower bound is 19; the same strict inequality holds for all STS(v) with v>7. This directly falsifies both the general existence statement and the claimed complete solution for (3,m;6) cages.
  2. [Construction via Steiner systems] The girth-6 construction section (where the incidence graph is shown to have girth exactly 6): while λ=1 correctly implies no 4-cycles, the order calculation shows the graph is a cage but not a Moore cage except in the projective-plane case; the manuscript therefore misidentifies the extremal graphs.
minor comments (1)
  1. [Abstract] The abstract and introduction should explicitly compare the new upper bounds for g=8,12,14 against the 2019 Filipovski et al. bounds they improve upon.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the flaw in our central claim. The referee is correct that the incidence graphs of general S(2,k,v) Steiner systems are not Moore cages except in the projective-plane case (v = k² - k + 1). We will revise the manuscript to remove the incorrect assertions that these graphs are Moore cages and that the (3,m;6) problem is completely solved. The higher-girth results relating generalized polygons to Moore cages remain as stated and are not addressed by the referee's comments.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that any S(2,k,v) yields a (k,r;6)-Moore cage with r=(v-1)/(k-1) is false except when v=k²-k+1. The incidence graph has partite sets of sizes v and b=v(v-1)/(k(k-1)), meeting the point-side Moore count 1+r(k-1)=v but exceeding the block-side count 1+k(r-1) unless v=k²-k+1. For the affine plane of order 3 (S(2,3,9)), the graph has 21 vertices while the Moore lower bound is 19; the same strict inequality holds for all STS(v) with v>7. This directly falsifies both the general existence statement and the claimed complete solution for (3,m;6) cages.

    Authors: We agree with the referee's analysis and the concrete counter-example. The incidence graph attains the Moore lower bound on the point side but exceeds it on the block side except when the design is a projective plane. Consequently the general existence claim and the assertion that Steiner triple systems solve all (3,m;6) Moore-cage problems are false. We will revise the abstract (and the introduction) to state only that the incidence graphs furnish explicit constructions of bipartite biregular (k,r;6)-graphs of girth 6; we will delete the erroneous Moore-cage and complete-solution claims. revision: yes

  2. Referee: [Construction via Steiner systems] The girth-6 construction section (where the incidence graph is shown to have girth exactly 6): while λ=1 correctly implies no 4-cycles, the order calculation shows the graph is a cage but not a Moore cage except in the projective-plane case; the manuscript therefore misidentifies the extremal graphs.

    Authors: The referee is correct. The λ=1 condition guarantees girth 6, but the resulting order meets the Moore bound only for projective planes. We will rewrite the construction section to describe the graphs as (k,r;6)-cages (or as providing upper bounds on cage orders) and to remove all statements that they are Moore cages outside the projective-plane case. revision: yes

Circularity Check

0 steps flagged

No circularity; explicit constructions from external Steiner systems attain cited bounds

full rationale

The derivation consists of an explicit incidence-graph construction from any S(2,k,v) Steiner system (an externally existing combinatorial object) together with a direct verification that the resulting biregular graph has girth 6 and meets the order lower bound stated in the authors' prior 2019 paper. No parameter is fitted to the target cage order, no quantity is defined in terms of itself, and the self-citation supplies only the independent lower-bound formula rather than the central existence implication. The special-case solution for Steiner triple systems likewise rests on the known existence spectrum of STS(v), which is independent of the present paper.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Results depend only on the standard definitions and existence conditions of Steiner systems and generalized polygons; no free parameters, ad-hoc axioms, or new entities are introduced.

axioms (1)
  • domain assumption Standard incidence and girth properties of S(2,k,v) Steiner systems and of generalized quadrangles, hexagons, and octagons
    Invoked to guarantee that the constructed graphs meet the Moore bound and have the claimed girth.

pith-pipeline@v0.9.0 · 5900 in / 1292 out tokens · 28898 ms · 2026-05-24T15:36:14.056431+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    Araujo-Pardo, D

    G. Araujo-Pardo, D. Gonz´ alez-Moreno, J.J. Montellano-Balles teros, O. Serra, On upper bounds and connectivity of cages, Australasian J. Combin. 38 (2009) 221-228

    work page 2009

  2. [2]

    Araujo-Pardo, C

    G. Araujo-Pardo, C. Balbuena, P. Garc ´ ıa-V´ azquez, X. Marcote, J.C. Valen- zuela, On the order of ( {r, m}; g)-cages of even girth, Discrete Math. 308 (2008) 2484-2491

    work page 2008

  3. [3]

    Araujo-Pardo, C

    G. Araujo-Pardo, C. Balbuena, and T. H´ eger, Finding small reg ular graphs of girths 6, 8 and 12 as subgraphs of cages, Discrete Math. 310 (8) (2010) 1301-1306

    work page 2010

  4. [4]

    Araujo-Pardo, G

    G. Araujo-Pardo, G. Exoo and R. Jajcay, Small biregular graph s of even girth, Discrete Math. 339 (2016) 658-667. 11

    work page 2016

  5. [5]

    Boben, R

    M. Boben, R. Jajcay and T. Pisanski, Generalized cages, Electron. J. Com- bin. 22(1) (2015) #P1.77

    work page 2015

  6. [6]

    C.J.Colbourn and J.Dinitz (eds.), The CRC handbook of combinatorial de- signs. 2nd ed. , Discrete Mathematics and its Applications, Boca Raton, FL: Chapman & Hall/CRC (2007) 984 p

    work page 2007

  7. [7]

    Erd˝ os and H

    P. Erd˝ os and H. Sachs, Regul¨ are Graphen gegebener Taillenweite mit min- imaler Knotenzahl, Wiss. Z. Uni. Halle (Math. Nat.) 12 (1963) 251-257

    work page 1963

  8. [8]

    Exoo and R

    G. Exoo and R. Jajcay, Dynamic cage survey, Electron. J. Combin., Dy- namic Survey 16 (2008)

    work page 2008

  9. [9]

    Exoo and R

    G. Exoo and R. Jajcay, Biregular cages of odd girth, J. Graph Theory 81, No. 1 (2016), 50-56

    work page 2016

  10. [10]

    Filipovski, On bipartite cages of excess 4, Electron

    S. Filipovski, On bipartite cages of excess 4, Electron. J. Combin. 24(1) (2017) #P1.40

    work page 2017

  11. [11]

    Filipovski, A

    S. Filipovski, A. Ramos Rivera and R. Jajcay, On biregular bipartit e graphs of small excess, Discrete Math. 342 (2019), 2066-2076

    work page 2019

  12. [12]

    Furedi, F

    Z. Furedi, F. Lazebnik, A. Seress, V. A. Ustimenko and A. J. Wo ldar, Graphs of prescribed girth and bi-degree, J. Comb. Theory Ser. B 64 (1995) 228-239

    work page 1995

  13. [13]

    T. B. Jajcayov´ a, S. Filipovski and R. Jajcay, Improved lower bounds for the orders of even-girth cages, Electron. J. Combin. 23(3) (2016) #P3.55

    work page 2016

  14. [14]

    Van Maldeghem, Generalized Polygons , Birkh¨ auser, Springer, Basel (1998)

    H. Van Maldeghem, Generalized Polygons , Birkh¨ auser, Springer, Basel (1998)

    work page 1998

  15. [15]

    Yuansheng and W

    Y. Yuansheng and W. Liang, The minimum number of vertices with g irth 6 and degree set D = {r, m}, Discrete Math. 269 (2003) 249-258. 12

    work page 2003