Sortable simplicial complexes and $t$-independence ideals of proper interval graphs

Fahimeh Khosh-Ahang; J\"urgen Herzog; Masoomeh Rahimbeigi; Somayeh Moradi

REVIEW 1 major objections 4 minor 16 references

Sortable simplicial complexes and $t$-independence ideals of proper interval graphs

T0 review · 1 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The independence complex of a graph is sortable precisely for proper interval graphs, and this forces strong persistence and linear quotients for t-independence ideals.

desk verdict The sortability characterization of proper interval graphs is genuinely new and the proof of linear quotients checks out; the strong-persistence corollary has a small unstated field-hypothesis issue. read the letter →

arxiv 1908.07179 v1 pith:AQ3KGDRW submitted 2019-08-20 math.AC

Jürgen Herzog , Fahimeh Khosh-Ahang , Somayeh Moradi , Masoomeh Rahimbeigi This is my paper · ORCID

classification math.AC MSC 13F2005E4513H10

keywords properintervalgraphsortablesimplicialcomplext-sortabilityt-independenceidealstrongpersistencepropertylinearquotientsKoszulalgebramonomial

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper introduces a combinatorial sorting operation on the faces of a simplicial complex and defines a complex to be sortable when sorting any two faces produces two faces again. Its central result is that the independence complex of a graph is sortable, under some labeling of the vertices, exactly when the graph is a proper interval graph. This graph-theoretic characterization is then used to prove algebraic facts about the t-independence ideal generated by monomials attached to t-vertex independent sets: for proper interval graphs the ideal has the strong persistence property and every power has linear quotients, hence linear resolutions. The interest is that few general families of monomial ideals are known to have strong persistence, and this paper supplies one tied to a recognizable graph class.

What carries the argument

The sorting operator is the central object: given two faces $F$ and $G$ of a complex, one forms the product monomial $x_F x_G$, writes it with variables in increasing order, and returns the two faces made from the odd-position and even-position variables. A complex is sortable when this operation never leaves the complex, and $t$-sortable when the condition is required only for pairs of faces of size $t$. The algebraic half runs through the sorting relations $y_u y_v - y_{u'} y_{v'}$ attached to unsorted pairs; the paper uses the theorem that, for a sortable monomial ideal, these relations form a Gröbner basis of the defining ideal of the fiber ring with respect to a sorting order, together with the $\ell$-exchange property, to transfer the combinatorial sorting condition into linear-quotient and persistence statements.

What would settle it

Run an exhaustive search over all graphs on, say, six vertices: test whether sorting closure holds for every labeling of the independence complex and compare with the proper interval graph property from Lemma 1.7(v); any graph whose independence complex is sortable but which is not a proper interval graph would refute Theorem 1.8. Equivalently, find a pair of faces in a non-proper interval graph whose sorted pair contains an edge under every labeling.

Watch

Extended reading notes

Core claim

On the graph-theoretic side, the paper proves (Theorem 1.8) that $\Delta(G)$ is sortable if and only if $G$ is a proper interval graph, where sorting pairs two faces by writing the multiset union in increasing order and splitting it into odd and even positions. It also proves that every cycle graph is $t$-sortable for every $t$, though cycles are not sortable. On the algebraic side, for any proper interval graph and any $t \geq 2$, the $t$-independence ideal $I_t(G)$ satisfies the $\ell$-exchange property, satisfies strong persistence, and each power $I_t(G)^m$ has linear quotients; in addition the fiber ring $K[u : u \in \mathcal{G}(I_t(G))]$ is Koszul and a normal Cohen-Macaulay domain. A corollary is that a forest has sortable independence complex exactly when every component is a path.

Load-bearing premise

The chain from sortability to strong persistence and linear quotients depends on the imported theorem that, for a sortable monomial ideal, the sorting relations form a Gröbner basis of the defining ideal of the fiber ring under the sorting order; the paper quotes it rather than proving it, and Corollary 2.6 additionally uses a normality-to-strong-persistence criterion that assumes an infinite field.

Editorial extensions

If this is right

If $G$ is a proper interval graph, then its $t$-independence ideal $I_t(G)$ (for $t \geq 2$) has the strong persistence property, so $\operatorname{Ass}(I_t(G)^k) \subseteq \operatorname{Ass}(I_t(G)^{k+1})$ for all $k$.
Every power $I_t(G)^m$ has linear quotients with respect to the lex order, and therefore has a linear resolution.
The fiber ring of $I_t(G)$ is Koszul, normal, and Cohen-Macaulay; the same holds for $t$-independence ideals of cycle graphs because cycles are $t$-sortable.
A forest has sortable independence complex exactly when it is a disjoint union of paths; a tree is sortable exactly when it is a path.
The sortability characterization gives a new graph-theoretic recognition principle for proper interval graphs: checking that the sorting operation closes on the independence complex.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Not pursued in the paper: the sortability criterion might be turned into an algorithmic recognition test for unit interval graphs, since sorting closure can be checked locally on pairs of faces.
The $t$-sortability notion is weaker and applies to cycles, so it may cover further graph classes whose $t$-independence ideals still have Koszul fiber rings; identifying those classes is a natural next step.
Because the strong-persistence conclusion for proper interval graphs passes through normality of the Rees ring, testing whether non-proper interval graphs fail linear quotients for some $t$ would sharpen the boundary of the algebraic theorem.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The thing to know about this paper is that it earns its main claim. The notion of a sortable simplicial complex is new, and Theorem 1.8—independence complex sortable iff proper interval graph—is a real characterization, not present in the cited literature. The proof is short and sound, building on the known graph-theoretic conditions in Lemma 1.7 and a clean sorting argument. That alone is worth the read.

The algebraic half is mostly solid. The t-independence ideals of proper interval graphs get an ℓ-exchange property (Proposition 2.4) and all powers are shown to have linear quotients (Theorem 2.7). I checked the minimal-generator argument and the exchange step; the pigeonhole contradiction is valid and uses the clique-interval property appropriately. The linear-quotients proof is also coherent. So the paper's central results stand.

The soft spots are minor but real. Corollary 2.6 states strong persistence for arbitrary fields, but the proof invokes [8, Corollary 1.6], which—as the paper itself notes two paragraphs earlier—requires K infinite. For finite fields, the statement is unsupported as written. This is a genuine gap, not an internal contradiction, and likely fixable: either state the infinite-field hypothesis or give a descent argument for the monomial equality I^{k+1}:I = I^k. The other issue is Remark 1.6's CoCoA computation, which is not reproducible from the paper; it's an aside, so only mildly annoying.

One thing to keep in mind: Theorem 2.1, the Gröbner-basis result for sorting relations, is imported from Ene–Herzog without proof. That is standard for a paper in this area, but the algebraic results depend on it, so the reader should know the algebraic half rests on that external theorem. The combinatorial half is self-contained.

This paper is for combinatorial commutative algebraists looking at independence complexes, t-independence ideals, and powers with linear resolutions. It deserves a serious referee—the novel characterization and the linear-quotients results are important enough. The referee should ask for a fix to Corollary 2.6 and a small tightening of the field hypothesis.

Referee Report

1 major / 4 minor

Summary. The paper introduces a notion of sortability for simplicial complexes and proves that the independence complex of a graph is sortable if and only if the graph is a proper interval graph (Theorem 1.8). It then studies the t-independence ideals I_t(G) of proper interval graphs, showing that they satisfy the ℓ-exchange property (Proposition 2.4), that their Rees rings have a quadratic Gröbner basis (Theorem 2.5), and consequently that the ideals have the strong persistence property and all their powers have linear resolutions (Corollary 2.6) and linear quotients (Theorem 2.7). It also proves that the independence complexes of cycle graphs are t-sortable for all t, and that the corresponding toric rings are Koszul and normal Cohen–Macaulay (Corollary 2.2).

Significance. If the results hold, the paper makes a clean contribution: it gives a new combinatorial characterization of proper interval graphs via a sorting operation on faces, and it provides a new family of ideals with strong persistence and linear quotients. The proof of Theorem 1.8 is direct and convincing, and the linear-quotients argument in Theorem 2.7 is essentially self-contained, using the clique-interval property in a nice pigeonhole argument. The algebraic half, however, rests on substantial imported Gröbner-basis results (Theorem 2.1 from Ene–Herzog, and the normality/Cohen–Macaulay implication from [8]), and one of the headline claims, strong persistence, is stated without a field hypothesis that the cited theorem requires. This is a genuine but local gap that a revision can fix.

major comments (1)

[Section 2, paragraph before Corollary 2.6 and Corollary 2.6] Corollary 2.6 states that for every proper interval graph G and every t ≥ 2, the ideal I_t(G) satisfies the strong persistence property, with no hypothesis on the field K. The proof invokes [8, Corollary 1.6], but the manuscript itself notes immediately before the corollary that this implication from normality/Cohen–Macaulayness to strong persistence holds 'under the assumption that K is infinite.' Since no alternative argument is provided for finite fields, the strong-persistence claim as stated is unsupported. Please either add 'K infinite' to the hypotheses of Corollary 2.6 or supply a field-descent argument showing that the monomial equality I^{k+1}:I = I^k, which characterizes strong persistence, descends from an infinite extension to K.

minor comments (4)

[Theorem 2.7 proof] The phrase 'Let i_{s,k} be the smallest index such that i_{s,k} ≠ i'_{s,k}' is ambiguous: it should say the first position in the linear order of the sorted entries (equivalently, the lexicographically first pair (s,k)), not the smallest numerical vertex label. The subsequent reasoning is correct once this order is specified.
[Theorem 2.7 proof] In the argument that S is independent, the case s = t is not explicitly addressed. If s = t, then S is exactly the column of u', so the claim follows immediately; spelling this out would improve clarity.
[Corollary 2.6] The corollary calls I_t(G) the 'independence ideal' while the rest of the paper uses 't-independence ideal'; please make the terminology consistent.
[Proposition 1.4 proof] The parity-sensitive interleaving of the two blocks in the join is terse. A short sentence explaining that an odd-length first block shifts the parity of the second block would help the reader verify the formula.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the sortability characterization and the t-independence ideal results are derived from independent combinatorial and standard Groebner-basis theorems; the only flagged defect is an omitted field hypothesis in Corollary 2.6, which is a correctness gap rather than a circular reduction.

full rationale

The paper's central theorem, Theorem 1.8, equates sortability of the independence complex with being a proper interval graph. The notion of sortability is defined directly in terms of a sorting operator on faces, and the proof uses the independent graph-theoretic characterization in Lemma 1.7, quoted from Looges and Olariu [11], together with a direct combinatorial argument. No fitted parameter, normalization, or prior result of the same paper is assumed as input, so this part is self-contained and non-circular. The algebraic half uses standard imported results: Theorem 2.1 is the known Groebner basis theorem for sortable monomial ideals from Ene and Herzog [3]; Theorem 2.5 is the fiber-type presentation theorem of Herzog, Hibi, and Vladoiu [7]; and Corollary 2.2 applies Sturmfels's normality criterion and Hochster's Cohen-Macaulay theorem. These are independent of the paper's target claims. The paper's Theorem 2.7 is proved directly from the proper interval property and the explicit sorted generating set of powers. The only noteworthy issue is that Corollary 2.6 invokes [8, Corollary 1.6] without stating its infinite-field hypothesis, even though the paragraph before it explicitly says that the implication from normality/Cohen-Macaulayness to strong persistence requires the field K to be infinite. That is a missing or understated assumption in the statement of a headline result, not a circular derivation: the cited theorem is a general algebraic result whose assumptions do not include the target claims about t-independence ideals. Because no prediction or conclusion is shown to be equivalent by construction to its own inputs, the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 1 invented entities

No free parameters: this is a pure combinatorial and algebraic paper, with no numerical fitting. The new notion 'sortable' is a definition, not an unexplained entity, and it is pinned down by an external graph class. The proof relies on several standard external theorems, listed in the axioms, which are cited from the literature rather than derived in this paper.

assumptions (5)

standard math Proper interval graphs are exactly those admitting a vertex labeling satisfying condition (i) of Lemma 1.7: for all i<j, {i,j} in E(G) implies the induced subgraph on {i,...,j} is a clique.
Used in Lemma 1.7 and Theorem 1.8 without proof; cited from Looges and Olariu [11, Theorem 1 and Proposition 1].
standard math For a sortable monomial ideal, the sorting relations form a Gröbner basis of the defining ideal of the fiber ring with respect to the sorting order (Theorem 2.1).
Quoted from Ene and Herzog [3]; underpins Corollary 2.2 and the standard monomial characterization in Proposition 2.4.
standard math If a monomial ideal satisfies the ℓ-exchange property, its Rees ring has a presentation with a reduced Gröbner basis formed by the fiber Gröbner basis plus certain exchange binomials (Theorem 2.5).
Quoted from Herzog, Hibi and Vladoiu [7, Theorem 5.1]; used to control the Rees ring and powers.
standard math A toric ring with squarefree initial ideal is normal (Sturmfels), and a normal toric ring is Cohen-Macaulay (Hochster).
Used in Corollary 2.2 and Corollary 2.6 to deduce normality and Cohen-Macaulayness of fiber and Rees rings.
standard math If the Rees ring R(I) is normal or Cohen-Macaulay and K is infinite, then I satisfies the strong persistence property ([8, Corollary 1.6]).
Used in Corollary 2.6 to conclude strong persistence; the corollary does not restate the infinite field requirement.

invented entities (1)

Sortable simplicial complex independent evidence
purpose: A combinatorial condition on a simplicial complex that is proved to characterize independence complexes of proper interval graphs, and that triggers algebraic consequences such as the strong persistence property and linear quotients for related ideals.
This is a new definition, not an unexplained postulate. It is characterized against the externally known class of proper interval graphs (Theorem 1.8), which provides independent evidence that the notion is meaningful.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Sortable simplicial complexes and $t$-independence ideals of proper interval graphs." pith.science (2026). https://pith.science/paper/AQ3KGDRW

@misc{pith2026190807179,
  author       = {Pith},
  title        = {Pith review of: Sortable simplicial complexes and $t$-independence ideals of proper interval graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AQ3KGDRW}},
  note         = {Machine review of arXiv:1908.07179}
}

abstract

We introduce the notion of sortability and $t$-sortability for a simplicial complex and study the graphs for which their independence complexes are either sortable or $t$-sortable. We show that the proper interval graphs are precisely the graphs whose independence complex is sortable. By using this characterization, we show that the ideal generated by all squarefree monomials corresponding to independent sets of vertices of $G$ of size $t$ (for a given positive integer $t$) has the strong persistence property, when $G$ is a proper interval graph. Moreover, all of its powers have linear quotients.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

[8]

Herzog and A

J. Herzog and A. Qureshi, Persistence and stability properties of powers of ideals , J. Pure and Appl. Alg. 219, (2015), 530–542

work page 2015
[1]

Bogart and D

K.P. Bogart and D. West, A short proof that ‘proper = unit’ , Discrete Mathematics, 201, no. 1, (1999), 21-23

work page 1999
[2]

Bruns and J

W. Bruns and J. Herzog, Cohen-Macaulay Rings, Cambridge Stud ies in advanced mathematics 39, Cambridge University Press, Cambridge, UK, 1998

work page 1998
[3]

Ene and J

V. Ene and J. Herzog, Gr¨ obner Bases in Commutative Algebra, A merican Mathematical Soc., (2011)

work page 2011
[4]

Gardi, The Roberts characterization of proper and unit interval gr aphs, Discrete Mathe- matics 307, no

F. Gardi, The Roberts characterization of proper and unit interval gr aphs, Discrete Mathe- matics 307, no. 22, (2007), 2906-2908

work page 2007
[5]

Herzog and T

J. Herzog and T. Hibi, Monomial ideals, Graduate Texts in Mathema tics. Springer, New York, 2010

work page 2010
[6]

Herzog, T

J. Herzog, T. Hibi and H. Ohsugi, Binomial ideals, Graduate Texts in Mathematics. Springer, New York, 2018. 9

work page 2018
[7]

Herzog, T

J. Herzog, T. Hibi and M. Vladoiu, Ideals of ﬁber type and polymatroids , Osaka J. Math. 42, (2005), 807–829

work page 2005

Show all 16 references

[9]

Herzog, A

J. Herzog, A. Rauf and M. Vladoiu, The stable set of associated prime ideals of a polymatroidal ideal, J. Algebraic Combinatorics, 37, no. 2, (2013), 289-312

2013
[10]

Khosh-Ahang and S

F. Khosh-Ahang and S. Moradi, Some algebraic properties of t-clique ideals , Communications in Algebra 47, (2019), 2870–2882

2019
[11]

Looges and S

P.J. Looges and S. Olariu, Optimal greedy algorithms for indiﬀerence graphs , Comput. Math. Appl. 25, (1993), 15–25

1993
[12]

Martinez-Bernal, S

J. Martinez-Bernal, S. Morey and R.H. Villarreal, Associated primes of powers of edge ideals , Collectanea Mathematica 63, no. 3, (2012), 361-374

2012
[13]

Moradi, t-clique ideal and t-independence ideal of a graph , Communications in Algebra 46, (2018), 3377–3387

S. Moradi, t-clique ideal and t-independence ideal of a graph , Communications in Algebra 46, (2018), 3377–3387

2018
[14]

Moradi, M

S. Moradi, M. Rahimbeigi, F. Khosh-Ahang and A. Soleyman Jahan , A family of monomial ideals with the persistence property , Journal of Algebra and its Applications, 18, No. 5, (2019) 1950093

2019
[15]

Roberts, Representations of indiﬀerence relations, Ph.D

F.S. Roberts, Representations of indiﬀerence relations, Ph.D. Thesis, Stanford University, Stanford, CA, 1968

1968
[16]

Sturmfels, Gr¨ obner bases and convex polytopes, America n Mathematical Society, 1996

B. Sturmfels, Gr¨ obner bases and convex polytopes, America n Mathematical Society, 1996. J¨urgen Herzog, F achbereich Mathematik, Universit ¨at Duisburg-Essen, Campus Essen, 45117 Essen, Germany E-mail address : juergen.herzog@uni-essen.de F ahimeh Khosh-Ahang, Department of ...

1996

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [8]

Herzog and A

J. Herzog and A. Qureshi, Persistence and stability properties of powers of ideals , J. Pure and Appl. Alg. 219, (2015), 530–542

work page 2015

[2] [1]

Bogart and D

K.P. Bogart and D. West, A short proof that ‘proper = unit’ , Discrete Mathematics, 201, no. 1, (1999), 21-23

work page 1999

[3] [2]

Bruns and J

W. Bruns and J. Herzog, Cohen-Macaulay Rings, Cambridge Stud ies in advanced mathematics 39, Cambridge University Press, Cambridge, UK, 1998

work page 1998

[4] [3]

Ene and J

V. Ene and J. Herzog, Gr¨ obner Bases in Commutative Algebra, A merican Mathematical Soc., (2011)

work page 2011

[5] [4]

Gardi, The Roberts characterization of proper and unit interval gr aphs, Discrete Mathe- matics 307, no

F. Gardi, The Roberts characterization of proper and unit interval gr aphs, Discrete Mathe- matics 307, no. 22, (2007), 2906-2908

work page 2007

[6] [5]

Herzog and T

J. Herzog and T. Hibi, Monomial ideals, Graduate Texts in Mathema tics. Springer, New York, 2010

work page 2010

[7] [6]

Herzog, T

J. Herzog, T. Hibi and H. Ohsugi, Binomial ideals, Graduate Texts in Mathematics. Springer, New York, 2018. 9

work page 2018

[8] [7]

Herzog, T

J. Herzog, T. Hibi and M. Vladoiu, Ideals of ﬁber type and polymatroids , Osaka J. Math. 42, (2005), 807–829

work page 2005