/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesForMathlib.Combinatorics.Hypergraph.Basic
public import Mathlib.Combinatorics.SetFamily.Intersecting
public import Mathlib.Data.Finset.Powerset
public import Mathlib.Data.Finset.Sort
public import Mathlib.Data.ENat.Lattice
public import FormalConjecturesForMathlib.Combinatorics.SetFamily.PropertyB@[expose] public sectionFinite hypergraphs and block designs
Finite hypergraphs are finite families of finite vertex sets. This file supplies uniformity,
weak vertex coloring, independent sets, transversals, designs, and finite extremal counts.
Finset.toHypergraph connects this presentation to Mathlib's Hypergraph.
The ground type includes isolated vertices. The support is H.biUnion id when only incident
vertices should be counted. Colorings require two differently colored vertices in every edge;
empty and singleton edges therefore admit no proper coloring.
namespace Set
A family of finite sets has a transversal with at most k vertices.
def HasFiniteTransversal {V : Type*} (F : Set (Finset V)) (k : ℕ) : Prop :=
∃ S : Finset V, S.card ≤ k ∧ ∀ e ∈ F, ∃ v ∈ S, v ∈ eend Setnamespace Finsetvariable {V : Type*} [DecidableEq V]
Every edge has exactly r vertices.
def IsUniform (H : Finset (Finset V)) (r : ℕ) : Prop := ∀ e ∈ H, e.card = r
The hypergraph with edge family H and ground vertex set S.
def toHypergraph (H : Finset (Finset V)) (S : Finset V) (h : ∀ e ∈ H, e ⊆ S) :
Hypergraph V :=
Hypergraph.ofEdgeFamily (H : Set (Finset V)) S homit [DecidableEq V] inConversion preserves uniformity.
@[simp]
theorem isUniform_toHypergraph_iff (H : Finset (Finset V)) (S : Finset V)
(h : ∀ e ∈ H, e ⊆ S) (r : ℕ) :
(H.toHypergraph S h).IsUniform r ↔ H.IsUniform r := V:Type u_1H:Finset (Finset V)S:Finset Vh:∀ e ∈ H, e ⊆ Sr:ℕ⊢ (H.toHypergraph S h).IsUniform r ↔ H.IsUniform r
All goals completed! 🐙A weak proper coloring has no monochromatic edge.
def IsProperHypergraphColoring (H : Finset (Finset V)) {C : Type*} (c : V → C) : Prop :=
∀ e ∈ H, ∃ x ∈ e, ∃ y ∈ e, c x ≠ c yomit [DecidableEq V] inConversion preserves weak proper colorings.
@[simp]
theorem isProperColoring_toHypergraph_iff {C : Type*} (H : Finset (Finset V))
(S : Finset V) (h : ∀ e ∈ H, e ⊆ S) (f : V → C) :
(H.toHypergraph S h).IsProperColoring f ↔ H.IsProperHypergraphColoring f := V:Type u_1C:Type u_2H:Finset (Finset V)S:Finset Vh:∀ e ∈ H, e ⊆ Sf:V → C⊢ (H.toHypergraph S h).IsProperColoring f ↔ H.IsProperHypergraphColoring f
All goals completed! 🐙
The edge family admits a weak proper coloring with k colors.
def HypergraphColorable (H : Finset (Finset V)) (k : ℕ) : Prop :=
∃ c : V → Fin k, H.IsProperHypergraphColoring comit [DecidableEq V] inTwo-colorability agrees with the existing Property B predicate.
theorem hypergraphColorable_two_iff (H : Finset (Finset V)) :
H.HypergraphColorable 2 ↔ H.HasPropertyB := Iff.rfl
The weak chromatic number is exactly k.
def HasHypergraphChromaticNumber (H : Finset (Finset V)) (k : ℕ) : Prop :=
H.HypergraphColorable k ∧ ∀ j < k, ¬ H.HypergraphColorable jNo edge is contained in this set of vertices.
def IsHypergraphIndependent (H : Finset (Finset V)) (S : Finset V) : Prop :=
∀ e ∈ H, ¬ e ⊆ SThe number of hyperedges containing a vertex.
def hypergraphDegree (H : Finset (Finset V)) (v : V) : ℕ := #{e ∈ H | v ∈ e}Distinct edges intersect in at most one vertex.
def IsLinearHypergraph (H : Finset (Finset V)) : Prop :=
(H : Set (Finset V)).Pairwise fun e f ↦ (e ∩ f).card ≤ 1
Some m vertices span at least k edges.
def ContainsSubgraph (H : Finset (Finset V)) (m k : ℕ) : Prop :=
∃ S : Finset V, S.card = m ∧ k ≤ #{e ∈ H | e ⊆ S}The edges induced on a vertex set.
def hypergraphInduce (H : Finset (Finset V)) (S : Finset V) : Finset (Finset V) :=
H.filter (· ⊆ S)
A copy of the complete r-uniform hypergraph on k vertices.
def ContainsCompleteHypergraph (H : Finset (Finset V)) (r k : ℕ) : Prop :=
∃ S : Finset V, S.card = k ∧ S.powersetCard r ⊆ H
A collection of k pairwise vertex-disjoint edges.
def HasHypergraphMatching (H : Finset (Finset V)) (k : ℕ) : Prop :=
∃ M ⊆ H, M.card = k ∧ (M : Set (Finset V)).Pairwise Disjoint
Every t-set of ground vertices lies in exactly one block.
def IsBlockDesign (H : Finset (Finset V)) (t k : ℕ) : Prop :=
H.IsUniform k ∧ ∀ S : Finset V, S.card = t → ∃! e, e ∈ H ∧ S ⊆ eA pairwise balanced design, permitting a block equal to the ground set.
def IsPairwiseBalancedDesign (H : Finset (Finset V)) : Prop :=
(∀ e ∈ H, 2 ≤ e.card) ∧
∀ S : Finset V, S.card = 2 → ∃! e, e ∈ H ∧ S ⊆ eThe nondecreasing block-size sequence, retaining repeated sizes.
def blockSizeProfile (H : Finset (Finset V)) : List ℕ :=
(H.val.map Finset.card).sort (· ≤ ·)
Partition into complete r-graphs with either r or r+1 vertices.
def IsCompleteHypergraphDecomposition (H : Finset (Finset V)) (r : ℕ)
(D : Finset (Finset V)) : Prop :=
(∀ S ∈ D, S.card = r ∨ S.card = r + 1) ∧
H = D.biUnion (fun S ↦ S.powersetCard r) ∧
(D : Set (Finset V)).Pairwise fun S T ↦ Disjoint (S.powersetCard r) (T.powersetCard r)
A complete t-partite t-uniform hypergraph with r vertices in each part.
def ContainsCompletePartiteHypergraph (H : Finset (Finset V)) (t r : ℕ) : Prop :=
∃ f : Fin t × Fin r ↪ V, ∀ a : Fin t → Fin r,
(Finset.univ.image fun i ↦ f (i, a i)) ∈ HTwo distinct disjoint pairs of edges with the same union.
def HasRepeatedDisjointUnion (H : Finset (Finset V)) : Prop :=
∃ A ∈ H, ∃ B ∈ H, ∃ C ∈ H, ∃ D ∈ H,
Disjoint A B ∧ Disjoint C D ∧ A ∪ B = C ∪ D ∧
A ≠ B ∧ C ≠ D ∧ A ≠ C ∧ A ≠ D ∧ B ≠ C ∧ B ≠ Domit [DecidableEq V] in
@[simp] theorem isUniform_empty (r : ℕ) : (∅ : Finset (Finset V)).IsUniform r := V:Type u_1r:ℕ⊢ ∅.IsUniform r
All goals completed! 🐙
The cardinal bound in ContainsSubgraph counts edges, not copies with labels.
theorem containsSubgraph_iff (H : Finset (Finset V)) (m k : ℕ) :
H.ContainsSubgraph m k ↔ ∃ S : Finset V,
S.card = m ∧ k ≤ (H.hypergraphInduce S).card := Iff.rflomit [DecidableEq V] inA singleton edge prevents any weak proper coloring.
theorem not_colorable_singleton (v : V) (k : ℕ) :
¬ ({ {v} } : Finset (Finset V)).HypergraphColorable k := V:Type u_1v:Vk:ℕ⊢ ¬{{v}}.HypergraphColorable k
V:Type u_1v:Vk:ℕc:V → Fin khc:{{v}}.IsProperHypergraphColoring c⊢ False
All goals completed! 🐙open scoped Classical inThe largest cardinality of an independent vertex set in a finite ground type.
noncomputable def hypergraphIndependenceNumber [Fintype V] (H : Finset (Finset V)) : ℕ :=
((Finset.univ : Finset V).powerset.filter H.IsHypergraphIndependent).sup Finset.cardopen scoped Classical inSubsets of the incident vertices witnessing Property B.
noncomputable def propertyBWitnesses (H : Finset (Finset V)) : Finset (Finset V) :=
(H.biUnion id).powerset.filter fun B ↦
(∀ e ∈ H, (e ∩ B).Nonempty) ∧ H.IsHypergraphIndependent Bend Finsetnamespace Hypergraphopen scoped Classical in
Maximum number of edges among r-uniform families satisfying P on n labeled vertices.
The value is zero if no family is admissible.
noncomputable def extremalNumber (n r : ℕ) (P : Finset (Finset (Fin n)) → Prop) : ℕ :=
(((Finset.univ : Finset (Fin n)).powersetCard r).powerset.filter P).sup Finset.cardThe extremal number forbidding a complete uniform hypergraph.
noncomputable def cliqueExtremalNumber (n r k : ℕ) : ℕ :=
extremalNumber n r fun H ↦ ¬ H.ContainsCompleteHypergraph r k
The extremal number forbidding e edges on v vertices (not necessarily induced).
noncomputable def configurationExtremalNumber (n r v e : ℕ) : ℕ :=
extremalNumber n r fun H ↦ ¬ H.ContainsSubgraph v eThe extremal number forbidding a complete balanced multipartite uniform hypergraph.
noncomputable def partiteExtremalNumber (n t r : ℕ) : ℕ :=
extremalNumber n t fun H ↦ ¬ H.ContainsCompletePartiteHypergraph t r
Minimum edge count for chromatic number k, with infinity when no such graph exists.
noncomputable def minChromaticEdges (r k : ℕ) : ℕ∞ :=
⨅ (n : ℕ) (H : Finset (Finset (Fin n))) (_ : H.IsUniform r)
(_ : H.HasHypergraphChromaticNumber k), (H.card : ℕ∞)open scoped Classical in
All block-size sequences of pairwise balanced designs on n labeled vertices.
noncomputable def blockSizeProfiles (n : ℕ) : Finset (List ℕ) :=
(((Finset.univ : Finset (Fin n)).powerset.powerset).filter
Finset.IsPairwiseBalancedDesign).image Finset.blockSizeProfileend Hypergraph