Documentation

Complexitylib.Algebraic.LowerBound.Cutwidth.Aggregate.Geometry.Fiber.Internal

Exact counting for disjoint conjunction majority inputs #

Split the original cube into all selected endpoints and the unused coordinates. Each selected pair independently allows exactly three of its four assignments.

theorem Algebraic.Cutwidth.Aggregate.Geometry.Fiber.Internal.local_card {E : Type u_1} [Fintype E] (left right : E → Bool) :
Fintype.card { x : E × Bool → Bool // ∀ (e : E), (x (e, false) == left e && x (e, true) == right e) = false } = 3 ^ Fintype.card E

Independent signed pairs have exactly three majority assignments each.

The majority set of disjoint signed conjunctions has its exact product cardinality.