pith. sign in

arxiv: 2605.16838 · v1 · pith:ZS6QABNHnew · submitted 2026-05-16 · 🧮 math.CO

A Ridge-Saturation Characterization of α-Critical mathbf {W}_p Graphs

Do Trong Hoang , Vadim E. Levit , Eugen Mandrescu , Kevin Pereyra This is my paper

Pith reviewed 2026-05-19 21:00 UTC · model grok-4.3

classification 🧮 math.CO
keywords α-critical graphswell-covered graphsW_p classindependence complexridge degreesclique saturationclique codegreeslocalization fibers
0
0 comments X

The pith

Graphs that are α-critical and in W_p have three equivalent characterizations in graph, complex, and complement terms.

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

The paper characterizes graphs that are both α-critical and members of the class W_p. It provides three equivalent descriptions: in the graph itself as a well-covered graph with codimension-one localization fibers of size at least p whose edges are exactly covered by cliques from those fibers; in the independence complex as a pure flag complex where every ridge has degree at least p and missing edges are generated by ridge links; and in the complement as a K_{r+1}-saturated graph with r equal to the independence number, all maximal cliques of size r, and minimum (r-1)-clique codegree at least p. This provides an exact formula for the largest p for which a well-covered graph is in W_p. The work also derives saturation consequences like dense-complement rigidity and p-sensitive bounds, plus examples showing a prior local condition is not necessary outside triangle-free cases.

Core claim

The graphs which are simultaneously α-critical and members of the class W_p are characterized by three equivalent descriptions. In the graph, it is a well-covered graph whose codimension-one localization fibers all have size at least p and whose edges are exactly covered by the cliques induced by those fibers. In the independence complex, it is a pure flag complex in which every ridge has degree at least p and every missing edge is generated by the link of a ridge. In the complement, it is a K_{r+1}-saturated graph, where r=α(G), all maximal cliques have size r, and the minimum (r-1)-clique-codegree is at least p. This gives an exact formula for the largest p for which a well-covered graph属于

What carries the argument

The three equivalent languages for α-critical W_p graphs: codimension-one localization fibers of size at least p with induced cliques exactly covering the edges, ridge degrees at least p in the pure flag independence complex with missing edges from ridge links, and minimum (r-1)-clique codegree at least p in the K_{r+1}-saturated complement where r=α(G) and maximal cliques have size r.

If this is right

  • Well-covered graphs belong to W_p only for p up to an exact value determined by the fiber sizes and codegrees.
  • The complement being K_{r+1}-saturated with the given codegree minimum implies dense-complement rigidity.
  • p-sensitive upper bounds on edges and graph order follow from the saturation and codegree conditions.
  • Sharp examples exist for all p at least 2 showing that a local sufficient condition is not necessary outside locally triangle-free graphs.

Where Pith is reading between the lines

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

  • The multi-language equivalence might extend to characterizations of other critical graph classes beyond α-criticality.
  • These conditions could support enumeration of all such graphs for fixed small values of p and independence number r.
  • The saturation view may link to broader questions in extremal graph theory on clique codegrees and rigidity.
  • Verification algorithms could check W_p membership for candidate critical graphs by testing one of the three equivalent conditions.

Load-bearing premise

The three descriptions are equivalent specifically for α-critical members of W_p relying on the prior definitions of α-criticality and the class W_p.

What would settle it

An α-critical well-covered graph in W_p where at least one codimension-one localization fiber has size less than p, or where the complement fails to be K_{r+1}-saturated with all maximal cliques of size r and minimum (r-1)-clique codegree at least p, would disprove the characterization.

Figures

Figures reproduced from arXiv: 2605.16838 by Do Trong Hoang, Eugen Mandrescu, Kevin Pereyra, Vadim E. Levit.

Figure 1
Figure 1. Figure 1: A ridge in the complement for the case r = 3. The solid upper edge is a Kr−1, the three lower vertices are its extensions to Kr’s, and the dashed lower pairs are missing edges of H. In G = H, those dashed pairs become edges inside the fiber clique FG(S). 6. Consequences and examples 6.1. Small independence number A graph G is called maximal triangle-free if G contains no triangle and, for every non-edge e … view at source ↗
Figure 2
Figure 2. Figure 2: The q = 2 member of the clique blow-up family Gq = C7[Kq]. Each Vi is a clique, and consecutive classes are joined completely. The general case is obtained by replacing each displayed pair by a q-vertex clique. For a ∈ V1 and b ∈ V2, the localization (Gq)ab is induced by V4 ∪ V5 ∪ V6, which is not well-covered. The Petersen graph gives a complementary instance of the same phe￾nomenon in the especially tran… view at source ↗
Figure 3
Figure 3. Figure 3: The Petersen graph P. Its complement is an α-critical graph in W3 with α = 2, by the maximal triangle-free characterization. 7. An algebraic corollary and a homological question Fix a field k. For a simple graph G with vertex set V (G) = {x1, . . . , xn}, the associated edge ideal of G is the quadratic squarefree monomial ideal I(G) = (xixj | xixj ∈ E(G)) in the polynomial ring R = k[x1, . . . , xn]. We sa… view at source ↗
read the original abstract

We characterize the graphs which are simultaneously $\alpha$-critical and members of the class $\mathbf W_p$. The characterization is stated in three equivalent languages. In the graph itself, such a graph is a well-covered graph whose codimension-one localization fibers all have size at least $p$ and whose edges are exactly covered by the cliques induced by those fibers. In the independence complex, it is a pure flag complex in which every ridge has degree at least $p$ and every missing edge is generated by the link of a ridge. In the complement, it is a $K_{r+1}$-saturated graph, where $r=\alpha(G)$, all maximal cliques have size $r$, and the minimum $(r-1)$-clique-codegree is at least $p$. This gives an exact formula for the largest $p$ for which a well-covered graph belongs to $\mathbf W_p$. We make this complement correspondence explicit, record saturation-theoretic consequences including dense-complement rigidity and $p$-sensitive edge and order bounds, and give a family of sharp examples showing that the local sufficient condition from the recent work of Hoang, Levit and Mandrescu is not necessary outside the locally triangle-free setting, for all $p\ge2$.

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 manuscript characterizes the graphs that are simultaneously α-critical and members of the class W_p. The characterization is given in three equivalent languages: (i) in the graph itself, as well-covered graphs whose codimension-one localization fibers all have size at least p and whose edges are exactly covered by the cliques induced by those fibers; (ii) in the independence complex, as pure flag complexes in which every ridge has degree at least p and every missing edge is generated by the link of a ridge; (iii) in the complement, as K_{r+1}-saturated graphs (r=α(G)) with all maximal cliques of size r and minimum (r-1)-clique codegree at least p. The paper derives an exact formula for the largest p for which a well-covered graph belongs to W_p, records saturation-theoretic consequences (dense-complement rigidity, p-sensitive edge and order bounds), and supplies a family of sharp examples showing that the local sufficient condition of Hoang-Levit-Mandrescu is not necessary outside the locally triangle-free setting for all p≥2.

Significance. If the equivalences are established, the result supplies a useful structural unification of graph-theoretic, simplicial-complex, and saturation perspectives on α-critical W_p graphs. The explicit complement correspondence, the exact formula for maximal p, and the sharp examples that falsify the necessity of the prior local condition constitute concrete advances. The manuscript records reproducible constructions for the extremal family and derives falsifiable bounds, which are strengths.

major comments (2)
  1. [§3.2, Theorem 3.4] §3.2, Theorem 3.4: the claimed equivalence between the codimension-one fiber condition (graph language) and the ridge-degree-plus-link-generation condition (independence-complex language) is load-bearing for the entire characterization; the argument invokes the prior definition of W_p and α-criticality but does not contain an explicit, self-contained verification that the link-generation property translates back to the exact edge-cover by induced cliques from the fibers under the α-critical hypothesis.
  2. [§4.1, Corollary 4.3] §4.1, Corollary 4.3: the exact formula for the largest p is derived from the minimum (r-1)-clique codegree in the complement; this step assumes the saturation and maximality conditions already established in the equivalence, so any gap in the cross-verification of the three languages directly affects the formula's validity.
minor comments (2)
  1. [§2] The notation for localization fibers is introduced in §2 without a small illustrative example; adding a concrete 4- or 5-vertex well-covered graph with its fibers labeled would improve readability.
  2. [Figure 2] Figure 2 (the family of sharp examples) does not annotate the value of p or the independence number on the diagram; this makes it harder to verify the claimed saturation and codegree properties at a glance.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on the manuscript. The positive assessment of the significance of the equivalences, the exact formula, and the sharp examples is appreciated. We address each major comment below and will revise the paper to strengthen the explicitness of the cross-verification between the three languages.

read point-by-point responses

  1. Referee: [§3.2, Theorem 3.4] the claimed equivalence between the codimension-one fiber condition (graph language) and the ridge-degree-plus-link-generation condition (independence-complex language) is load-bearing for the entire characterization; the argument invokes the prior definition of W_p and α-criticality but does not contain an explicit, self-contained verification that the link-generation property translates back to the exact edge-cover by induced cliques from the fibers under the α-critical hypothesis.

    Authors: We agree that an additional explicit step would improve clarity and self-containment. In the revised manuscript we will insert a short lemma (or expanded paragraph) immediately after the proof of Theorem 3.4 that directly verifies the reverse direction: under the α-critical hypothesis, the ridge link-generation property implies that every edge lies in exactly one fiber-induced clique and that no extraneous edges are present. This lemma will cite only the definitions of α-criticality and the codimension-one localization fibers already introduced in §2 and §3, thereby closing the loop without circularity. revision: yes

  2. Referee: [§4.1, Corollary 4.3] the exact formula for the largest p is derived from the minimum (r-1)-clique codegree in the complement; this step assumes the saturation and maximality conditions already established in the equivalence, so any gap in the cross-verification of the three languages directly affects the formula's validity.

    Authors: Corollary 4.3 relies on the saturation and maximality properties that follow from the three-language equivalence in Theorem 3.4. Once the explicit verification requested above is added to §3.2, the derivation of the exact formula for the largest p (via the minimum (r-1)-clique codegree) will rest on a fully verified foundation. We will also add a one-sentence cross-reference in the proof of Corollary 4.3 pointing back to the new lemma. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in the equivalence characterization of α-critical W_p graphs

full rationale

The paper's central result is a structural characterization asserting equivalence among three descriptions (graph fibers, ridge degrees in the independence complex, and clique codegrees in the complement) specifically for graphs that are simultaneously α-critical and in W_p. This equivalence is presented as a theorem to be proven from the standard definitions of α-criticality and the class W_p, with no evidence in the abstract or described claims that any description is defined in terms of another or that a parameter is fitted to data and then relabeled as a prediction. The derived formula for maximal p follows from the characterization rather than being presupposed. The reference to prior work by Hoang, Levit and Mandrescu serves only to exhibit a counterexample to necessity outside a special case and does not function as a load-bearing premise for the new equivalences. The derivation chain is therefore self-contained against external graph-theoretic definitions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard definitions of α-critical graphs, well-covered graphs, and the class W_p from prior literature; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption Standard definitions of α-critical graphs and the class W_p of well-covered graphs.
    The characterization and equivalences presuppose these established combinatorial notions.

pith-pipeline@v0.9.0 · 5770 in / 1334 out tokens · 53487 ms · 2026-05-19T21:00:15.372849+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

27 extracted references · 27 canonical work pages

  1. [1]

    Andrásfai, P

    B. Andrásfai, P. Erdős, and V. T. Sós, On the connection be tween chro- matic number, maximal clique and minimal degree of a graph, Discrete Mathematics 8 (1974), no. 3, 205–218. 12

    work page 1974

  2. [2]

    L. W. Beineke, F. Harary, and M. D. Plummer, On the critica l lines of a graph, Pacific Journal of Mathematics 22 (1967), no. 2, 205–212. 2, 5

    work page 1967

  3. [3]

    Berge, Some common properties for regularizable grap hs, edge- critical graphs and B-graphs, Annals of Discrete Mathematics 12 (1982), 31–44

    C. Berge, Some common properties for regularizable grap hs, edge- critical graphs and B-graphs, Annals of Discrete Mathematics 12 (1982), 31–44. 2, 5

    work page 1982

  4. [4]

    Bermudo and H

    S. Bermudo and H. Fernau, Lower bounds on the differential of a graph, Discrete Mathematics 312 (2012), 3236–3250. 2

    work page 2012

  5. [5]

    I. D. Castrillón, R. Cruz, and E. Reyes, On well-covered, vertex decom- posable and Cohen–Macaulay graphs, Electronic Journal of Combina- torics 23 (2016), no. 2, 17 pp. 2

    work page 2016

  6. [6]

    Erdős and T

    P. Erdős and T. Gallai, On the minimal number of vertices r epresenting the edges of a graph, Publications of the Mathematical Institute of the Hungarian Academy of Sciences 6 (1961), 181–203. 2, 5

    work page 1961

  7. [7]

    Erdős, A

    P. Erdős, A. Hajnal, and J. W. Moon, A problem in graph theo ry, The American Mathematical Monthly 71 (1964), no. 10, 1107–1110. 3, 4

    work page 1964

  8. [8]

    Favaron, Very well-covered graphs, Discrete Mathematics 42 (1982), 177–187

    O. Favaron, Very well-covered graphs, Discrete Mathematics 42 (1982), 177–187. 2

    work page 1982

  9. [9]

    Finbow, B

    A. Finbow, B. Hartnell, and R. Nowakowski, A characteriz ation of well- covered graphs of girth 5 or greater, Journal of Combinatorial Theory. Series B 57 (1993), 44–68. 2, 7

    work page 1993

  10. [10]

    D. T. Hoang, V. E. Levit, E. Mandrescu, and M. H. Pham, On t he uni- modality of the independence polynomial of clique corona gr aphs, A vail- able online at SSRN: http://dx.doi.org/10.2139/ssrn.4293649. 2

    work page doi:10.2139/ssrn.4293649

  11. [11]

    D. T. Hoang, V. E. Levit, E. Mandrescu, and M. H. Pham, Log - concavity of the independence polynomials of Wp graphs, Discrete Mathematics 349 (2026), 115109. 2 19

    work page 2026

  12. [12]

    D. T. Hoang and T. N. Trung, A characterization of triang le-free Goren- stein graphs and Cohen–Macaulayness of second powers of edg e ideals, Journal of Algebraic Combinatorics 43 (2016), 325–338. 2, 17

    work page 2016

  13. [13]

    D. T. Hoang and T. N. Trung, Buchsbaumness of the second p owers of edge ideals, Journal of Algebra and Its Applications 17 (2018), no. 6, 1850117. 2

    work page 2018

  14. [14]

    D. T. Hoang, V. E. Levit, and E. Mandrescu, Structural pr operties and characterizations of Wp class, Discussiones Mathematicae Graph Theory, A vailable online at https://doi.org/10.7151/dmgt.2623. 2, 3, 7, 8, 14, 18

    work page doi:10.7151/dmgt.2623

  15. [15]

    Jaramillo and R

    D. Jaramillo and R. H. Villarreal, The v-number of edge ideals, Journal of Combinatorial Theory. Series A 177 (2021), 105310. 2, 8

    work page 2021

  16. [16]

    V. E. Levit and E. Mandrescu, The Roller-Coaster conjec ture revisited, Graphs and Combinatorics 33 (2017), 1499–1508. 2

    work page 2017

  17. [17]

    V. E. Levit and E. Mandrescu, 1-well-covered graphs rev isited, European Journal of Combinatorics 80 (2019), 261–272. 2, 7

    work page 2019

  18. [18]

    M. R. Pinter, A class of planar well-covered graphs with girth four, Journal of Graph Theory 19 (1995), 69–81. 2, 7

    work page 1995

  19. [19]

    M. R. Pinter, Planar regular one-well-covered graphs, Congressus Nu- merantium 91 (1992), 159–159. 2

    work page 1992

  20. [20]

    M. R. Pinter, W2 graphs and strongly well-covered graphs: two well- covered graph subclasses, Ph.D. thesis, Vanderbilt Univer sity, Depart- ment of Mathematics, 1991. 2

    work page 1991

  21. [21]

    M. D. Plummer, Some covering concepts in graphs, Journal of Combi- natorial Theory 8 (1970), 91–98. 2, 4

    work page 1970

  22. [22]

    M. D. Plummer, Well-covered graphs: survey, Quaestiones Mathemati- cae 16 (1993), 253–287. 2, 4, 7

    work page 1993

  23. [23]

    M. D. Plummer, On a family of line-critical graphs, Monatshefte für Mathematik 71 (1967), no. 1, 40–48. 2, 5 20

    work page 1967

  24. [24]

    J. W. Staples, On some subclasses of well-covered graph s, Ph.D. thesis, Vanderbilt University, 1975. 2, 4

    work page 1975

  25. [25]

    J. W. Staples, On some subclasses of well-covered graph s, Journal of Graph Theory 3 (1979), 197–204. 2, 4

    work page 1979

  26. [26]

    Topp and L

    J. Topp and L. Volkmann, On the well-coveredness of prod ucts of graphs, Ars Combinatoria 33 (1992), 199–215. 2

    work page 1992

  27. [27]

    Woodroofe, Vertex decomposable graphs and obstruct ions to shella- bility, Proceedings of the American Mathematical Society 137 (2009), 3235–3246

    R. Woodroofe, Vertex decomposable graphs and obstruct ions to shella- bility, Proceedings of the American Mathematical Society 137 (2009), 3235–3246. 2 21

    work page 2009