/-
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.Finite
public import Mathlib.SetTheory.Cardinal.Basic
public import Mathlib.SetTheory.Cardinal.Ordinal@[expose] public sectionUniform hypergraphs
A UniformHypergraph V k extends Mathlib's Hypergraph V with uniformity k
and vertex set Set.univ. The vertex type includes isolated vertices.
Finite edge families use Finset.IsUniform;
UniformHypergraph.ofFinset converts them to this presentation.
The API includes complete subgraphs, maximal clique sizes, weak colorings, embeddings, and chromatic cardinals. The chromatic cardinal is zero when no proper coloring exists. Empty and singleton edges admit no weak proper coloring.
open Cardinal Setuniverse uA uniform Mathlib hypergraph whose vertex set is the entire ambient type.
structure UniformHypergraph (V : Type*) (k : ℕ) extends Hypergraph V whereAll elements of the vertex type are vertices, including isolated ones.
vertexSet_eq_univ : vertexSet = Set.univ
Every hyperedge has exactly k vertices.
uniform : toHypergraph.IsUniform knamespace UniformHypergraphvariable {k : ℕ}A finite uniform edge family viewed as a uniform hypergraph.
def ofFinset {V : Type*} (H : Finset (Finset V)) (hH : H.IsUniform k) :
UniformHypergraph V k where
toHypergraph := Hypergraph.ofEdgeFamily (H : Set (Finset V)) Set.univ
(fun _ _ ↦ Set.subset_univ _)
vertexSet_eq_univ := rfl
uniform := Hypergraph.isUniform_ofEdgeFamily_iff.mpr hH@[simp]
theorem mem_edgeSet_ofFinset {V : Type*} {H : Finset (Finset V)} {hH : H.IsUniform k}
{e : Finset V} : (e : Set V) ∈ (ofFinset H hH).edgeSet ↔ e ∈ H :=
Hypergraph.mem_edgeSet_ofEdgeFamily (h := fun _ _ ↦ Set.subset_univ _)
Every k-element subset of S is an edge.
def IsCompleteOn {V : Type*} (H : UniformHypergraph V k) (S : Finset V) : Prop :=
∀ e : Finset V, e ⊆ S → e.card = k → (e : Set V) ∈ H.edgeSetThe sizes of the finite maximal complete subgraphs.
def cliqueSizes {V : Type*} (H : UniformHypergraph V k) : Set ℕ :=
{ n | ∃ S : Finset V, Maximal (IsCompleteOn H) S ∧ S.card = n }Weak proper coloring of the underlying Mathlib hypergraph.
abbrev IsProperColoring {V : Type*} (H : UniformHypergraph V k) {C : Type*}
(f : V → C) : Prop :=
H.toHypergraph.IsProperColoring fAn injective coloring is proper when every edge has at least two vertices.
theorem isProperColoring_of_injective {V C : Type*} (H : UniformHypergraph V k)
(hk : 2 ≤ k) {f : V → C} (hf : Function.Injective f) : H.IsProperColoring f :=
H.uniform.isProperColoring_of_injective hk hfThe finite and possibly infinite presentations have the same proper colorings.
theorem isProperColoring_ofFinset_iff {V C : Type*} (H : Finset (Finset V))
(hH : H.IsUniform k) (f : V → C) :
(ofFinset H hH).IsProperColoring f ↔ H.IsProperHypergraphColoring f := k:ℕV:Type u_1C:Type u_2H:Finset (Finset V)hH:H.IsUniform kf:V → C⊢ (ofFinset H hH).IsProperColoring f ↔ H.IsProperHypergraphColoring f
All goals completed! 🐙The infimum of cardinalities of color types admitting a proper coloring. The value is zero when no proper coloring exists.
noncomputable def chromaticCardinal {V : Type u} (H : UniformHypergraph V k) : Cardinal.{u} :=
sInf {κ : Cardinal.{u} | ∃ (C : Type u), #C = κ ∧ ∃ f : V → C, H.IsProperColoring f}A proper coloring bounds the chromatic cardinal by the number of colors.
theorem chromaticCardinal_le {V C : Type u} (H : UniformHypergraph V k)
{f : V → C} (hf : H.IsProperColoring f) : H.chromaticCardinal ≤ #C :=
csInf_le' ⟨C, rfl, f, hf⟩
The vertex type itself always supplies enough colors when 2 ≤ k.
theorem chromaticCardinal_le_mk {V : Type u} (H : UniformHypergraph V k) (hk : 2 ≤ k) :
H.chromaticCardinal ≤ #V :=
H.chromaticCardinal_le (H.isProperColoring_of_injective hk Function.injective_id)
An injective vertex map carrying every edge of F to an edge of H.
def Appears {W V : Type*} (F : UniformHypergraph W k)
(H : UniformHypergraph V k) : Prop :=
∃ φ : W → V, Function.Injective φ ∧
(F.toHypergraph.image φ).edgeSet ⊆ H.edgeSetAppearance is transitive under composition of injective vertex maps.
k:ℕU:Type u_1W:Type u_2V:Type u_3F:UniformHypergraph U kG:UniformHypergraph W kH:UniformHypergraph V kf:U → Whf:Function.Injective fhF:(F.image f).edgeSet ⊆ G.edgeSetg:W → Vhg:Function.Injective ghG:(G.image g).edgeSet ⊆ H.edgeSet⊢ ((F.image f).image g).edgeSet ⊆ H.edgeSet
exact (Set.image_mono hF).trans hG All goals completed! 🐙
A weak proper coloring using at most n colors.
abbrev IsNColorable {V : Type*} (F : UniformHypergraph V k) (n : ℕ) : Prop :=
F.toHypergraph.IsNColorable n
Some hypergraph of the same uniformity and chromatic cardinal κ omits F.
def HasAvoidingChromaticCardinal {W : Type u} (F : UniformHypergraph W k)
(κ : Cardinal.{u}) : Prop :=
∃ (V : Type u) (_ : DecidableEq V) (H : UniformHypergraph V k),
H.chromaticCardinal = κ ∧ ¬ F.Appears H
A finite uniform hypergraph is obligatory if it appears in every hypergraph of
that uniformity whose chromatic cardinal exceeds ℵ₀.
def IsObligatory {W : Type u} [Fintype W] (F : UniformHypergraph W k) : Prop :=
∀ (V : Type u) [DecidableEq V] (H : UniformHypergraph V k),
ℵ₀ < H.chromaticCardinal → F.Appears Hend UniformHypergraph