Intersecting families, Sperner theory and sunflowers

Erdős–Ko–Rado and its variants, Chvátal's conjecture, forbidden and singleton intersections, comparable pairs, union-free and union-closed families, shadows (Kruskal–Katona, Macaulay), Harper's isoperimetric inequality, and sunflower bounds.

TheoremMacaulay's theorem for monomials#✓fully proved

Let \(k \ge 0\) and let \(A\) be a finite set of monomials of degree \(k + 1\) in the variables \(x_0, x_1, x_2, \dots\), given by their exponent vectors: finitely supported \(a \colon \mathbb{N} \to \mathbb{N}\) with \(\sum_j a_j = k + 1\). Suppose that \(|A| = \sum_{i=0}^{k} \binom{d_i}{i + 1}\) for natural numbers \(d_0 < d_1 < \dots < d_k\). Let the shadow \(\partial A\) be the set of exponent vectors obtained from some \(a \in A\) by lowering one positive coordinate \(a_j\) by \(1\). Then \(\partial A\) has at least \(\sum_{0 \le i \le k,\ d_i \ge 1} \binom{d_i - 1}{i}\) elements.

Terms with \(d_i = 0\), which can occur only for \(i = 0\), contribute nothing to the bound.

Proof: following Ábrego, Fernández-Merchant, and Llano, from a binomial-cascade split inequality and induction on coordinate slices (their route from Theorem 1 to Theorem M).

public theorem macaulay_multiset_shadow_minimal
    (k : ℕ) (A : Finset (ℕ →₀ ℕ)) (digits : Fin (k + 1) → ℕ)
    (hdegree : ∀ a ∈ A, a.sum (fun _ e => e) = k + 1)
    (hstrict : StrictMono digits)
    (hcard : A.card = ∑ i, Nat.choose (digits i) (i.1 + 1)) :
    (∑ i, if digits i = 0 then 0 else Nat.choose (digits i - 1) i.1) ≤
      (A.biUnion fun a => a.support.image fun i => a.update i (a i - 1)).card
Sources

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.