The connection between the chromatic function and the Redei-Berge function

Stefan Mitrovi\'c; Tanja Stojadinovi\'c

REVIEW 3 major objections 4 minor 23 references

The connection between the chromatic function and the Redei-Berge function

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read For every finite poset $P$, the noncommutative chromatic symmetric function of its incomparability graph is exactly the $\omega$-dual of the noncommutative Redei-Berge function of its poset digraph: $Y_{\operatorname{inc}(P)} =…

desk verdict The noncommutative bridge Y_inc(P)=omega(W_P) is a genuine, likely correct unification, but Section 4 contains false Hamiltonian-cycle claims that must be fixed. read the letter →

arxiv 2506.08841 v1 pith:4PQKHVAW submitted 2025-06-10 math.CO

Stefan Mitrović , Tanja Stojadinović This is my paper

classification math.CO MSC 05E0505C2005C3106A07

keywords chromaticsymmetricfunctionRedei-Bergenoncommutativefunctionsposetsincomparabilitygraphsdeletion-contractionStanley-Stembridgeconjecturebagsofsticks

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

Every finite poset defines two objects at once: an incomparability graph and a digraph of its strict order. This paper proves that the two colour-counting functions attached to those objects---the chromatic symmetric function and the Redei-Berge function---are the same up to the omega involution, and that the identity is already visible at the noncommutative level, where deletion-contraction arguments become available. Through this bridge the authors translate results in both directions: known facts about chromatic functions become theorems about Redei-Berge functions, and vice versa. The payoff includes a converse of Redei's theorem, a multipartite distinguishability result, a generalized triple deletion property, and a restatement of the Stanley-Stembridge positivity conjecture as $h$-positivity of Redei-Berge functions.

What carries the argument

The machinery is the pair of deletion-contraction identities for noncommutative functions, together with the raising operation $f\uparrow$ that squares the last variable. For graphs, $Y_G = Y_{G\setminus e} - Y_{G/e}\uparrow$ for the distinguished edge $e=\{v_{n-1},v_n\}$; for digraphs, $W_X = W_{X\setminus e} - W_{X/e}\uparrow$ for $e=(v_{n-1},v_n)$. The key lemma $\omega(f\uparrow) = -\omega(f)\uparrow$ turns the subtracted contracted term into exactly the term appearing in the chromatic deletion-contraction identity. The induction pairs poset coverings with graph edges: deleting a covering from the poset adds the corresponding incomparability edge, and contracting it is the same as contracting that edge in the graph, which lets the two ordinary functions of the induction match.

What would settle it

Take a small poset with a covering edge $e=(v_{n-1},v_n)$, such as the three-element chain, and expand $W_P$, $W_{P\setminus e}$, and $W_{P/e}\uparrow$ in the noncommuting monomial basis. If $W_P \neq W_{P\setminus e} - W_{P/e}\uparrow$ on any monomial, Theorem 5.7 is false; agreement across all small posets would confirm the induction.

Watch

Extended reading notes

Core claim

The central claim is Theorem 5.7: if $P$ is a finite poset with labeled vertices $v_1,\dots,v_n$, then $Y_{\operatorname{inc}(P)} = \omega(W_P)$, where $Y$ is the noncommutative chromatic symmetric function of the incomparability graph $\operatorname{inc}(P)$, $W_P$ is the noncommutative Redei-Berge function of the digraph whose edges are the strict order relations of $P$, and $\omega$ is the involution interchanging noncommutative elementary and complete homogeneous basis elements. The proof is an induction on the number of comparable pairs: choosing a covering edge $e=(v_{n-1},v_n)$, the deletion-contraction identities for $Y$ and $W$ reduce the statement to smaller posets, and Lemma 5.6 shows that deleting $e$ from the poset adds the edge to $\operatorname{inc}(P)$ while contracting it contracts the graph edge. Once the noncommutative identity is established, letting the variables commute immediately yields $X_{\operatorname{inc}(P)} = \omega(U_P)$ for the ordinary functions, recovering and reproving the commutative connection of Section 3. The paper presents the bridge as a general translation device: properties of $X_G$ that survive the $\omega$-substitution become properties of $U_P$, and the noncommutative setting supplies computational tools that the commutative functions lack.

Load-bearing premise

The bridge stands or falls on a deletion-contraction rule for the noncommutative Redei-Berge function, which the paper takes from a cited companion without proving it here; if that rule fails on digraphs coming from posets, the main theorem collapses.

Editorial extensions

If this is right

Letting the variables commute in Theorem 5.7 recovers $X_{\operatorname{inc}(P)} = \omega(U_P)$, so any coefficient identity or positivity statement proved for either function transfers to the other.
Redei's theorem is turned into an if-and-only-if statement: a poset is a chain exactly when it has an odd number of quasi-linear extensions, while every non-chain has an even number.
The bridge distinguishes complete multipartite graphs: if two complete $k$- and $\ell$-partite graphs have the same chromatic symmetric function, they are isomorphic.
The Stanley-Stembridge conjecture is equivalent to $h$-positivity of $U_P$ for $(3+1)$-free posets, and $U_P$ is already $s$-positive in that case.
A generalized triple deletion holds: if $v$ covers $u_1,\dots,u_k$ in $P$ and $F=\{\{u_i,v\}\}$, then $Y_{\operatorname{inc}(P)} = \sum_{S\subseteq F} (-1)^{|S|-1} Y_{\operatorname{inc}(P)\cup S}$, with the same formula for $X$.

Reading between the lines

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

Editorial extension: since $W_X$ is defined for every labeled digraph, the same kind of identity could be sought for graphs that are not incomparability graphs of posets, choosing a digraph whose deletion-contraction tree is simpler and carrying the result back to $Y$.
Editorial extension: the equivalence with $h$-positivity suggests a computational search over unit interval orders: expand $W_P$ in the complete-homogeneous basis by deleting and contracting non-covering edges of $D_P$, which leave the poset category but remain valid digraphs, and check whether the coefficients stay nonnegative.
Editorial extension: the bag-of-sticks decomposition expresses $X_{\operatorname{inc}(P)}$ as a signed sum over minimal elements of the edge poset, so computing the chain sums $\xi([S,E])$ for unit interval orders could localize where $e$-positivity would fail, if it fails.
Editorial extension: the identity $\omega(f\uparrow) = -\omega(f)\uparrow$ is a self-contained calculus that may transfer the same bridge to other deletion-contraction invariants with a raising rule, such as quasisymmetric chromatic functions.

Share X Bluesky LinkedIn Reddit HN

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 real content here is Theorem 5.7: for a poset P, the noncommutative chromatic symmetric function of the incomparability graph is the omega-dual of the noncommutative Redei-Berge function of the poset digraph. That identity looks right to me. The induction is coherent: the base case is exact, the deletion-contraction steps respect the poset structure when the chosen edge is a covering, and Lemma 5.6 supplies the needed graph-level translation. The cited deletion-contraction for W_X (Theorem 5.5, from the first author's earlier paper) is not reproved, but it is stated for arbitrary labeled digraphs and is used here only for coverings, so this is a verification gap rather than an error. The paper deserves credit for what follows from the bridge: the clean proof of the commutative identity X_inc(P)=omega(U_P), the translation of e-positivity questions into h-positivity for the Redei-Berge function, the generalized triple deletion property, and the bag-of-sticks coefficient formulas. Those are genuinely new and useful.

The soft spots are real, but they are concentrated in Section 4. D_P is acyclic by definition - edges go from smaller to larger elements in the poset - so Theorem 4.6's claim that D_P has a Hamiltonian cycle iff P is irreducible cannot be true as written. The same problem infects Theorem 4.8: the right-hand side counts permutations whose nontrivial cycles are cycles of D_P, but D_P has no nontrivial directed cycles, so the claimed equality with broken-cycle subsets of inc(P) is not a meaningful statement in the way the paper presents it. The reader's stress-test note is right that none of this feeds into the proof of Theorem 5.7 - Section 4 is illustrative, not load-bearing - but the errors are concrete and would mislead a reader. They need to be fixed before publication: either drop the Hamiltonian-cycle language and count what is actually counted (cycles in the complement digraph, or acyclic path covers), or restrict the claims to a class of digraphs where cycles can exist.

The citation pattern is mostly healthy: the commutative identity is explicitly credited to Chow, and the main new result is the noncommutative one. The heavy reliance on the authors' own prior theorems is acceptable because those theorems are separate, independently stated results, not restatements of the target identity.

Who is this for? Anyone working in algebraic combinatorics on chromatic symmetric functions or Redei-Berge functions will want this bridge. It does not resolve Stanley-Stembridge, but it gives a new angle and some handy computational tools. I would cite the noncommutative identity if I worked in the area.

Recommendation: send it to peer review. The central theorem is solid and interesting, but Section 4 needs a serious revision before acceptance. A good referee can verify the induction and force the Section 4 corrections.

Referee Report

3 major / 4 minor

Summary. The paper proves that for a finite poset P, the noncommutative chromatic symmetric function of its incomparability graph equals the omega-dual of the noncommutative Redei-Berge function of the associated acyclic digraph D_P (Theorem 5.7), thereby recovering the commutative identity X_inc(P) = omega(U_P). The authors use this bridge to translate distinguishability, basis, and positivity results between the chromatic and Redei-Berge settings, and they develop a decomposition into bags of sticks that yields a generalization of the triple deletion property.

Significance. If the central theorem stands, the paper provides a clean inductive proof of the commutative relationship and a transfer principle that yields new results, including a formulation of the Stanley-Stembridge conjecture in terms of h-positivity of U_P and explicit formulas for bags of sticks. The noncommutative approach is a genuine contribution. However, Section 4 as written contains false Hamiltonian-cycle assertions that must be corrected before the paper can be accepted; these errors are not central to Theorem 5.7 but are part of the paper's claimed results.

major comments (3)

[Section 4, Theorem 4.6] The statement that D_P contains a Hamiltonian cycle if and only if P is irreducible is false, because D_P is defined by strict order relations and is therefore acyclic for every poset P. For |P| >= 2, D_P has no directed cycles at all. The proof's identification of [p_n]U_P with the number of Hamiltonian cycles of D_P contradicts Theorem 2.2; in the expansion U_{D_P} = sum_{pi in S_V(D_P, overline{D_P})} ..., any n-cycle counted in [p_n] must be a cycle of the complement overline{D_P}, not of D_P. The theorem should be reformulated for overline{D_P} or with the correct permutation set, and the subsequent discussion of bases should be adjusted accordingly.
[Section 4, Theorem 4.8] The right-hand side #{pi in S_V(D_P) : type(pi) = lambda} is zero whenever lambda has a part larger than 1, since D_P is acyclic, whereas the left-hand side is generally nonzero; for lambda = (2,1^{n-2}) it counts incomparable pairs, which can be positive. The correct set is S_V(D_P, overline{D_P}) as in Theorem 2.2, with nontrivial cycles taken in overline{D_P}. This is not a minor typo, because the equality is the stated combinatorial connection between broken circuits and permutations.
[Section 5, Theorem 5.7] The induction proving the central identity depends entirely on the deletion-contraction identity for W_X stated as Theorem 5.5 and quoted from [14]. Since this identity is the engine of the central proof and is used here for the specific digraphs D_P, D_{P\e}, and D_{P/e}, the paper should either reproduce the proof of Theorem 5.5 or give a self-contained verification for the covering-edge case, so that the reader can check that the contraction convention used for posets matches the one in Theorem 5.5.

minor comments (4)

[Section 4, after Corollary 4.5] The sentence 'If P is a poset, then D_P does not contain any non trivial cycle. Therefore, if (P_n) is a list of posets such that P_n has n elements and D_{P_n} has at least one Hamiltonian cycle...' is internally inconsistent, since the stated hypothesis can never be satisfied; it should likely refer to the complement digraph overline{D_{P_n}}.
[Section 5, proof of Theorem 5.7] In the last displayed equation of the proof, the equality 'Y_{(inc(P) union e)/e} = Y_{inc(P)}' appears to contain a typo; it should read 'Y_{(inc(P) union e)\e} = Y_{inc(P)}', matching the deletion-contraction identity.
[Section 6, Theorem 6.5] The function f is defined on [n-2] with values in [n-1], but the condition is stated 'for every i in [n-1]'; the intended range is i in [n-2], and the statement should be corrected accordingly.
[Section 4, proof of Theorem 4.8] The proof uses the notation S_V(D_P) as though it included permutations whose cycles are cycles of the complement; the notation should be made consistent with the definitions in Section 2, where S_V(X) and S_V(X, overline{X}) are distinct sets.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity identified: the central bridge Y_inc(P)=omega(W_P) is derived from independent deletion-contraction theorems, not from its own conclusion.

full rationale

No circular step is exhibited. Theorem 5.7 is proved by induction whose base cases are exact (Examples 5.2 and 5.4) and whose induction step applies the prior deletion-contraction theorems Theorem 5.3 (Gebhard-Sagan) and Theorem 5.5 (Mitrovic [14]) to the poset cover e=(v_{n-1},v_n), together with Lemma 5.6 relating inc(P\e), inc(P/e), and inc(P) union e. The quantity proved, Y_inc(P)=omega(W_P), is not used as an input anywhere in those cited theorems, and neither antecedent assumes the target identity; Theorem 5.5 is a parameter-free statement about arbitrary labeled digraphs, so citing it is real evidence rather than a circular self-citation. The commutative identity Theorem 3.2 follows directly from the descent-set definitions and the involution omega, not from a fitted parameter. Sections 6 and 7 translate known positivity and decomposition results via Theorem 3.2/5.7; no quantity is fitted and then renamed a prediction. The false Hamiltonian-cycle assertions in Section 4 are mathematical errors independent of the central derivation and do not feed into Theorem 5.7; they are a correctness concern, not a circularity concern. The derivation chain is self-contained up to the cited antecedents, so the circularity score is 0.

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

The central claim rests on two imported deletion-contraction theorems and standard symmetric function machinery. No free parameters are fitted. The paper introduces no unexplained entities; its 'bags of sticks' and edge poset are explicit mathematical constructions used as tools.

assumptions (3)

domain assumption The noncommutative Redei-Berge function satisfies a deletion-contraction identity for the distinguished edge (v_{n-1}, v_n): deleting the edge and subtracting the contracted graph with a raised last variable reproduces the original.
Theorem 5.5, imported from the first author's earlier preprint [14], is the engine of the induction in Theorem 5.7; the paper does not reprove it.
domain assumption The noncommutative chromatic function satisfies the Gebhard-Sagan deletion-contraction identity for the distinguished edge.
Theorem 5.3, imported from [9], is used in the same induction alongside Lemma 5.6.
standard math The omega automorphism and the raising operation satisfy Lemma 5.1: omega(f raised) equals minus omega(f) raised.
This is proved in the paper directly from the power-sum formula for the noncommutative omega automorphism and is needed for the induction step.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The connection between the chromatic function and the Redei-Berge function." pith.science (2026). https://pith.science/paper/4PQKHVAW

@misc{pith2026250608841,
  author       = {Pith},
  title        = {Pith review of: The connection between the chromatic function and the Redei-Berge function},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4PQKHVAW}},
  note         = {Machine review of arXiv:2506.08841}
}

read the original abstract

There is a natural way to assign both graph and digraph to every poset. Furthermore, any graph has its chromatic function, while any digraph has its Redei-Berge function. On the level of posets, these two functions are almost identical. Here, we prove that this connection is actually a reflection of the connection between the noncommutative generalizations of these two functions. The simplicity of this relationship enables us to easily translate the properties proved for one of them to the case of the other. We perform such conversions regarding distinguishability, decomposition techniques and positivity questions. Among others, we obtain the converse of Redei's theorem, generalization of the triple deletion property and expressions for these functions in some special cases.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

23 extracted references · 21 canonical work pages

[14]

The Redei-Berge function in noncommuting variables

S. Mitrovi´ c, The Redei-Berge function in noncommuting variables, accepted for FPSAC 2025,arXiv:2504.20968

work page Pith review arXiv 2025
[1]

Aguiar, N

M. Aguiar, N. Bergeron, F. Sottile, Combinatorial Hopf algebras and gen- eralized Dehn-Sommerville relations, Compos. Math. 142 (2006) 1-30

work page 2006
[2]

J. C. Aval, N. Bergeron, J. Machacek, New invariants for permutations, orders and graphs, Adv. Appl. Math. 121, (2020), 102080

work page 2020
[3]

Bergeron, M

N. Bergeron, M. Zabrocki. The Hopf algebras of symmetric functions and quasisymmetric functions in non-commutative variables are free and cofree, J. Algebra Appl. 8 (2009), 581–600

work page 2009
[4]

Berge, Graphs and Hypergraphs, North-Holland Mathematical Library 6, 2nd edition, North-Holland (1976)

C. Berge, Graphs and Hypergraphs, North-Holland Mathematical Library 6, 2nd edition, North-Holland (1976). 26

work page 1976
[5]

S. Cho, S. van Willigenburg, Chromatic bases for symmetric functions, Elec- tron. J. Combin. 23, 6pp. (2016)

work page 2016
[6]

Chow, Symmetric function generalizations of graph polynomials, Ph

T. Chow, Symmetric function generalizations of graph polynomials, Ph. D. Thesis, MIT, 1995

work page 1995
[7]

F. R. K. Chung and R. L. Graham, On the cover polynomial of a digraph, J. Combin. Theory Ser. B, 65(2):273–29, 1995

work page 1995

Show all 23 references

[8]

Gasharov, Incomparability graphs of (3 + 1)−free posets ares−positive, Discrete Math

V. Gasharov, Incomparability graphs of (3 + 1)−free posets ares−positive, Discrete Math. 157, 193-197 (1996)

1996
[9]

D. D. Gebhard, B. E. Sagan, A Noncommutative Chromatic Symmetric Function, J. Algebraic Combin. 13 (2001), 227–255

2001
[10]

Grinberg, R

D. Grinberg, R. Stanley, The Redei-Berge symmetric function of a directed graph,arXiv:2307.05569v1

arXiv
[11]

Gruji´ c, T

V. Gruji´ c, T. Stojadinovi´ c, The Redei-Berge Hopf algebra of digraphs, Period. Math. Hung. (2025). https://doi.org/10.1007/s10998-024-00619-9

2025 doi
[12]

Guay-Paquet, A modular relation for the chromatic symmetric functions of (3+ 1)-free posets,arXiv:1306.2400 (2013)

M. Guay-Paquet, A modular relation for the chromatic symmetric functions of (3+ 1)-free posets,arXiv:1306.2400 (2013)

2013 arXiv
[13]

Hikita, A proof of the Stanley-Stembridge conjecture,arXiv:: 2410.12758 (2024)

T. Hikita, A proof of the Stanley-Stembridge conjecture,arXiv:: 2410.12758 (2024)

2024
[15]

Mitrovi´ c, T

S. Mitrovi´ c, T. Stojadinovi´ c, Some properties of the Redei-Berge function and related combinatorial Hopf algebras,arXiv:2407.18608v3

arXiv
[16]

Orellana and G

R. Orellana and G. Scott, Graphs with equal chromatic symmetric function, Discrete Math. 320, 1-14 (2014)

2014
[17]

Redei, Ein kombinatorischer Satz, Acta Litteraria Szeged 7 (1934), 39- 43

L. Redei, Ein kombinatorischer Satz, Acta Litteraria Szeged 7 (1934), 39- 43

1934
[18]

M. H. Rosas, B. E. Sagan, Symmetric Functions in Noncommuting Vari- ables, Trans. Amer. Math. Soc., 358(1), 215–232
[19]

B. E. Sagan, F. Tom, Chromatic symmetric functions and change of basis, arXiv:2407.06155v1 (2024)

2024 arXiv
[20]

Scott and P

D. Scott and P. Suppes, Foundational aspects of theories of measurement, J. Symb. Logic 23 (1958), 113–128

1958
[21]

Stanley, Enumerative combinatorics

R. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Univ. Press, Cambridge, (1999) 27

1999
[22]

Stanley, A symmetric function generalization of the chromatic polyno- mial of a graph, Adv

R. Stanley, A symmetric function generalization of the chromatic polyno- mial of a graph, Adv. Math. 111, 166-194 (1995)

1995
[23]

Shareshian and M

J. Shareshian and M. Wachs, Chromatic quasisymmetric functions, Adv. Math. 295, 497-551 (2016). 8 Declarations and statements The authors declare that no funds, grants, or other support were received during the preparation of this manuscript. The authors have no relevant finan...

2016

Pith tools

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

[1] [14]

The Redei-Berge function in noncommuting variables

S. Mitrovi´ c, The Redei-Berge function in noncommuting variables, accepted for FPSAC 2025,arXiv:2504.20968

work page Pith review arXiv 2025

[2] [1]

Aguiar, N

M. Aguiar, N. Bergeron, F. Sottile, Combinatorial Hopf algebras and gen- eralized Dehn-Sommerville relations, Compos. Math. 142 (2006) 1-30

work page 2006

[3] [2]

J. C. Aval, N. Bergeron, J. Machacek, New invariants for permutations, orders and graphs, Adv. Appl. Math. 121, (2020), 102080

work page 2020

[4] [3]

Bergeron, M

N. Bergeron, M. Zabrocki. The Hopf algebras of symmetric functions and quasisymmetric functions in non-commutative variables are free and cofree, J. Algebra Appl. 8 (2009), 581–600

work page 2009

[5] [4]

Berge, Graphs and Hypergraphs, North-Holland Mathematical Library 6, 2nd edition, North-Holland (1976)

C. Berge, Graphs and Hypergraphs, North-Holland Mathematical Library 6, 2nd edition, North-Holland (1976). 26

work page 1976

[6] [5]

S. Cho, S. van Willigenburg, Chromatic bases for symmetric functions, Elec- tron. J. Combin. 23, 6pp. (2016)

work page 2016

[7] [6]

Chow, Symmetric function generalizations of graph polynomials, Ph

T. Chow, Symmetric function generalizations of graph polynomials, Ph. D. Thesis, MIT, 1995

work page 1995

[8] [7]

F. R. K. Chung and R. L. Graham, On the cover polynomial of a digraph, J. Combin. Theory Ser. B, 65(2):273–29, 1995

work page 1995