Pith. sign in

REVIEW 3 major objections 4 minor 35 references

New Invariants for Permutations, Orders and Graphs

T0 review · 3 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 Applying the operator $\nabla$ at $q=1$ makes every graph's chromatic symmetric function Schur-positive and $e$-positive.

desk verdict The central theorem is unproven: Lemma 3.4's induction uses the false claim that ∇ at q=1 is multiplicative, though the underlying idea may be salvageable. read the letter →

arxiv 1908.04841 v1 pith:C53BN3DU submitted 2019-08-13 math.CO

Jean-christophe Aval , Nantel Bergeron , John Machacek This is my paper · ORCID
classification math.CO MSC 16T3005E0505E1505C15
keywords CombinatorialHopfalgebrachromaticsymmetricfunctionpositivelyh-alternatingSchurpositivitye-positivitynablaoperatorschedulingproblemsgraphcoloring
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 establishes a transfer principle: a symmetric function that is positively $h$-alternating—meaning its expansion in homogeneous symmetric functions has coefficients with sign $(-1)^{n-\ell(\lambda)}$—becomes $e$-positive and Schur positive after applying the operator $\nabla$ and setting $q=1$. The authors show that the chromatic symmetric function of every graph, the generating function of proper vertex colorings, has this property as a consequence of the classical power-sum expansion of chromatic symmetric functions. Consequently, for every graph $g$ on $n$ vertices, the specialization at $q=1$ of $\nabla\Psi_\bullet(g)$ expands with nonnegative coefficients in both the Schur basis and the elementary symmetric basis, and the coefficients are polynomials in $t$ with nonnegative integer entries. The same mechanism covers many other invariants built from Hopf-algebra characters on permutations, posets, and graphs, and the paper shows these invariants can all be expressed as scheduling problems.

What carries the argument

The load-bearing object is the family of operators $C_\alpha$ on symmetric functions and their specialization at $q=1$, where $(C_\alpha 1)|_{q=1}=(-1)^{|\alpha|-\ell(\alpha)}h_\alpha$ and the operators become multiplicative. Lemma 3.4 gives a Dyck-path formula for $\nabla(s_{k1^{n-k}})|_{q=1}$, writing the result as a weighted sum of $e_{\mathrm{type}(D)}$ over Dyck paths whose first component is at least $k$. The property of being positively $h$-alternating lets a symmetric function be assembled from these pieces, and multiplicativity of $\nabla$ at $q=1$ spreads the positivity to products. The classical power-sum expansion of the chromatic symmetric function is what supplies the $h$-alternating property for graphs.

What would settle it

Compute $(\nabla e_4)|_{q=1}$ directly from the defining eigendata of the operator, expand in the elementary symmetric basis, and compare with $\sum_{D\in\mathcal{D}_4} t^{\operatorname{area}(D)}e_{\operatorname{type}(D)}$; a single mismatched coefficient would invalidate Lemma 3.4 and the e-positivity theorem for all graphs.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.5: if $F\in\mathrm{Sym}_n$ is positively $h$-alternating, then $(\nabla F)|_{q=1}$ is $e$-positive and Schur positive. Because every graph's chromatic symmetric function is positively $h$-alternating, Corollary 3.6 follows: for any graph $g$ on $n$ vertices, $(\nabla\Psi_\bullet(g))|_{q=1}=\sum_{\lambda\vdash n} d_\lambda(t)s_\lambda=\sum_{\lambda\vdash n} d'_\lambda(t)e_\lambda$, where $d_\lambda(t)$ and $d'_\lambda(t)$ lie in $\mathbb{N}[t]$. The proof uses an explicit Dyck-path formula for $\nabla(s_{k1^{n-k}})$ at $q=1$, expressing it as a signed sum of weighted elementary symmetric functions indexed by Dyck paths; the base case is the shuffle-theorem identity for $\nabla e_n$. The paper also computes coefficient information: at $t=0$ the coefficient of $s_\lambda$ is $a(g)f^\lambda$, so the number of acyclic orientations of the graph appears naturally.

Load-bearing premise

The chain of argument assumes the cited identity that applying $\nabla$ to $e_n$ and setting $q=1$ gives the weighted sum of elementary symmetric functions over Dyck paths; this base case is imported from the shuffle-theorem literature and is not proved here, and the induction also relies on $\nabla$ being multiplicative at $q=1$.

Editorial extensions

If this is right

  • Every graph acquires a new symmetric-function invariant, $(\nabla\Psi_\bullet(g))|_{q=1}$, that is both Schur-positive and $e$-positive, so all its structure constants in these bases are nonnegative.
  • At $t=0$ the transformed invariant recovers $a(g)f^\lambda$, meaning the number of acyclic orientations and standard Young tableaux data are encoded at the leading specialization.
  • The same positivity argument applies to invariants from homogeneous Hopf-algebra characters: up to a global sign they are $\omega(p)$-positive, hence $h$-alternating, so after $\nabla$ at $q=1$ they are Schur-positive and $e$-positive.
  • Because all these invariants are scheduling problems, they inherit deletion-contraction laws in noncommuting variables and the geometric enumeration that comes with scheduling problems.

Reading between the lines

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

  • Because positive $h$-alternation is strictly weaker than $\omega(p)$-positivity, the mechanism suggests a route to $e$-positivity for symmetric functions that fail power-sum positivity, such as some hypergraph chromatic functions whose edges are all even and pairwise intersect oddly.
  • The Dyck-path formula hints at a parking-function model for the coefficients $d_\lambda(t)$, which could give a purely combinatorial description of the transformed chromatic symmetric function.
  • If the scheduling-problem viewpoint is combined with the coefficient formulas, the polynomials $d_\lambda(t)$ become candidates for unimodality or log-concavity questions, paralleling known results for chromatic polynomials.
  • The operator $\nabla$ at $q=1$ could be applied to any graph invariant for which $h$-alternation can be established, so the framework may extend to hypergraphs or simplicial complexes without passing through power-sum positivity.
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.

Referee Report

3 major / 4 minor

Summary. The paper studies symmetric-function invariants arising from combinatorial Hopf algebras (CHAs) on permutations, posets, and graphs. After setting up characters and the terminal CHA morphism Ψ, it introduces the property of being positively h-alternating, proves from Stanley's power-sum expansion that chromatic symmetric functions are positively h-alternating, and then claims that applying the operator ∇ at q=1 to any positively h-alternating symmetric function yields Schur-positive and e-positive results. The main application, Corollary 3.6, asserts that for every graph, (∇Ψ•(g))|q=1 has nonnegative Schur and elementary symmetric function expansions. The paper also studies the matching-based invariants Ψ21 and Ψ•−•, gives a p-basis expansion via a bond-type poset, proves p-positivity results for homogeneous characters, and relates the invariants to scheduling problems.

Significance. If the main theorem were established, it would be a striking and potentially important result: every graph's chromatic symmetric function would become Schur-positive and e-positive after a single application of ∇ at q=1, which would unify several known positivity phenomena and give a new family of graph invariants from the compositional shuffle theorem. The paper also provides a useful CHA framework connecting invariants on permutations, posets, and graphs, and the scheduling interpretation is attractive. The worked examples are consistent with the stated expansions, and the use of external theorems such as Stanley's power-sum expansion and the compositional shuffle theorem is a reasonable strategy. However, the proof of the central theorem currently contains a false multiplicativity claim, so the main claim is not established in this version.

major comments (3)
  1. [Section 3 (proof of Lemma 3.4, p. 19)] The induction proof of Lemma 3.4 relies on the assertion that "∇ at q = 1 is multiplicative," and this assertion is false. Take n=3 and k=2. Since C_{1,1,1}1 = h_1^3 and C_{2,1}1 = -h_1 h_2, we have h_1 e_2 = C_{1,1,1}1 + C_{2,1}1. By Theorem 3.1, ∇(h_1 e_2)|_{q=1} = e_{111} + t^2 e_{21}. On the other hand, ∇(h_1)|_{q=1} = e_1 and ∇(e_2)|_{q=1} = e_2 + t e_{11}, so (∇h_1)(∇e_2)|_{q=1} = e_{111} + t e_{21}. These differ, so the replacement of ∇(h_{k-1} e_{n-k+1}) by ∇(h_{k-1})∇(e_{n-k+1}) is invalid. The lemma may be true — the n=3, k=2 case is consistent with the shuffle theorem — but the proof as written does not establish it.
  2. [Section 3 (Theorem 3.5 and Corollary 3.6)] The proof of Theorem 3.5 uses the same false multiplicativity claim to pass from an h-alternating expansion F = Σ_λ c_λ (-1)^{n-ℓ(λ)} h_λ to ∇F = Σ_λ c_λ (-1)^{n-ℓ(λ)} ∏_i ∇(h_{λ_i}). Even if Lemma 3.4 were repaired, an independent argument would be needed to justify this distribution over products of h's. Without such an argument, the theorem that (∇F)|_{q=1} is e-positive and Schur positive for every positively h-alternating F does not follow from Lemma 3.4. Consequently Corollary 3.6, the central application to chromatic symmetric functions, is not supported by the current proof.
  3. [Section 3 (Proposition 3.8, p. 21)] The proof of Proposition 3.8 explicitly invokes "the fact that ∇(·)|_{q=1} is multiplicative." The same counterexample as above invalidates this step. As a result, Equation (11) and the three formulas for d_λ(0), d_(n)(t), and d_{1^n}(t) are not justified by the given argument. These formulas may be true, but they need a proof that does not rely on the false multiplicativity of ∇ at q=1.
minor comments (4)
  1. [Abstract] In the abstract, "positivelyh-alternating" is missing a space between "positively" and "h-alternating."
  2. [Section 3, opening paragraph] The sentence "we return to the more familiar case of the usual chromatic symmetric symmetric function" repeats the word "symmetric."
  3. [Section 2, Proposition 2.4 proof] The proof refers to "Equation 4.1 implies...," but the relevant displayed equation is (6); the cross-reference should be corrected.
  4. [Section 3, Lemma 3.4] The base case ∇(e_n)|_{q=1} = Σ_{D∈D_n} t^{area(D)} e_{type(D)} is cited as "well known (see [18])" without a precise theorem number; since this identity is load-bearing, a more specific reference would help the reader.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the main ∇-positivity claim rests on external theorems (Stanley, shuffle theorem, Carlsson–Mellit), not on a self-citation or fitted input; the suspicious multiplicativity step in Lemma 3.4 is a correctness gap, not a circular reduction.

full rationale

The paper's central derivation is not circular. The h-alternating property of chromatic symmetric functions (Cor. 1.15) follows from Stanley's power-sum expansion (Prop. 1.12) and a determinant identity, not from the conclusion. The transfer theorem (Thm. 3.5) and its graph corollary (Cor. 3.6) rest on Lemma 3.4, whose base case is explicitly cited to the external shuffle theorem [18] and whose induction is an attempted derivation; no quantity is fitted and the conclusion is not built into the definition of 'positively h-alternating.' Self-citations ([3], [5], [11], [25]) supply the CHA framework and context but are not used as the sole evidence for the positivity claims, which are supported by external results such as Stanley [30], Carlsson–Mellit [13], and Lenart [22]. The one serious concern is not circularity: Lemma 3.4's proof uses the assertion 'Since ∇ at q = 1 is multiplicative' and replaces ∇(h_{k−1}e_{n−k+1})|q=1 with ∇(h_{k−1})|q=1∇(e_{n−k+1})|q=1. This multiplicativity is not proven in the paper and appears to fail (e.g., by Theorem 3.1, ∇(h_1e_2)|q=1 ≠ ∇(h_1)|q=1∇(e_2)|q=1). That is a proof gap and a potential invalidity of the supplied derivation, but it is not a circular definition, a fitted input called a prediction, or a self-citation chain; it should be raised as a correctness objection, not as circularity. Score 2 reflects only the presence of minor, non-load-bearing self-citations in the framework sections.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central derivation is an honest transfer: h-alternation is established from Stanley's p-positivity, and ∇ at q=1 flips the alternating signs to positivity via Lemma 3.4. The ledger above collects the external theorems the paper relies on without proof; all are published results, but the ∇(e_n) q=1 identity is the specific entry point the new theorem hangs on. There are no fitted free parameters, and the only new mathematical objects (the h-alternating property and the ν function on the (•−•)-bond poset) are definitions inside proofs, not postulated entities with independent evidence.

assumptions (7)
  • standard math CHA terminal object theorem: for every CHA (H,ζ) there is a unique Hopf morphism Ψζ: H → QSym with ζ = φ1 ∘ Ψζ (Theorem 1.1, [3]).
    Foundational setup: this defines all the invariants Ψγ, ΨQ, Ψh studied in the paper; taken as background from the cited literature.
  • domain assumption Standard characters ζ1, ζ21, ζ_{•−•}, ζ_A defined on generators with no global ascents or splits determine the specific invariants.
    This is the paper's modeling choice: the results concern these particular invariants, and everything downstream, including which objects get e-positivity, depends on the characters chosen.
  • standard math Stanley's power-sum expansion Ψ•(g) = Σ_{Q∈L_g} μ(0,Q) p_{λ(Q)} (Proposition 1.12, [30]) and its consequence that ω(Ψ•(g)) is p-positive; Whitney's acyclic-orientation result [34].
    Load-bearing for Lemma 1.14, Corollary 1.15, and Proposition 3.8. External, published, and standard, but not proven in the paper.
  • standard math The shuffle theorem ∇(C_α 1) = Σ_{PF} t^{area} q^{dinv} F_{ides} (Theorem 3.1, [13]), and the q=1 specialization ∇(e_n)|q=1 = Σ_{D∈D_n} t^{area(D)} e_{type(D)} given as 'well known (see [18])'.
    The base case of Lemma 3.4 and the parking-function expression (11) in Proposition 3.8 both rest on this external theorem; the e-type summation over labelings is only cited, not proved in this paper.
  • standard math ∇ is an algebra automorphism of Sym, and at q=1 the plethystic shift in Cα vanishes so (C_α 1)|q=1 = (−1)^{|α|−l(α)} h_α (Eq. 8), and ∇|q=1 is multiplicative.
    Multiplicativity carries the h-alternating expansion term by term to the product of e-basis elements in Theorem 3.5.
  • standard math Lenart's theorem [22]: ∇(s_{λ/µ})|q=1 is Schur positive up to a global sign.
    Used for the Schur positivity half of Theorem 3.5 and cited without proof.
  • standard math Antipode formula S(g) = Σ_{F∈F(g)} (−1)^{c(F)} a(g/F) g|_{V,F} for the incidence Hopf algebra of graphs (Eq. 12, [21]).
    Load-bearing for the combinatorial reciprocity formula in Proposition 4.3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of New Invariants for Permutations, Orders and Graphs." pith.science (2026). https://pith.science/paper/C53BN3DU

@misc{pith2026190804841,
  author       = {Pith},
  title        = {Pith review of: New Invariants for Permutations, Orders and Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/C53BN3DU}},
  note         = {Machine review of arXiv:1908.04841}
}
abstract

We study the symmetric function and polynomial combinatorial invariants of Hopf algebras of permutations, posets and graphs. We investigate their properties and the relations among them. In particular, we show that the chromatic symmetric function and many other invariants have a property we call positively $h$-alternating. This property of positively $h$-alternating leads to Schur positivity and $e$-positivity when applying the operator $\nabla$ at $q=1$. We conclude by showing that the invariants we consider can be expressed as scheduling problems.

Figures

Figures reproduced from arXiv: 1908.04841 by the authors.

Figure 1
Figure 1. Example of (•−•)-bond poset every positive integer a we define an operator Ca on Sym by CaF[X] :=  −1 q a−1 F  1 − 1/q z X m≥0 z mhm[X] ! [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗
Figure 2
Figure 2. A parking function of size 8. The shuffle theorem gives a combinatorial interpretation of ∇en. A natural next step is to look for an understanding of ∇F given another symmetric function F. In this section we initiate the study of ∇Ψ•(g) for any graph g. The quantity ∇Ψ•(g) is a generalization of ∇en as Ψ•(g) = n!en when g is the complete graph on n vertices. Other symmetric functions which have been considered inclu… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 34 canonical work pages

  1. [1]

    Adiprasito, J

    K. Adiprasito, J. Huh, and E. Katz. Hodge theory for combinatorial geometries. Ann. of Math. (2), 188(2):381–452, 2018

    work page 2018

  2. [2]

    Aguiar and F

    M. Aguiar and F. Ardila. Hopf monoid of generalized permutahedra. arXiv:1709.07504. NEW INV ARIANTS FOR PERMUTATIONS, ORDERS AND GRAPHS 25

    arXiv

  3. [3]

    Aguiar, N

    M. Aguiar, N. Bergeron, and F. Sottile. Combinatorial Hopf algebras and generalized Dehn- Sommerville relations. Compositio Mathematica, 142:1–30, 1 2006

    work page 2006

  4. [4]

    Aguiar and S

    M. Aguiar and S. Mahajan. Monoidal functors, species and Hopf algebras , volume 29 of CRM Monograph Series. American Mathematical Society, Providence, RI, 2010

    work page 2010

  5. [5]

    Cancelation free formula for the antipode of linearized Hopf monoid

    C. Benedetti and N. Bergeron. The antipode of linearized Hopf monoids, 2016. arXiv:1611.01657

    work page Pith review arXiv 2016

  6. [6]

    Benedetti, N

    C. Benedetti, N. Bergeron, and J. Machacek. Hypergraphic polytopes: combinatorial properties and antipode. J. Comb., 2019. to appear

    work page 2019

  7. [7]

    Benedetti, J

    C. Benedetti, J. Hallam, and J. Machacek. Combinatorial Hopf algebras of simplicial complexes. SIAM Journal on Discrete Mathematics , 30(3):1737–1757, 2016

    work page 2016

  8. [8]

    Benedetti and B

    C. Benedetti and B. E. Sagan. Antipodes and involutions. J. Combin. Theory Ser. A, 148:275–315, 2017

    work page 2017

Show all 35 references
  1. [9]

    Bergeron and A

    F. Bergeron and A. M. Garsia. Science fiction and Macdonald’s polynomials. In Algebraic methods and q-special functions (Montr´ eal, QC, 1996), volume 22 of CRM Proc. Lecture Notes, pages 1–52. Amer. Math. Soc., Providence, RI, 1999

    1996

  2. [10]

    Bergeron, A

    F. Bergeron, A. M. Garsia, M. Haiman, and G. Tesler. Identities and positivity conjectures for some remarkable operators in the theory of symmetric functions. Methods Appl. Anal. , 6(3):363–420,

  3. [11]

    Bergeron, F

    N. Bergeron, F. Descouens, and M. Zabrocki. A filtration of ( q, t)-Catalan numbers. Adv. in Appl. Math., 44(1):16–36, 2010

    2010

  4. [12]

    Breuer and C

    F. Breuer and C. J. Klivans. Scheduling problems. J. Combin. Theory Ser. A , 139:59 – 79, 2016

    2016

  5. [13]

    Carlsson and A

    E. Carlsson and A. Mellit. A proof of the shuffle conjecture. J. Amer. Math. Soc. , 31(3):661–697, 2018

    2018

  6. [14]

    D. D. Gebhard and B. E. Sagan. A chromatic symmetric function in noncommuting variables. Journal of Algebraic Combinatorics , 13(3):227–255, May 2001

    2001

  7. [15]

    I. M. Gessel. Multipartite P -partitions and inner products of skew Schur functions. In Combina- torics and algebra (Boulder, Colo., 1983) , volume 34 of Contemp. Math. , pages 289–317. Amer. Math. Soc., Providence, RI, 1984

    1983

  8. [16]

    Gruji´ c and T

    V. Gruji´ c and T. Stojadinovi´ c. Hopf algebra of building sets. Electron. J. Combin. , 19(4):P42, 2012

    2012

  9. [17]

    Gruji´ c, T

    V. Gruji´ c, T. Stojadinovi´ c, and D. Joji´ c. Generalized Dehn–Sommerville relations for hypergraphs. European Journal of Mathematics , 2(2):459–473, 2016

    2016

  10. [18]

    Haglund, M

    J. Haglund, M. Haiman, N. Loehr, J. B. Remmel, and A. Ulyanov. A combinatorial formula for the character of the diagonal coinvariants. Duke Math. J. , 126(2):195–232, 2005

    2005

  11. [19]

    Haglund, J

    J. Haglund, J. Morse, and M. Zabrocki. A compositional shuffle conjecture specifying touch points of the Dyck path. Canad. J. Math. , 64(4):822–844, 2012

    2012

  12. [20]

    J. Huh. Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs. J. Amer. Math. Soc., 25(3):907–927, 2012

    2012

  13. [21]

    Humpert and J

    B. Humpert and J. L. Martin. The incidence Hopf algebra of graphs. SIAM Journal on Discrete Mathematics, 26(2):555–570, 2012

    2012

  14. [22]

    C. Lenart. Lagrange inversion and Schur functions. J. Algebraic Combin., 11(1):69–78, 2000

    2000

  15. [23]

    N. A. Loehr and G. S. Warrington. Square q, t-lattice paths and∇(pn). Trans. Amer. Math. Soc., 359(2):649–669, 2007

    2007

  16. [24]

    N. A. Loehr and G. S. Warrington. Nested quantum Dyck paths and ∇(sλ). Int. Math. Res. Not. IMRN, (5):Art. ID rnm 157, 29, 2008

    2008

  17. [25]

    Machacek

    J. Machacek. Plurigraph coloring and scheduling problems. Electron. J. Combin., 24(2):Paper 2.29, 2017

    2017

  18. [26]

    E. Sergel. A combinatorial model for ∇mµ. arXiv:1804.06037

    arXiv

  19. [27]

    E. Sergel. The combinatorics of nabla pn and connections to the rational shuffle conjecture . Pro- Quest LLC, Ann Arbor, MI, 2016. Thesis (Ph.D.)–University of California, San Diego

    2016

  20. [28]

    E. Sergel. A proof of the square paths conjecture. J. Combin. Theory Ser. A , 152:363–379, 2017

    2017

  21. [29]

    R. P. Stanley. Acyclic orientations of graphs. Discrete Mathematics, 5(2):171 – 178, 1973. 26 JEAN-CHRISTOPHE A V AL, NANTEL BERGERON, AND JOHN MACHACEK

    1973

  22. [30]

    R. P. Stanley. A symmetric function generalization of the chromatic polynomial of a graph. Adv. Math., 111(1):166–194, 1995

    1995

  23. [31]

    R. P. Stanley. Graph colorings and related symmetric functions: ideas and applications: a descrip- tion of results, interesting applications, & notable open problems. Discrete Math., 193(1-3):267– 286, 1998. Selected papers in honor of Adriano Garsia (Taormina, 1994)

    1998

  24. [32]

    R. P. Stanley and J. R. Stembridge. On immanants of Jacobi-Trudi matrices and permutations with restricted position. J. Combin. Theory Ser. A , 62(2):261–279, 1993

    1993

  25. [33]

    Takeuchi

    M. Takeuchi. Free Hopf algebras generated by coalgebras. J. Math. Soc. Japan , 23:561–582, 1971

    1971

  26. [34]

    H. Whitney. A logical expansion in mathematics. Bull. Amer. Math. Soc. , 38(8):572–579, 1932. (Aval) LaBRI, CNRS, Universit de Bordeaux, FRANCE E-mail address : aval@labri.fr (Bergeron) Department of Mathematics and Statistics, York University, Toronto, Ontario M3J 1P3, CANADA...

    1932

  27. [1999]

    Askey on the occasion of his 65th birthday, Part III

    Dedicated to Richard A. Askey on the occasion of his 65th birthday, Part III

Pith tools

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