/-
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.Analysis.Asymptotics.Defs
public import Mathlib.Topology.Instances.ENNReal.Lemmas
public import Mathlib.Analysis.SpecialFunctions.Log.Basic@[expose] public sectionExtremal parameters for hypergraphs
Shared counting and local-to-global parameters for uniform hypergraphs, designs, transversals and dense subgraphs. Finite extrema use all labeled edge families; isomorphic copies are not counted separately when counting edges or block-size profiles.
namespace Hypergraphopen Filter
All r-uniform hypergraphs on n vertices with exactly m edges.
def fixedSizeFamilies (n r m : ℕ) : Finset (Finset (Finset (Fin n))) :=
((Finset.univ : Finset (Fin n)).powersetCard r).powersetCard mopen scoped Classical in
Probability of a matching in a uniformly chosen fixed-size edge family.
This is the cardinality of the event divided by that of the finite sample space; it is zero
when m exceeds the number of possible edges.
noncomputable def matchingProbability (n r m k : ℕ) : ℝ :=
((fixedSizeFamilies n r m).filter (fun H ↦ H.HasHypergraphMatching k)).card /
((fixedSizeFamilies n r m).card : ℝ)open scoped Classical in
Smallest independence number of a linear three-uniform hypergraph on n vertices.
noncomputable def linearIndependenceNumber (n : ℕ) : ℕ :=
n - ((((Finset.univ : Finset (Fin n)).powersetCard 3).powerset.filter
Finset.IsLinearHypergraph).sup fun H ↦ n - H.hypergraphIndependenceNumber)Maximum global transversal size under a local vertex-set constraint. Infinity records that no finite bound works.
noncomputable def localTransversalBound (r v a : ℕ) : ℕ∞ :=
⨅ (b : ℕ) (_ : ∀ (n : ℕ) (H : Finset (Finset (Fin n))), H.IsUniform r →
(∀ S : Finset (Fin n), S.card ≤ v →
(H.hypergraphInduce S : Set (Finset (Fin n))).HasFiniteTransversal a) →
(H : Set (Finset (Fin n))).HasFiniteTransversal b), (b : ℕ∞)
Global transversal bound for a uniform family whose small subfamilies have small
transversals. Subfamilies with fewer than q edges are included.
noncomputable def subfamilyTransversalBound (k q a : ℕ) : ℕ∞ :=
⨅ (b : ℕ) (_ : ∀ (V : Type) (F : Set (Finset V)),
(∀ e ∈ F, e.card = k) →
(∀ E : Finset (Finset V), (↑E : Set _) ⊆ F → E.card ≤ q →
(E : Set (Finset V)).HasFiniteTransversal a) → F.HasFiniteTransversal b), (b : ℕ∞)
Least number of edges in an intersecting r-uniform family with transversal size r.
Infinity records a missing witness.
noncomputable def minIntersectingEdges (r : ℕ) : ℕ∞ :=
⨅ (n : ℕ) (H : Finset (Finset (Fin n))) (_ : H.IsUniform r)
(_ : (H : Set (Finset (Fin n))).Intersecting)
(_ : (H : Set (Finset (Fin n))).HasFiniteTransversal r)
(_ : ¬ (H : Set (Finset (Fin n))).HasFiniteTransversal (r - 1)), (H.card : ℕ∞)Least vertex count forcing the Brown--Erdős--Sós little-o conclusion. Infinity records the absence of a finite threshold.
noncomputable def sparseConfigurationThreshold (r e : ℕ) : ℕ∞ :=
⨅ (v : ℕ) (_ : (fun n ↦ (configurationExtremalNumber n r v e : ℝ))
=o[atTop] (fun n ↦ (n : ℝ) ^ 2)), (v : ℕ∞)Edge density normalized by the number of possible uniform edges.
noncomputable def edgeDensity {n : ℕ} (r : ℕ) (H : Finset (Finset (Fin n))) : ℝ :=
(H.card : ℝ) / n.choose rA density increase on growing induced vertex sets for every growing host sequence. The boolean chooses the strict or weak lower bound at the initial density.
def HasDensityJump (r : ℕ) (α β : ℝ) (strict : Bool) : Prop :=
∀ (v : ℕ → ℕ), Tendsto v atTop atTop →
∀ G : (n : ℕ) → Finset (Finset (Fin (v n))),
(∀ n, (G n).IsUniform r) →
(if strict then α < atTop.liminf (fun n ↦ edgeDensity r (G n))
else α ≤ atTop.liminf (fun n ↦ edgeDensity r (G n))) →
∃ S : (n : ℕ) → Finset (Fin (v n)),
Tendsto (fun n ↦ (S n).card) atTop atTop ∧
β < atTop.liminf (fun n ↦ ((G n).hypergraphInduce (S n)).card /
((S n).card.choose r : ℝ))open scoped Classical in
The least size above which a coloring gives both colors a positive share of every
induced complete uniform hypergraph. Positivity at α = 0 retains the Ramsey convention.
noncomputable def balancedColoringThreshold (n r : ℕ) (α : ℝ) : ℕ :=
sInf {m | ∃ c : Finset (Fin n) → Bool, ∀ X : Finset (Fin n), m ≤ X.card →
∀ b : Bool, let count := ((X.powersetCard r).filter (fun e ↦ c e = b)).card
0 < count ∧ α * (X.card.choose r : ℝ) ≤ count}end Hypergraph