Neggers–Stanley conjecture

DefinitionNumber of descents of a permutation of \(\{0, \dots, n-1\}\)#✓fully proved

For a permutation \(w\) of \(\{0, 1, \dots, n-1\}\), read as the word \(w(0)\,w(1) \cdots w(n-1)\), the number of descents \(d(w)\) is the number of indices \(i\) with \(i + 1 < n\) and \(w(i) > w(i+1)\).

def descentCount {n : ℕ} (w : Equiv.Perm (Fin n)) : ℕ :=
  (Finset.univ.filter fun i : Fin n => ∃ h : i.val + 1 < n, w ⟨i.val + 1, h⟩ < w i).card

Used by 1

Used byThe \(W\)-polynomial of a labeled poset

DefinitionThe \(W\)-polynomial of a labeled poset#✓fully proved

Let \(R\) be a relation on the labels \(\{0, 1, \dots, n-1\}\), with \(R(i, j)\) read as \(i \lt _P j\) in the poset \(P\) it generates. A linear extension of \(P\) is a permutation \(w\) of the labels such that \(a < b\) whenever \(R(w(a), w(b))\), that is, a word \(w(0)\,w(1) \cdots w(n-1)\) listing every label once with \(w(a)\) before \(w(b)\) whenever \(R(w(a), w(b))\). The \(W\)-polynomial is the integer polynomial \(W(P, x) = \sum_w x^{d(w)}\), summed over the linear extensions \(w\) of \(P\), where \(d(w)\) is the number of descents of \(w\).

Linear extensions of \(R\) and of its transitive closure coincide, so \(R\) need not be transitive.

noncomputable def wPolynomial {n : ℕ} (R : Fin n → Fin n → Prop) : Polynomial ℤ :=
  ∑ w : Equiv.Perm (Fin n) with ∀ a b, R (w a) (w b) → a < b, Polynomial.X ^ descentCount w

Uses 1 · Used by 1

Statement usesNumber of descents of a permutation of \(\{0, \dots, n-1\}\)

Used byNeggers' conjecture

DefinitionNeggers' conjecture#✓fully proved

For every \(n\) and every relation \(R\) on the labels \(\{0, 1, \dots, n-1\}\) that is naturally labeled, meaning that \(R(i, j)\) implies \(i < j\), every complex zero of the \(W\)-polynomial \(W(P, x)\) of the poset \(P\) generated by \(R\) is real.

This is Stanley, Positivity Problems, Problem 20, for naturally labeled posets.

def neggersConjecture : Prop :=
  ∀ (n : ℕ) (R : Fin n → Fin n → Prop), (∀ i j, R i j → i < j) →
    ((wPolynomial R).map (Int.castRingHom ℂ)).IsRealRooted

Uses 2 · Used by 1

Statement usesThe \(W\)-polynomial of a labeled poset · Real-rooted polynomials

Used byNeggers' conjecture is false

TheoremNeggers' conjecture is false#●ready to prove

There exist \(n\) and a naturally labeled relation \(R\) on the labels \(\{0, 1, \dots, n-1\}\), one in which \(R(i, j)\) implies \(i < j\), such that the \(W\)-polynomial \(W(P, x)\) of the poset \(P\) generated by \(R\) has a complex zero that is not real.

Stembridge found naturally labeled posets on \(17\) elements whose \(W\)-polynomials have non-real zeros, disproving Neggers' conjecture and hence the Neggers–Stanley conjecture (Brändén had earlier given counterexamples with non-natural labelings).

public theorem_wanted neggersConjecture_refuted : ¬ neggersConjecture

Sources

• R. P. Stanley, Positivity Problems and Conjectures in Algebraic Combinatorics (1999), Problem 20 (Neggers–Stanley conjecture); resolution: J. R. Stembridge, Counterexamples to the poset conjectures of Neggers, Stanley, and Stembridge, Trans. Amer. Math. Soc. 359 (2007), 1115-1128; P. Brändén, Counterexamples to the Neggers-Stanley conjecture, Electron. Res. Announc. Amer. Math. Soc. 10 (2004), 155-158 (non-natural labelings), Stembridge, Introduction: there exist naturally labeled narrow posets on 17 vertices whose W-polynomials have non-real zeros (and none smaller), disproving Neggers' original conjecture; Figure 1 gives one, with W-polynomial t + 32t² + 336t³ + 1420t⁴ + 2534t⁵ + 1946t⁶ + 658t⁷ + 86t⁸ + 3t⁹, https://websites.umich.edu/~jrs/papers/pocon.pdf.

Uses 1

Statement usesNeggers' conjecture

3 fully proved1 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.