Partitionable and interval-decomposable complexes

DefinitionRank-\(k\) interval decomposition with a subcomplex of bottoms#✓fully proved

For a natural number \(k\), a finite family \(K\) of finite subsets of \(\mathbb{N}\) has a rank-\(k\) interval decomposition with a subcomplex of bottoms if there are a finite family \(B\) of finite subsets of \(\mathbb{N}\), closed under taking subsets, and an assignment of a finite set \(\mathrm{top}(F) \subseteq \mathbb{N}\) to each finite set \(F \subseteq \mathbb{N}\), such that every \(F \in B\) satisfies \(F \subseteq \mathrm{top}(F)\), \(|\mathrm{top}(F)| = |F| + k\) and \(\mathrm{top}(F) \in K\), and every \(\sigma \in K\) lies in the interval \([F, \mathrm{top}(F)] = \{G : F \subseteq G \subseteq \mathrm{top}(F)\}\) for exactly one \(F \in B\).

def HasRankIntervalDecomposition (K : Finset (Finset ℕ)) (k : ℕ) : Prop :=
  ∃ (B : Finset (Finset ℕ)) (top : Finset ℕ → Finset ℕ), (∀ F ∈ B, ∀ G ⊆ F, G ∈ B) ∧
    (∀ F ∈ B, F ⊆ top F ∧ (top F).card = F.card + k ∧ top F ∈ K) ∧
    ∀ σ ∈ K, ∃! F, F ∈ B ∧ F ⊆ σ ∧ σ ⊆ top F
Used by 1
Used byStanley's interval-decomposition conjecture for complexes with acyclic links

The statement that for every integer \(k \ge 1\) and every finite simplicial complex \(K\) on the vertex set \(\mathbb{N}\) (a finite family of finite subsets of \(\mathbb{N}\) closed under taking subsets): if the link \(\mathrm{lk}_K(F) = \{G \in K : G \cap F = \emptyset,\ G \cup F \in K\}\) of every face \(F \in K\) with fewer than \(k\) vertices (including \(\mathrm{lk}_K(\emptyset) = K\)) is acyclic over \(\mathbb{Q}\) (all of its reduced rational homology vanishes), then \(K\) has a rank-\(k\) interval decomposition with a subcomplex of bottoms: there are a family \(B\) of finite subsets of \(\mathbb{N}\), closed under taking subsets, and faces \(\mathrm{top}(F) \in K\) for \(F \in B\) with \(F \subseteq \mathrm{top}(F)\) and \(|\mathrm{top}(F)| = |F| + k\), such that every face of \(K\) lies in the interval \([F, \mathrm{top}(F)]\) for exactly one \(F \in B\).

This is Stanley's Problem 5 (Positivity Problems; Conjecture 2.4 of Stanley, Discrete Math. 120 (1993)) with \(k = j + 2\): the faces with fewer than \(k\) vertices are the faces of dimension at most \(j\), and for an interval \([F, F']\) with \(F' = \mathrm{top}(F)\), the condition \(|F'| = |F| + k\) means \(\dim F' - \dim F = k\).

def acyclicLinksIntervalDecomposition : Prop :=
  ∀ k : ℕ, 1 ≤ k → ∀ K : Finset (Finset ℕ), IsSimplicialComplex K →
    (∀ F ∈ K, F.card < k → IsRationallyAcyclic (link K F)) → HasRankIntervalDecomposition K k
Uses 4 · Used by 1
Statement usesRank-\(k\) interval decomposition with a subcomplex of bottoms · Rationally acyclic complexes · Finite abstract simplicial complex · Link
Used byStanley's interval-decomposition conjecture for complexes with acyclic links is false

It is not true that for every integer \(k \ge 1\) and every finite simplicial complex \(K\) on the vertex set \(\mathbb{N}\) (a finite family of finite subsets of \(\mathbb{N}\) closed under taking subsets) such that the link \(\mathrm{lk}_K(F) = \{G \in K : G \cap F = \emptyset,\ G \cup F \in K\}\) of every face \(F \in K\) with fewer than \(k\) vertices is acyclic over \(\mathbb{Q}\) (all of its reduced rational homology vanishes), there are a family \(B\) of finite subsets of \(\mathbb{N}\), closed under taking subsets, and faces \(\mathrm{top}(F) \in K\) for \(F \in B\) with \(F \subseteq \mathrm{top}(F)\) and \(|\mathrm{top}(F)| = |F| + k\), such that every face of \(K\) lies in the interval \([F, \mathrm{top}(F)]\) for exactly one \(F \in B\).

Doolittle and Goeckner constructed a complex with \(k = 2\) (a \(2\)-fold acyclic complex) that cannot be partitioned into intervals \([F, F']\) with \(|F'| = |F| + 2\) at all; the case \(k = 1\) is Stanley's theorem.

public theorem_wanted acyclicLinksIntervalDecomposition_refuted :
    ¬ acyclicLinksIntervalDecomposition
Sources
  • R. P. Stanley, Positivity Problems and Conjectures in Algebraic Combinatorics (1999), Problem 5 (interval decompositions of complexes with acyclic links); resolution: J. Doolittle and B. Goeckner, Resolving Stanley's conjecture on k-fold acyclic complexes, FPSAC 2019 (Sém. Lothar. Combin. 82B, Article 46), arXiv:1811.08518, §3: Theorem 3.2 (gluing N copies of Δ along Γ preserves k-fold acyclicity and non-decomposability for N > ℓ/2^k) with Theorem 3.4 (Φ = (Δ, Γ) is not rank 2 boolean decomposable); "Ω₁₇ is a counterexample to Conjecture 1.3" (Stanley's Conjecture 2.4 = Problem 5 of the 1999 list, k = 2), https://arxiv.org/abs/1811.08518.
Uses 1
Statement usesStanley's interval-decomposition conjecture for complexes with acyclic links

DefinitionCohen–Macaulay complexes over \(\mathbb{Q}\)#✓fully proved

A finite family \(K\) of finite subsets of \(\mathbb{N}\) is Cohen–Macaulay over \(\mathbb{Q}\) when for every member \(F\) of \(K\) (the empty face included, if it belongs to \(K\)) the link \(L = \operatorname{lk}_K F = \{G \in K : G \cap F = \emptyset,\ G \cup F \in K\}\) satisfies \(\tilde\beta_i(L) = 0\) for every integer \(i\) with \(-1 \le i < \dim L\). Here \(\dim L\) is one less than the largest number of elements of a member of \(L\), taken to be \(-1\) when \(L\) has no nonempty member, and \(\tilde\beta_i(L)\) is the number of members of \(L\) with \(i + 1\) elements minus the ranks of the augmented rational simplicial boundary maps (vertices ordered as in \(\mathbb{N}\)) out of and into the span of these members; when \(L\) is a simplicial complex, \(\tilde\beta_i(L) = \dim \tilde H_i(L; \mathbb{Q})\).

For a simplicial complex this is Reisner's criterion.

def IsCohenMacaulayOverRat (K : Finset (Finset ℕ)) : Prop :=
  ∀ F ∈ K, ∀ k, k < topCard (link K F) → reducedBetti (link K F) k = 0
Uses 3 · Used by 1
Statement usesLink · Reduced rational Betti numbers · Largest face size
Used byStanley–Garsia partitionability conjecture

DefinitionPure complexes#✓fully proved

A finite family \(K\) of finite subsets of \(\mathbb{N}\) is pure when all its facets (maximal members) have the same number of elements.

def IsPure (K : Finset (Finset ℕ)) : Prop :=
  ∃ d : ℕ, ∀ F, IsFacet K F → F.card = d
Uses 1 · Used by 1
Statement usesFacet
Used byStanley–Garsia partitionability conjecture

DefinitionPartitionable complexes#✓fully proved

A finite family \(K\) of finite subsets of \(\mathbb{N}\) is partitionable when there is a map \(r\) assigning to each facet \(F\) of \(K\) a set \(r(F) \subseteq F\) such that for every member \(\sigma\) of \(K\) there is exactly one facet \(F\) of \(K\) with \(r(F) \subseteq \sigma \subseteq F\).

For a simplicial complex this says that its faces are partitioned into the intervals \([r(F), F] = \{\sigma : r(F) \subseteq \sigma \subseteq F\}\), one for each facet \(F\).

def IsPartitionable (K : Finset (Finset ℕ)) : Prop :=
  ∃ r : Finset ℕ → Finset ℕ, (∀ F, IsFacet K F → r F ⊆ F) ∧
    ∀ σ ∈ K, ∃! F, IsFacet K F ∧ r F ⊆ σ ∧ σ ⊆ F
Uses 1 · Used by 1
Statement usesFacet
Used byStanley–Garsia partitionability conjecture

DefinitionStanley–Garsia partitionability conjecture#✓fully proved

Every finite simplicial complex on the vertex set \(\mathbb{N}\) that is pure and Cohen–Macaulay over \(\mathbb{Q}\) is partitionable.

def cohenMacaulayPartitionable : Prop :=
  ∀ K : Finset (Finset ℕ), IsSimplicialComplex K → IsPure K → IsCohenMacaulayOverRat K →
    IsPartitionable K
Sources
  • R. P. Stanley, Positivity Problems and Conjectures in Algebraic Combinatorics, Problem 6 (partitionability conjecture of Stanley and Garsia).
Uses 4 · Used by 1
Statement usesCohen–Macaulay complexes over \(\mathbb{Q}\) · Partitionable complexes · Pure complexes · Finite abstract simplicial complex
Used byThe Stanley–Garsia partitionability conjecture is false

TheoremThe Stanley–Garsia partitionability conjecture is false#●ready to prove

There is a finite simplicial complex on the vertex set \(\mathbb{N}\) that is pure and Cohen–Macaulay over \(\mathbb{Q}\) but not partitionable.

Duval, Goeckner, Klivans and Martin constructed explicit pure \(3\)-dimensional Cohen–Macaulay simplicial complexes that are not partitionable.

public theorem_wanted cohenMacaulayPartitionable_refuted : ¬ cohenMacaulayPartitionable
Sources
  • R. P. Stanley, Positivity Problems and Conjectures in Algebraic Combinatorics (1999), Problem 6 (Stanley–Garsia partitionability conjecture); resolution: A. M. Duval, B. Goeckner, C. J. Klivans and J. L. Martin, A non-partitionable Cohen-Macaulay simplicial complex, Adv. Math. 299 (2016), 381-395, arXiv:1504.04279, Theorem 3.5 (arXiv numbering): the complex C₃ obtained by gluing three copies of X along A is Cohen-Macaulay and non-partitionable (Theorem 3.4: likewise C₂₅, by the gluing Theorem 3.1); abstract: "We disprove the conjecture by constructing an explicit counterexample", https://arxiv.org/abs/1504.04279.
Uses 1
Statement usesStanley–Garsia partitionability conjecture
6 fully proved2 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.