Skip to content

Möbius algebras and flag vectors

4 fully proved

The Möbius algebra

DefinitionMöbius algebra product#✓fully proved

Let \(L\) be a lattice with meet \(\wedge\) and let \(R\) be a commutative semiring. The Möbius algebra \(A(L, R)\) is the set of functions \(f \colon L \to R\) with \(f(s) \neq 0\) for only finitely many \(s \in L\). The product of \(f, g \in A(L, R)\) is the function \(f \cdot g \in A(L, R)\) given by

\[(f \cdot g)(u) = \sum_{s \wedge t = u} f(s)\, g(t) \qquad (u \in L),\]

the sum taken over all pairs \((s, t) \in L \times L\) with \(f(s) \neq 0\), \(g(t) \neq 0\) and \(s \wedge t = u\). Equivalently, identifying each \(s \in L\) with the function that is \(1\) at \(s\) and \(0\) elsewhere, it is the bilinear extension of \(s \cdot t = s \wedge t\).

noncomputable def moebiusAlgebraMul {L R : Type*} [Lattice L]
    [CommSemiring R] (f g : L →₀ R) : L →₀ R :=
  f.sum fun s a => g.sum fun t b =>
    Finsupp.single (s ⊓ t) (a * b)

Flag vectors

DefinitionFlag \(f\)-vector#✓fully proved

Let \(P\) be a finite partially ordered set with a grade function \(\rho \colon P \to \mathbb{Z}_{\ge 0}\), that is, \(\rho(s) < \rho(t)\) whenever \(s < t\), \(\rho(t) = \rho(s) + 1\) whenever \(t\) covers \(s\) (that is, \(s < t\) and no \(u \in P\) satisfies \(s < u < t\)), and \(\rho(t) = 0\) whenever \(t\) is minimal. For a finite set \(S \subseteq \mathbb{Z}_{\ge 0}\), let \(P_S = \{t \in P : \rho(t) \in S\}\). The flag \(f\)-vector of \(P\) is the function \(\alpha_P\) on finite sets \(S \subseteq \mathbb{Z}_{\ge 0}\) such that \(\alpha_P(S)\) is the number of maximal chains in \(P_S\), that is, of subsets \(C \subseteq P_S\) any two elements of which are comparable and such that every element of \(P_S \setminus C\) is incomparable with some element of \(C\). In particular \(\alpha_P(\emptyset) = 1\), the empty chain being the only maximal chain in the empty poset.

def flagFVector (P : Type*) [PartialOrder P] [Fintype P]
    [DecidableEq P] [DecidableLE P] [GradeMinOrder ℕ P]
    (S : Finset ℕ) : ℕ :=
  (Finset.univ.filter fun c : Finset P =>
    (∀ t ∈ c, grade ℕ t ∈ S) ∧
      (∀ x ∈ c, ∀ y ∈ c, x ≤ y ∨ y ≤ x) ∧
      ∀ t, grade ℕ t ∈ S → t ∉ c →
        ∃ x ∈ c, ¬(x ≤ t ∨ t ≤ x)).card
Used by 1
Used byFlag \(h\)-vector

DefinitionFlag \(h\)-vector#✓fully proved

Let \(P\) be a finite partially ordered set with a grade function \(\rho \colon P \to \mathbb{Z}_{\ge 0}\), that is, \(\rho(s) < \rho(t)\) whenever \(s < t\), \(\rho(t) = \rho(s) + 1\) whenever \(t\) covers \(s\), and \(\rho(t) = 0\) whenever \(t\) is minimal. Let \(\alpha_P\) be the flag \(f\)-vector of \(P\) with respect to \(\rho\): for a finite set \(T \subseteq \mathbb{Z}_{\ge 0}\), \(\alpha_P(T)\) is the number of maximal chains in the subposet \(\{t \in P : \rho(t) \in T\}\). The flag \(h\)-vector of \(P\) is the integer-valued function \(\beta_P\) on finite sets \(S \subseteq \mathbb{Z}_{\ge 0}\) given by

\[\beta_P(S) = \sum_{T \subseteq S} (-1)^{|S \setminus T|} \alpha_P(T),\]

where the sum runs over all subsets \(T\) of \(S\) and \(|S \setminus T|\) is the number of elements of \(S \setminus T\). In particular, \(\beta_P(\emptyset) = \alpha_P(\emptyset) = 1\).

def flagHVector (P : Type*) [PartialOrder P] [Fintype P]
    [DecidableEq P] [DecidableLE P] [GradeMinOrder ℕ P]
    (S : Finset ℕ) : ℤ :=
  ∑ T ∈ S.powerset, (-1) ^ (S \ T).card * (flagFVector P T : ℤ)
Uses 1
Statement usesFlag \(f\)-vector

DefinitionHyperplane arrangement#✓fully proved

Let \(K\) be a field, let \(V\) be a finite-dimensional vector space over \(K\), and let \(E\) be an affine subspace of \(V\), possibly empty. The dimension of a nonempty affine subspace \(v + W\), with \(v \in V\) and \(W\) a linear subspace of \(V\), is \(\dim W\). An affine hyperplane of \(E\) is a nonempty affine subspace \(H\) of \(V\) with \(H \subseteq E\) and \(\dim H + 1 = \dim E\). A set \(\mathcal{A}\) of affine subspaces of \(V\) is a hyperplane arrangement in \(E\) if \(\mathcal{A}\) is finite and every element of \(\mathcal{A}\) is an affine hyperplane of \(E\).

For \(n \in \mathbb{Z}_{\ge 0}\), \(V = K^n\) and \(E = V\), the affine hyperplanes of \(E\) are the sets \(\{v \in K^n : \alpha_1 v_1 + \cdots + \alpha_n v_n = a\}\) with \((\alpha_1, \ldots, \alpha_n) \in K^n\) nonzero and \(a \in K\). The empty set is a hyperplane arrangement in every \(E\), and it is the only one when \(E\) is empty or \(\dim E = 0\).

def IsHyperplaneArrangement {K V : Type*} [Field K]
    [AddCommGroup V] [Module K V] [FiniteDimensional K V]
    (E : AffineSubspace K V) (A : Set (AffineSubspace K V)) :
    Prop :=
  A.Finite ∧ ∀ H ∈ A, H ≤ E ∧ (H : Set V).Nonempty ∧
    Module.finrank K H.direction + 1 =
      Module.finrank K E.direction

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.