pith. machine review for the scientific record. sign in

arxiv: 2605.11320 · v1 · submitted 2026-05-11 · 🧮 math.AC · math.CO

Recognition: 2 theorem links

· Lean Theorem

Generalized Andr\'asfai graphs and special Betti diagrams of edge ideals

Ignacio Garc\'ia-Marco, Philippe Gimenez, Sara Asensio

Pith reviewed 2026-05-13 02:51 UTC · model grok-4.3

classification 🧮 math.AC math.CO
keywords graphsedgecompletegeneralizedidealsbettibipartitefamily
0
0 comments X

The pith

Removing a suitable Hamiltonian cycle from generalized Andrásfai graphs GA(t,k) yields edge ideals with regularity t+2, projective dimension t(k-2), and a generalized special Betti diagram.

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

Edge ideals are algebraic objects built from the edges of a graph. Earlier work showed that for complete graphs and complete bipartite graphs, removing a Hamiltonian cycle leaves an ideal whose algebraic complexity (measured by regularity and Betti numbers) follows a simple pattern. The authors introduce a larger family of graphs called generalized Andrásfai graphs that contains both of those families as special cases. They prove that the same pattern continues to hold: after removing an appropriate cycle, the resulting ideal has regularity exactly t+2 and projective dimension t(k-2), with Betti diagrams that follow a predictable shape generalizing the earlier cases. The proofs rely on combinatorial arguments about the structure of these graphs and standard tools from commutative algebra.

Core claim

when removing a suitable Hamiltonian cycle from GA(t,k), the resulting edge ideal has regularity t+2, projective dimension t(k-2) and a Betti diagram exhibiting a generalized version of the same special shape.

Load-bearing premise

That the newly defined family GA(t,k) admits a suitable Hamiltonian cycle for every t ≥ 1 and k ≥ 2 such that the combinatorial structure after removal produces exactly the claimed regularity, dimension, and Betti diagram shape.

Figures

Figures reproduced from arXiv: 2605.11320 by Ignacio Garc\'ia-Marco, Philippe Gimenez, Sara Asensio.

Figure 1
Figure 1. Figure 1: Generalized Andr´asfai GA(3, 6) = And(6) with the exterior cycle marked in red introduced by Das, Biswas and Saha [3] as an extension of the classical Andr´asfai graphs [1] (which first appeared in the context of extremal combinatorics, as they are non-bipartite triangle-free graphs with the largest possible ratio between degree and number of vertices). Generalized Andr´asfai graphs correspond to complete … view at source ↗
Figure 2
Figure 2. Figure 2: From top to bottom: Betti diagrams of I(GA(t, 5)′ ) for t ∈ {1, 2, 3, 4} 0 1 2 3 4 5 6 7 8 9 10 11 12 2 34 102 102 34 · · · · · · · · · 3 · 221 1326 3315 4488 3451 1394 221 · · · · · 4 · · 85 765 3060 7021 10115 9520 5967 2482 646 85 · 5 · · · · · · · · · · · · 1 0 1 2 3 4 5 6 7 8 9 10 11 12 2 34 102 85 17 · · · · · · · · · 3 · 187 1156 2686 3077 1802 493 51 · · · · · 4 · · 34 459 2176 4794 5678 3808 1377 … view at source ↗
Figure 3
Figure 3. Figure 3: From top to bottom: Betti diagrams of the edge ideals of GA(3, 6)′ , GA(3, 6) without the edges in the Hamiltonian cycle C4 = (4k mod 17 | 0 ≤ k ≤ 16), and GA(3, 6) without the edges in the Hamiltonian cycle C7 = (7k mod 17 | 0 ≤ k ≤ 16) is denoted by N(v), where the letter N stands for the word neighborhood. Furthermore, we denote by N[v] the closed neighborhood of v, which equals N(v) ∪ {v}. Given a subs… view at source ↗
Figure 4
Figure 4. Figure 4: Betti table of I(GA(t, 3)′ ) = I((t + 1) · K2) Theorem 2.8. Let ∆ be a simplicial complex, and let v ∈ V (∆) such that link∆(v) ̸= {∅}. Then there is a long exact sequence · · · → Hej (link∆(v)) → Hej (del∆(v)) → Hej (∆) → Hej−1(link∆(v)) → · · · · · · → He0(link∆(v)) → He0(del∆(v)) → He0(∆) → 0 . A direct consequence of this Mayer-Vietoris sequence is the following: Corollary 2.9. Let ∆ be a simplicial co… view at source ↗
Figure 5
Figure 5. Figure 5: A K2,3 induced subgraph of And(6)′ Lemma 3.3. Let t, k ≥ 3 and a, b ∈ N with 0 < a ≤ b. Then, ka,b(GA(t, k) ′ ) = ( n [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Vertices of the complete bipartite induced subgraph of GA(t, k) ′ GA(t, k) ′ isomorphic to Ka,b. To derive the formula for ka,b, it suffices to observe that this correspon￾dence is bijective whenever a < b, and all fibers have size 2 if a = b. □ Proposition 3.4. For all i ≥ 0, βi,i+2(I(GA(t, k) ′ )) = n  k − 2 i + 1 i + 1 2  . Proof. By Lemma 3.2, it is enough to compute P a+b=i+2 0<a≤b ka,b. The resul… view at source ↗
Figure 7
Figure 7. Figure 7: Induced matching of size 3 in And(6)′ Take now S ⊆ Zn such that the corresponding induced subgraph of GA(t, k) ′ is an induced matching of maximum size, and let us prove that it is of this form. We denote the edges of this matching by {u1, v1}, . . . , {us, vs}, where s ≥ t, ui < vi < t(k − 1) + 2 and u1 < u2 < · · · < us and assume, without loss of generality, that u1 = 0 and vi ̸= t(k − 1) + 1 for all i … view at source ↗
Figure 8
Figure 8. Figure 8: ). 0 t · (k − 1) + 1 ui ≡ uj ≡ vj − 1 (mod t) ui uj vj [PITH_FULL_IMAGE:figures/full_fig_p009_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Area containing the exact shape of the Betti diagram of I(GA(t, k) ′ ) Furthermore, we can determine the exact shape of the Betti diagram of I(GA(t, k) ′ ) in the case t = 3. We devote the next section to this problem. 7. Exact shape of the Betti diagram of I(And(k) ′ ) The goal of this section is to describe the exact shape of the Betti diagram of I(And(k) ′ ), which is given by the following result (see … view at source ↗
Figure 10
Figure 10. Figure 10: Exact shape of the Betti diagram of I(And(k) ′ ) Theorem 7.1. Let k ≥ 3 and consider And(k) ′ , the Andr´asfai graph from which the exterior cycle has been removed. Then: (1) if βi,i+j (I(And(k) ′ )) ̸= 0, then 2 ≤ j ≤ 5, (2) βi,i+2(I(And(k) ′ )) ̸= 0 if and only if i ∈ {0, . . . , k − 3}, (3) βi,i+3(I(And(k) ′ )) ̸= 0 if and only if i ∈ {1, . . . , 2k − 5}, (4) βi,i+4(I(And(k) ′ )) ̸= 0 if and only if i … view at source ↗
Figure 11
Figure 11. Figure 11: Betti diagram of the edge ideal of And(6) = GA(3, 6) Interestingly, one can also prove that reg(I(GA(t, k))) = t by combining Lemma 5.3 with the following fact: for every k ′ > t(k − 1) + k + 1, GA(t, k) is isomorphic to an induced subgraph of GA(t, k′ ) ′ via the map x 7→ (t + 1)x for all 0 ≤ x ≤ t(k − 1) + 1. Our results suggest several natural directions for future research. For every graph G, the exis… view at source ↗
Figure 12
Figure 12. Figure 12: Shape of the Betti diagram of I(GA(t, k) ′ ), according to Conjecture 8.2 Finally, all graph families considered in this paper satisfy the identity reg(I(G)) + pd(I(G)) = |V (G)|. This equality also holds for several classical graph families, but it fails in general. It would therefore be interesting to understand when this happens. Question 8.3. Characterize the graphs G such that reg(I(G)) + pd(I(G)) = … view at source ↗
read the original abstract

Edge ideals of graphs were introduced by Villarreal in 1990, and have been the subject of many studies since then. In the same year, Fr\"oberg characterized edge ideals with regularity 2 in combinatorial terms. This result was generalized by Fern\'andez-Ramos and Gimenez to regularity 3 for bipartite graphs. A key ingredient in these results is the particular shape of the Betti diagrams of the edge ideals of the graphs obtained after removing a Hamiltonian cycle from either a complete graph $ K_k$ or a complete bipartite graph $K_{k,k}$. In this work, we consider the family of Generalized Andr\'asfai graphs ${\rm GA}(t,k)$ with $t\geq 1 $ and $k \geq 2$. This family extends the families of complete graphs, since $K_{k+1} = {\rm GA}(1,k)$, and complete bipartite $k$-regular graphs, since $K_{k,k} = {\rm GA}(2,k)$. We show that the results known for $ K_k$ and $ K_{k,k}$ can be naturally extended to this family. More precisely, when removing a suitable Hamiltonian cycle from ${\rm GA}(t,k)$, the resulting edge ideal has regularity $t+2$, projective dimension $t(k-2)$ and a Betti diagram exhibiting a generalized version of the same special shape.

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

Summary. The paper defines the family of Generalized Andrásfai graphs GA(t,k) for t ≥ 1 and k ≥ 2, extending K_{k+1} = GA(1,k) and K_{k,k} = GA(2,k). It proves that removing a suitable Hamiltonian cycle from GA(t,k) yields an edge ideal with regularity t+2, projective dimension t(k-2), and a Betti diagram of generalized special shape, extending prior results on regularity 2 (Fröberg) and regularity 3 for bipartite graphs (Fernández-Ramos-Gimenez).

Significance. If the claims hold, the work supplies an explicit parameterized family of graphs whose edge ideals have fully determined homological invariants, allowing systematic construction of examples with prescribed regularity and Betti shapes beyond the classical complete and complete-bipartite cases. This strengthens the combinatorial-algebraic dictionary for monomial ideals and may support further classification results.

major comments (2)
  1. [Definition of GA(t,k) and main theorem] The existence of a suitable Hamiltonian cycle in GA(t,k) for arbitrary t ≥ 1, k ≥ 2 is load-bearing for the central claim; the manuscript must supply an explicit construction or inductive proof that the cycle removal produces exactly regularity t+2 and projective dimension t(k-2) (see the statement following the definition of GA(t,k) and the main theorem on Betti diagrams).
  2. [Main theorem on Betti diagrams] The explicit computation of the Betti diagram after cycle removal, showing the generalized special shape, requires a self-contained argument or table of generators in each bidegree; without it the extension from the t=1 and t=2 cases remains unverified (main theorem on Betti diagrams).
minor comments (2)
  1. Add a small explicit example (e.g., t=1, k=3 and t=2, k=3) with the resulting Betti table to illustrate the generalized shape.
  2. [Definition of GA(t,k)] Clarify the precise edge set in the definition of GA(t,k) to make the Hamiltonian-cycle construction immediately verifiable from the combinatorial description.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. The feedback correctly identifies points where additional explicit details would strengthen the presentation of the constructions and homological computations. We address each major comment below and will incorporate revisions accordingly.

read point-by-point responses

  1. Referee: The existence of a suitable Hamiltonian cycle in GA(t,k) for arbitrary t ≥ 1, k ≥ 2 is load-bearing for the central claim; the manuscript must supply an explicit construction or inductive proof that the cycle removal produces exactly regularity t+2 and projective dimension t(k-2) (see the statement following the definition of GA(t,k) and the main theorem on Betti diagrams).

    Authors: We agree that an explicit construction is necessary for the central claims. The manuscript defines GA(t,k) recursively, extending the known Hamiltonian cycles for the base cases t=1 (complete graphs) and t=2 (complete bipartite graphs). In the revised version we will add an inductive construction of the cycle for general t and k, together with a direct combinatorial argument showing that its removal from the edge ideal produces exactly the stated regularity t+2 and projective dimension t(k-2). revision: yes

  2. Referee: The explicit computation of the Betti diagram after cycle removal, showing the generalized special shape, requires a self-contained argument or table of generators in each bidegree; without it the extension from the t=1 and t=2 cases remains unverified (main theorem on Betti diagrams).

    Authors: The main theorem generalizes the Betti-diagram shape from the t=1 and t=2 cases using the recursive structure of GA(t,k). To make the argument fully self-contained we will include, in the revision, an explicit computation of the minimal generators in each bidegree (via a mapping-cone argument or direct resolution) together with a table of Betti numbers for representative small values of t and k that illustrates the generalized special shape. revision: yes

Circularity Check

0 steps flagged

No circularity; new graph family and invariants derived independently

full rationale

The paper defines the new family GA(t,k) independently as a combinatorial extension of K_{k+1} and K_{k,k}, then proves the stated regularity, projective dimension, and generalized Betti diagram shape after Hamiltonian cycle removal via direct combinatorial arguments. Prior results (including the self-citation to Fernández-Ramos and Gimenez for the t=2 case) supply background context but are not invoked to force the new claims by definition or by fitting. No step reduces a claimed prediction to an input parameter, renames a known result, or relies on a self-citation chain for uniqueness. The derivation remains self-contained and externally verifiable through the explicit graph construction and edge ideal computations.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the combinatorial definition of GA(t,k), the existence of a suitable Hamiltonian cycle, and standard facts from graph theory and commutative algebra about edge ideals and Betti diagrams. No numerical free parameters are fitted. The new graph family is the main added entity.

axioms (1)
  • standard math Standard results on edge ideals, regularity, and Betti diagrams from commutative algebra and graph theory (Fröberg 1990, Fernández-Ramos-Gimenez).
    The paper explicitly builds on these characterizations and extends them.
invented entities (1)
  • Generalized Andrásfai graphs GA(t,k) no independent evidence
    purpose: To provide a common generalization of complete graphs and complete bipartite graphs so that the known Betti-diagram results extend uniformly.
    Defined in the paper as a new parametric family of graphs.

pith-pipeline@v0.9.0 · 5559 in / 1394 out tokens · 80776 ms · 2026-05-13T02:51:19.329947+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.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · 1 internal anchor

  1. [1]

    Graphentheoretische extremalprobleme.Acta Mathematica Academiae Scientiarum Hungaricae, 15:413–438, 1964

    B´ ela Andr´ asfai. Graphentheoretische extremalprobleme.Acta Mathematica Academiae Scientiarum Hungaricae, 15:413–438, 1964

    work page 1964

  2. [2]

    Extremal Betti numbers and applications to monomial ideals

    Dave Bayer, Hara Charalambous, and Sorin Popescu. Extremal Betti numbers and applications to monomial ideals. Journal of Algebra, 221(2):497–512, 1999

    work page 1999

  3. [3]

    Generalized Andr´ asfai graphs.Discussiones Mathematicae - General Algebra and Applications, 42:449–462, 2022

    Angsuman Das, Sucharita Biswas, and Manideepa Saha. Generalized Andr´ asfai graphs.Discussiones Mathematicae - General Algebra and Applications, 42:449–462, 2022

    work page 2022

  4. [4]

    Eagon and Victor Reiner

    John A. Eagon and Victor Reiner. Resolutions of Stanley-Reisner rings and Alexander duality.Journal of Pure and Applied Algebra, 130(3):265–275, 1998

    work page 1998

  5. [5]

    Princeton University Press, 1952

    Samuel Eilenberg and Norman Steenrod.Foundations of Algebraic Topology. Princeton University Press, 1952

    work page 1952

  6. [6]

    Restricting linear syzygies: algebra and geometry

    David Eisenbud, Mark Lee Green, Klaus Hulek, and Sorin Popescu. Restricting linear syzygies: algebra and geometry. Compositio Mathematica, 141:1460–1478, 2004

    work page 2004

  7. [7]

    Minimal resolutions of some monomial ideals.Journal of Algebra, 129(1):1–25, 1990

    Shalom Eliahou and Michel Kervaire. Minimal resolutions of some monomial ideals.Journal of Algebra, 129(1):1–25, 1990

    work page 1990

  8. [8]

    Complexes of directed trees and independence complexes.Discrete Mathematics, 309(10):3299– 3309, 2009

    Alexander Engstr¨ om. Complexes of directed trees and independence complexes.Discrete Mathematics, 309(10):3299– 3309, 2009

    work page 2009

  9. [9]

    Chromatic numbers from edge ideals: Graph classes with vanishing syzygies are polynomially $\chi$-bounded

    Alexander Engstr¨ om. Chromatic numbers from edge ideals: Graph classes with vanishing syzygies are polynomially χ-bounded.Preprint, arXiv:2512.21800 [math.CO], 2025. 20 S. ASENSIO, I. GARC ´IA-MARCO, AND P. GIMENEZ

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  10. [10]

    First nonlinear syzygies of ideals associated to graphs.Communica- tions in Algebra, 37(6):1921–1933, 2009

    ´Oscar Fern´ andez-Ramos and Philippe Gimenez. First nonlinear syzygies of ideals associated to graphs.Communica- tions in Algebra, 37(6):1921–1933, 2009

    work page 1921

  11. [11]

    Regularity 3 in edge ideals associated to bipartite graphs.Journal of Algebraic Combinatorics, 39:919–937, 2014

    ´Oscar Fern´ andez-Ramos and Philippe Gimenez. Regularity 3 in edge ideals associated to bipartite graphs.Journal of Algebraic Combinatorics, 39:919–937, 2014

    work page 2014

  12. [12]

    Francisco, Huy T` ai H` a, and Adam Van Tuyl

    Christopher A. Francisco, Huy T` ai H` a, and Adam Van Tuyl. Colorings of hypergraphs, perfect graphs, and associated primes of powers of monomial ideals.Journal of Algebra, 331(1):224–242, 2011

    work page 2011

  13. [13]

    On Stanley-Reisner rings.Banach Center Publications, 26(2):57–70, 1990

    Ralf Fr¨ oberg. On Stanley-Reisner rings.Banach Center Publications, 26(2):57–70, 1990

    work page 1990

  14. [14]

    Splittable ideals and the resolutions of monomial ideals.Journal of Algebra, 309(1):405–425, 2007

    Huy T` ai H` a and Adam Van Tuyl. Splittable ideals and the resolutions of monomial ideals.Journal of Algebra, 309(1):405–425, 2007

    work page 2007

  15. [15]

    Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers

    Huy T` ai H` a and Adam Van Tuyl. Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers. Journal of Algebraic Combinatorics, 27:215–245, 2008

    work page 2008

  16. [16]

    Correction to: Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers [J

    Huy T` ai H` a and Adam Van Tuyl. Correction to: Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers [J. ALGEBRAIC COMBIN. 27 (2008), NO. 2, 215-245].Journal of Algebraic Combinatorics, 58(1):325–328, October 2022

    work page 2008

  17. [17]

    Springer, London, 2011

    J¨ urgen Herzog and Takayuki Hibi.Monomial Ideals, volume 260 ofGraduate Texts in Mathematics. Springer, London, 2011

    work page 2011

  18. [18]

    Melvin Hochster. Cohen-Macaulay rings, combinatorics, and simplicial complexes.Ring Theory, II, (Proceedings of the Second Conference, University of Oklahoma, Norman, Oklahoma, 1975), pages 171–223, 1975

    work page 1975

  19. [19]

    PhD thesis, University of Sheffield, 2004

    Sean Jacques.Betti numbers of graph ideals. PhD thesis, University of Sheffield, 2004

    work page 2004

  20. [20]

    A characterization of edge ideals with reg(R/I(G)) = 3.Preprint, arXiv:2603.23321 [math.AC], 2026

    Akane Kanno. A characterization of edge ideals with reg(R/I(G)) = 3.Preprint, arXiv:2603.23321 [math.AC], 2026

    work page arXiv 2026

  21. [21]

    Characteristic-independence of Betti numbers of graph ideals.Journal of Combinatorial Theory, Series A, 113(3):435–454, 2006

    Mordechai Katzman. Characteristic-independence of Betti numbers of graph ideals.Journal of Combinatorial Theory, Series A, 113(3):435–454, 2006

    work page 2006

  22. [22]

    Springer, New York, 2005

    Ezra Miller and Bernd Sturmfels.Combinatorial Commutative Algebra, volume 227 ofGraduate Texts in Mathemat- ics. Springer, New York, 2005

    work page 2005

  23. [23]

    On the linear strand of an edge ideal.Communications in Algebra, 35(3):821–832, 2007

    Mike Roth and Adam Van Tuyl. On the linear strand of an edge ideal.Communications in Algebra, 35(3):821–832, 2007

    work page 2007

  24. [24]

    Villarreal

    Rafael H. Villarreal. Cohen-Macaulay graphs.Manuscripta Mathematica, 66:277–293, 1990

    work page 1990

  25. [25]

    Villarreal.Monomial Algebras

    Rafael H. Villarreal.Monomial Algebras. Chapman & Hall/CRC Monographs and Research Notes in Mathematics. CRC Press, Boca Raton, FL, 3rd edition, 2026. Instituto de Investigaci´on en Matem´aticas (IMUVa), Universidad de Valladolid, Valladolid, Spain Email address:sara.asensio@uva.es Instituto de Matem ´aticas y Aplicaciones (IMAULL), Secci ´on de Matem´ati...

    work page 2026