pith. sign in

arxiv: 2504.21488 · v3 · submitted 2025-04-30 · 🧮 math.CO

New Constructions of Distance-Biregular Graphs

Blas Fern\'andez , Ferdinand Ihringer , Sabrina Lato , Akihiro Munemasa This is my paper

Pith reviewed 2026-05-22 18:25 UTC · model grok-4.3

classification 🧮 math.CO
keywords distance-biregular graphshyperovalsprojective planesMathon's perp systemDelorme constructionnon-existence conditionsfinite geometries
0
0 comments X

The pith

New constructions yield an infinite family of distance-biregular graphs from hyperovals along with a sporadic example from Mathon's perp system.

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

The paper constructs a new infinite family of distance-biregular graphs by using hyperovals in projective planes of suitable orders. It additionally produces one new sporadic example via a generalization of Delorme's construction applied to Mathon's perp system. The family is tied to the property of 2-bipartite-homogeneity while the sporadic case follows the generalized Delorme method. A fresh non-existence condition is proved that rules out any distance-biregular graph on 285 vertices. A sympathetic reader cares because the results enlarge the catalog of known examples and tighten the constraints on which parameters can occur for these graphs.

Core claim

We construct a new family of distance-biregular graphs related to hyperovals and a new sporadic example of a distance-biregular graph related to Mathon's perp system. The infinite family can be explained using 2-bipartite-homogeneity, while the sporadic example belongs to a generalization of a construction by Delorme. Additionally, we establish a new non-existence condition for distance-biregular graphs which, for instance, rules out the existence of a distance-biregular graph on 225+60 vertices.

What carries the argument

Hyperovals with prescribed intersection properties in projective planes together with the generalized Delorme construction on Mathon's perp system, which together enforce the distance-biregular intersection array.

If this is right

  • Infinite families of distance-biregular graphs exist for every order where the required hyperovals are present.
  • One additional concrete sporadic distance-biregular graph with specific parameters is now known.
  • Distance-biregular graphs on 285 vertices are impossible.
  • Geometric objects such as hyperovals and perp systems can be used to produce graphs with prescribed distance properties.

Where Pith is reading between the lines

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

  • Similar techniques might generate further families from other configurations in finite geometries.
  • The non-existence condition could be applied to additional parameter sets beyond 285 vertices.
  • These graphs may connect to problems in design theory or coding theory through their symmetry properties.
  • Small-order computational enumeration could confirm the new examples or the non-existence bound.

Load-bearing premise

The constructions assume the existence and specific intersection properties of hyperovals in projective planes of certain orders and the validity of the generalized Delorme construction applied to Mathon's perp system.

What would settle it

Explicit verification that the constructed graphs for the smallest order admitting a hyperoval satisfy the required intersection numbers, or a direct search showing whether any distance-biregular graph on exactly 285 vertices exists.

Figures

Figures reproduced from arXiv: 2504.21488 by Akihiro Munemasa, Blas Fern\'andez, Ferdinand Ihringer, Sabrina Lato.

Figure 1
Figure 1. Figure 1: The subgraph induced by N3(z ′ ) ∪ N4(z ′ ). 6.1.1 Theorem. Let G = (Y ∪ Z, E) be a distance-biregular graph with inter￾section array [PITH_FULL_IMAGE:figures/full_fig_p021_1.png] view at source ↗
read the original abstract

We construct a new family of distance-biregular graphs related to hyperovals and a new sporadic example of a distance-biregular graph related to Mathon's perp system. The infinite family can be explained using 2-$\bipartB$-homogeneity, while the sporadic example belongs to a generalization of a construction by Delorme. Additionally, we establish a new non-existence condition for distance-biregular graphs which, for instance, rules out the existence of a distance-biregular graph on $225+60$ vertices.

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 / 3 minor

Summary. The paper constructs a new infinite family of distance-biregular graphs arising from hyperovals in projective planes of order q via 2-bipartite-homogeneity, together with a sporadic example obtained by applying a generalized Delorme construction to Mathon's perp system. It also derives a new non-existence criterion for distance-biregular graphs that excludes, among other parameter sets, any such graph on 225 + 60 vertices.

Significance. If the constructions and the non-existence condition are verified, the work adds concrete new examples to a class of graphs that remains sparsely populated and supplies a useful parameter obstruction. The geometric origin of the constructions (hyperovals and perp systems) offers a systematic route that may generate further families, while the non-existence result tightens the known constraints on feasible intersection arrays.

major comments (2)
  1. [§3] §3, construction of the infinite family: the claim that the resulting graphs are distance-biregular rests on the 2-bipartite-homogeneity property and the intersection numbers inherited from the hyperoval; however, the explicit verification that these numbers satisfy the distance-regularity equations for both partitions is only sketched and should be written out for a representative order (e.g., q=4 or q=8) to confirm the parameters are consistent.
  2. [§5] §5, sporadic example: the generalized Delorme construction applied to Mathon's perp system produces a distance-biregular graph only if the perp system satisfies a specific homogeneity condition on its blocks; the manuscript states that this condition holds but does not supply the numerical intersection array or the eigenvalue check that would make the claim self-contained.
minor comments (3)
  1. The notation for the two partitions (A,B) and the distance sets is introduced without a dedicated preliminary subsection; a short table listing the intersection numbers for the new family would improve readability.
  2. Reference to the original Delorme construction and to Mathon's perp system should include the precise bibliographic details (year and journal) rather than only the author names.
  3. In the non-existence section, the derivation of the new condition is presented as a general inequality; adding the explicit numerical check for the (225,60) parameter set would make the ruling-out statement immediate.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive suggestions. We have revised the paper to incorporate explicit verifications as requested, which we believe strengthen the presentation without altering the main results.

read point-by-point responses

  1. Referee: §3, construction of the infinite family: the claim that the resulting graphs are distance-biregular rests on the 2-bipartite-homogeneity property and the intersection numbers inherited from the hyperoval; however, the explicit verification that these numbers satisfy the distance-regularity equations for both partitions is only sketched and should be written out for a representative order (e.g., q=4 or q=8) to confirm the parameters are consistent.

    Authors: We agree that an explicit verification for a concrete small order improves clarity. In the revised manuscript we have added a full computation of the intersection numbers for q=4, confirming that the distance-regularity equations hold on both partitions by direct substitution of the parameters inherited from the hyperoval and the 2-bipartite-homogeneity property. revision: yes

  2. Referee: §5, sporadic example: the generalized Delorme construction applied to Mathon's perp system produces a distance-biregular graph only if the perp system satisfies a specific homogeneity condition on its blocks; the manuscript states that this condition holds but does not supply the numerical intersection array or the eigenvalue check that would make the claim self-contained.

    Authors: We thank the referee for this observation. The revised Section 5 now includes the explicit intersection array of the resulting graph together with the eigenvalue verification that confirms distance-biregularity under the stated homogeneity condition on the blocks of Mathon's perp system. revision: yes

Circularity Check

0 steps flagged

No significant circularity; constructions rely on external geometric objects

full rationale

The paper's central claims consist of explicit constructions of an infinite family of distance-biregular graphs from hyperovals in projective planes (via 2-bipartite-homogeneity) and a sporadic example from a generalized Delorme construction applied to Mathon's perp system, plus a non-existence criterion derived from intersection number restrictions that rules out the (225,60) parameter set. These steps use stated geometric properties and homogeneity arguments supplied in the manuscript; they do not reduce to self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations whose validity is assumed without external verification. The derivation chain remains self-contained against the cited combinatorial objects.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard assumptions from finite geometry rather than new free parameters or invented entities. Hyperovals and Mathon's perp systems are treated as given combinatorial objects whose properties are invoked to produce the graphs.

axioms (2)
  • domain assumption Existence and intersection properties of hyperovals in projective planes of appropriate order
    Invoked to generate the infinite family via 2-bipartite-homogeneity.
  • domain assumption Properties of Mathon's perp system and its generalization of Delorme's construction
    Used to produce the sporadic distance-biregular graph.

pith-pipeline@v0.9.0 · 5619 in / 1362 out tokens · 62599 ms · 2026-05-22T18:25:17.534598+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages

  1. [1]

    Distance-biregular graphs

    van den Akker, J. Distance-biregular graphs. Master’s thesis, Eindhoven University of Technology, 1990

    work page 1990

  2. [2]

    A regular two-graph admitting the Hall-Janko-Wales group

    Bagchi, B. A regular two-graph admitting the Hall-Janko-Wales group. Sankhy¯ a: The Indian Journal of Statistics, Series B (1992), 35–45

    work page 1992

  3. [3]

    An easier proof of the maximal arcs con- jecture

    Ball, S., and Blokhuis, A. An easier proof of the maximal arcs con- jecture. Proceedings of the American Mathematical Society 126 , 11 (1998), 3377–3380

    work page 1998

  4. [4]

    Maximal arcs in Desargue- sian planes of odd order do not exist

    Ball, S., Blokhuis, A., and Mazzocca, F. Maximal arcs in Desargue- sian planes of odd order do not exist. Combinatorica 17, 1 (1997), 31–41

    work page 1997

  5. [5]

    A geometric construction of Mathon’s perp-system from four lines of pg (5, 3)

    Bamberg, J., and De Clerck, F. A geometric construction of Mathon’s perp-system from four lines of pg (5, 3). Journal of Combinatorial Designs 18, 6 (2010), 450–461

    work page 2010

  6. [6]

    Strongly regular graphs, partial geometries and partially bal- anced designs

    Bose, R. Strongly regular graphs, partial geometries and partially bal- anced designs

    work page

  7. [7]

    G., and Shrikhande, M

    Bose, R., Bridges, W. G., and Shrikhande, M. S. A characterization of partial geometric designs. Discrete Mathematics 16 , 1 (1976), 1–7

    work page 1976

  8. [8]

    Edge regular multigraphs and partial geometric designs with an application to the embedding of quasi-residual designs

    Bose, R., Shrikhande, S., and Singhi, N. Edge regular multigraphs and partial geometric designs with an application to the embedding of quasi-residual designs. Colloquie Internazionale sulle Teorie Combinatorie 1 (1976), 49–81

    work page 1976

  9. [9]

    Brouwer, A. E. Parameters of strongly regular graphs. https://aeb.win.tue.nl/graphs/srg/srgtab.html. Accessed: 16 April 2025

    work page 2025

  10. [10]

    Brouwer, A. E. Strongly regular graphs from hyperovals

    work page

  11. [11]

    E., Cohen, A

    Brouwer, A. E., Cohen, A. M., and Neumaier, A. Distance-regular graphs. Springer Berlin Heidelberg, 1989. tex.lccn: 89010101

    work page 1989

  12. [12]

    E., Ihringer, F., and Kantor, W

    Brouwer, A. E., Ihringer, F., and Kantor, W. M. Strongly regular graphs satisfying the 4-vertex condition. Combinatorica 43, 2 (2023), 257– 276. 26

    work page 2023

  13. [13]

    E., and van Lint, J

    Brouwer, A. E., and van Lint, J. H. Strongly regular graphs and partial geometries. Enumeration and design 85 (1984), 122

    work page 1984

  14. [14]

    E., and V an Maldeghem, H

    Brouwer, A. E., and V an Maldeghem, H. Strongly regular graphs , vol. 182. Cambridge University Press, 2022

    work page 2022

  15. [15]

    Calderbank, R., and Kantor, W. M. The geometry of two-weight codes. Bulletin of the London Mathematical Society 18 , 2 (1986), 97–122

    work page 1986

  16. [16]

    Spectra of Graphs: theory and applications

    Cvetkovi´c, D., Doob, M., and Sachs, H. Spectra of Graphs: theory and applications. 1980

    work page 1980

  17. [17]

    New strongly regular graphs from orthogonal groups O+(6, 2) and O− (6, 2)

    Crnkovi´c, D., Rukavina, S., and ˇSvob, A. New strongly regular graphs from orthogonal groups O+(6, 2) and O− (6, 2). Discrete Mathemat- ics 341 , 10 (2018), 2723–2728

    work page 2018

  18. [18]

    R., Koolen, J., and Tanaka, H

    van Dam, E. R., Koolen, J., and Tanaka, H. Distance-regular graphs. The Electronic Journal of Combinatorics 1000 (2016), DS22–15

    work page 2016

  19. [19]

    Perp-systems and partial geometries

    De Clerck, F., Delanote, M., Hamilton, N., and Mathon, R. Perp-systems and partial geometries

    work page

  20. [20]

    Some classes of rank 2 geometries

    De Clerck, F., and V an Maldeghem, H. Some classes of rank 2 geometries. In Handbook of incidence geometry . Elsevier, 1995, pp. 433– 473

    work page 1995

  21. [21]

    Distance biregular bipartite graphs

    Delorme, C. Distance biregular bipartite graphs. European Journal of Combinatorics 15 , 3 (1994), 223 – 238

    work page 1994

  22. [22]

    Regularit´ e m´ etrique forte, rapport de recherche no

    Delorme, C. Regularit´ e m´ etrique forte, rapport de recherche no. 156, univ. Paris sud, Orsay (1983)

    work page 1983

  23. [23]

    Dimensional dual hyperovals—an updated survey

    Dempwolff, U. Dimensional dual hyperovals—an updated survey. In International Conference on Algebra and Related Topics wit h Applications (2019), Springer, pp. 115–142

    work page 2019

  24. [24]

    Some maximal arcs in finite projective planes

    Denniston, R. Some maximal arcs in finite projective planes. Journal of Combinatorial Theory 6 , 3 (1969), 317–319. Publisher: Elsevier

    work page 1969

  25. [25]

    Feit, W., and Higman, D. G. The nonexistence of certain generalized polygons. Journal of Algebra 1 , 2 (1964), 114–131

    work page 1964

  26. [26]

    On (almost) 2-Y-homogeneous distance- biregular graphs

    Fern´andez, B., and Penji ´c, S. On (almost) 2-Y-homogeneous distance- biregular graphs. Bulletin of the Malaysian Mathematical Sciences Society 46, 2 (2023), 56. Publisher: Springer

    work page 2023

  27. [27]

    Distance-regularised graphs are distance-regular or distance-biregular

    Godsil, C., and Shawe-Taylor, J. Distance-regularised graphs are distance-regular or distance-biregular. Journal of Combinatorial Theory, Series B 43 , 1 (1987), 14 – 24. 27

    work page 1987

  28. [28]

    Goethals, J.-M., and Seidel, J. J. Strongly regular graphs derived from combinatorial designs. Canadian Journal of Mathematics 22 , 3 (1970), 597–614

    work page 1970

  29. [29]

    The simple group of order 604,800

    Hall Jr, M., and W ales, D. The simple group of order 604,800. Journal of Algebra 9 , 4 (1968), 417–450

    work page 1968

  30. [30]

    Strongly regular designs and coherent configurations of type [323]

    Higman, D. Strongly regular designs and coherent configurations of type [323]. European Journal of Combinatorics 9 , 4 (1988), 411–422

    work page 1988

  31. [31]

    On a class of strongly regular designs and quasi-semisymmetric designs

    Huang, T., Huang, L., and Lin, M. On a class of strongly regular designs and quasi-semisymmetric designs. Recent developments in algebra and related areas 8 (2007), 129–153

    work page 2007

  32. [32]

    Distance-biregular graphs and orthogonal polynomials

    Lato, S. Distance-biregular graphs and orthogonal polynomials . PhD the- sis, University of Waterloo, 2023

    work page 2023

  33. [33]

    Polynomial characterizations of distance-biregular graphs

    Lato, S. Polynomial characterizations of distance-biregular graphs. Jour- nal of Graph Theory

    work page

  34. [34]

    Distance-biregular graphs with 2- valent vertices and distance-regular line graphs

    Mohar, B., and Shawe-Taylor, J. Distance-biregular graphs with 2- valent vertices and distance-regular line graphs. Journal of Combinatorial Theory, Series B 38 , 3 (1985), 193–203

    work page 1985

  35. [35]

    t 1 2 -designs

    Neumaier, A. t 1 2 -designs. Journal of Combinatorial Theory, Series A 28 , 3 (1980), 226–248

    work page 1980

  36. [36]

    Regular sets and quasi-symmetric 2-designs

    Neumaier, A. Regular sets and quasi-symmetric 2-designs. In Combina- torial theory: Proceedings of a conference held at schloss r auischholzhausen, may 6–9, 1982 (1982), Springer, pp. 258–275

    work page 1982

  37. [37]

    Secker, P. R. Feasibility algorithms for distance-biregular graphs . PhD thesis, University of Birmingham, 1989

    work page 1989

  38. [38]

    Regularity and transitivity in graphs

    Shawe-Taylor, J. Regularity and transitivity in graphs . Phd, University of London, 1985

    work page 1985

  39. [39]

    S., and Sane, S

    Shrikhande, M. S., and Sane, S. S. Quasi-symmetric designs , vol. 164. Cambridge University Press, 1991

    work page 1991

  40. [40]

    Thas, J. A. Generalized polygons. In Handbook of incidence geometry . Elsevier, 1995, pp. 383–431

    work page 1995

  41. [41]

    Thas, J. A. Partial geometries. In Handbook of combinatorial designs . Chapman & Hall; CRC, 2007, pp. 557–561

    work page 2007

  42. [42]

    Sur la trialit´ e et certains groupes qui s’ en d´ eduisent.Publications Math´ ematiques de l’IH´ES 2 (1959), 13–60

    Tits, J. Sur la trialit´ e et certains groupes qui s’ en d´ eduisent.Publications Math´ ematiques de l’IH´ES 2 (1959), 13–60

    work page 1959

  43. [43]

    Generalized polygons

    V an Maldeghem, H. Generalized polygons. Springer Science & Business Media, 1998. 28

    work page 1998

  44. [44]

    ¨Uber steinersche systeme

    Witt, E. ¨Uber steinersche systeme. Abh. Math. Sem. Univ. Hamburg 12 , 1938 (1938), 265–275

    work page 1938

  45. [45]

    On order in generalized polygons

    Yanushka, A. On order in generalized polygons. Geometriae Dedicata 10, 1-4 (1981), 451–458. Publisher: Springer

    work page 1981

  46. [46]

    Dimensional dual arcs—a survey

    Yoshiara, S. Dimensional dual arcs—a survey. Finite geometries, groups, and computation (2006), 247–266

    work page 2006

  47. [47]

    A family of d-dimensional dual hyperovals in pg (2 d+ 1, 2)

    Yoshiara, S. A family of d-dimensional dual hyperovals in pg (2 d+ 1, 2). European Journal of Combinatorics 20 , 6 (1999), 589–603. 29

    work page 1999