/-
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 FormalConjecturesUtilErdős Problem 1017
References:
[EGP66] Erdős, Paul and Goodman, A. W. and Pósa, Lajos, The representation of a graph by set intersections. Canadian J. Math. (1966), 106–112.
[Er71] Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97–109.
[GyKe17] Győri, Ervin and Keszegh, Balázs, On the number of edge-disjoint triangles in $K_4$-free graphs. Combinatorica (2017), 1113–1124.
[Lo68] Lovász, L., On covering of graphs. Theory of Graphs (Proc. Colloq., Tihany, 1966) (1968), 231–236.
@[expose] public sectionnamespace Erdos1017open SimpleGraphThe least uniform bound on the number of cliques in an edge partition of an $n$-vertex, $k$-edge graph. For infeasible parameters the value is zero.
noncomputable def f (n k : ℕ) : ℕ :=
sInf {m : ℕ | ∀ G : SimpleGraph (Fin n), G.edgeSet.ncard = k →
∃ P : Finset (Finset (Fin n)), G.IsCliqueEdgePartition P ∧ P.card ≤ m}Partitioning into individual edges gives the bound $f(n,k) \le k$.
@[category API, AMS 5]
theorem f_le (n k : ℕ) : f n k ≤ k := n:ℕk:ℕ⊢ f n k ≤ k
classical
n:ℕk:ℕ⊢ k ∈ {m | ∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m}
n:ℕk:ℕG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = k⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ k
n:ℕk:ℕG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = kP:Finset (Finset (Fin n))hP:G.IsCliqueEdgePartition Phcard:P.card = G.edgeFinset.card⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ k
n:ℕk:ℕG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = kP:Finset (Finset (Fin n))hP:G.IsCliqueEdgePartition Phcard:P.card = G.edgeFinset.card⊢ P.card ≤ k
All goals completed! 🐙The infimum defining $f$ is an attained uniform bound.
n:ℕk:ℕG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = khne:{m | ∀ (H : SimpleGraph (Fin n)), H.edgeSet.ncard = k → ∃ P, H.IsCliqueEdgePartition P ∧ P.card ≤ m}.Nonempty⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ f n k
exact Nat.sInf_mem hne G hG All goals completed! 🐙A graph with no edges needs no cliques in its edge partition.
@[category test, AMS 5]
theorem f_zero (n : ℕ) : f n 0 = 0 := Nat.eq_zero_of_le_zero (f_le n 0)A proposed uniform bound is valid exactly when it is at least $f(n,k)$.
@[category API, AMS 5]
theorem f_le_iff (n k m : ℕ) : f n k ≤ m ↔
∀ G : SimpleGraph (Fin n), G.edgeSet.ncard = k →
∃ P : Finset (Finset (Fin n)), G.IsCliqueEdgePartition P ∧ P.card ≤ m := by n:ℕk:ℕm:ℕ⊢ f n k ≤ m ↔ ∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m
constructor mp n:ℕk:ℕm:ℕ⊢ f n k ≤ m → ∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ mmpr n:ℕk:ℕm:ℕ⊢ (∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m) → f n k ≤ m
· mp n:ℕk:ℕm:ℕ⊢ f n k ≤ m → ∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m intro h G hG mp n:ℕk:ℕm:ℕh:f n k ≤ mG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = k⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m
obtain ⟨P, hP, hcard⟩ := partition_card_le_f n k G hG mp n:ℕk:ℕm:ℕh:f n k ≤ mG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = kP:Finset (Finset (Fin n))hP:G.IsCliqueEdgePartition Phcard:P.card ≤ f n k⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m
exact ⟨P, hP, hcard.trans h⟩ All goals completed! 🐙
· mpr n:ℕk:ℕm:ℕ⊢ (∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m) → f n k ≤ m intro h mpr n:ℕk:ℕm:ℕh:∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m⊢ f n k ≤ m
apply Nat.sInf_le mpr n:ℕk:ℕm:ℕh:∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m⊢ m ∈ {m | ∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ m}
exact h All goals completed! 🐙Impossible edge counts give the vacuous value zero and are excluded from the question.
@[category test, AMS 5]
theorem f_eq_zero_of_infeasible (n k : ℕ) (hk : n.choose 2 < k) : f n k = 0 := by n:ℕk:ℕhk:n.choose 2 < k⊢ f n k = 0
classical
apply Nat.eq_zero_of_le_zero n:ℕk:ℕhk:n.choose 2 < k⊢ f n k ≤ 0
rw [f_le_iff n:ℕk:ℕhk:n.choose 2 < k⊢ ∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ 0 n:ℕk:ℕhk:n.choose 2 < k⊢ ∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ 0] n:ℕk:ℕhk:n.choose 2 < k⊢ ∀ (G : SimpleGraph (Fin n)), G.edgeSet.ncard = k → ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ 0
intro G hG n:ℕk:ℕhk:n.choose 2 < kG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = k⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ 0
have hcard := G.card_edgeFinset_le_card_choose_two n:ℕk:ℕhk:n.choose 2 < kG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = khcard:G.edgeFinset.card ≤ (Fintype.card (Fin n)).choose 2⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ 0
have : G.edgeFinset.card = k := by n:ℕk:ℕhk:n.choose 2 < k⊢ f n k = 0 n:ℕk:ℕhk:n.choose 2 < kG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = khcard:G.edgeFinset.card ≤ (Fintype.card (Fin n)).choose 2this:G.edgeFinset.card = k⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ 0
simpa [← SimpleGraph.coe_edgeFinset, Set.ncard_coe_finset] using hG n:ℕk:ℕhk:n.choose 2 < kG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = khcard:G.edgeFinset.card ≤ (Fintype.card (Fin n)).choose 2this:G.edgeFinset.card = k⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ 0 n:ℕk:ℕhk:n.choose 2 < kG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = khcard:G.edgeFinset.card ≤ (Fintype.card (Fin n)).choose 2this:G.edgeFinset.card = k⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ 0
simp only [Fintype.card_fin, this] at hcard n:ℕk:ℕhk:n.choose 2 < kG:SimpleGraph (Fin n)hG:G.edgeSet.ncard = kthis:G.edgeFinset.card = khcard:k ≤ n.choose 2⊢ ∃ P, G.IsCliqueEdgePartition P ∧ P.card ≤ 0
omega All goals completed! 🐙def erdos_1017.lower_bound.answer (n k : ℕ) : ℕ := by n:ℕk:ℕ⊢ ℕ sorry All goals completed! 🐙Let $f(n,k)$ be such that every graph on $n$ vertices and $k$ edges can be partitioned into at most $f(n,k)$ edge-disjoint complete graphs. Estimate $f(n,k)$ for $k>n^2/4$.
@[category research open, question value, AMS 5]
theorem erdos_1017.lower_bound :
∀ n k : ℕ, k ≤ n.choose 2 → n * n < 4 * k →
erdos_1017.lower_bound.answer n k ≤ f n k := by ⊢ ∀ (n k : ℕ), k ≤ n.choose 2 → n * n < 4 * k → lower_bound.answer n k ≤ f n k
sorry All goals completed! 🐙def erdos_1017.upper_bound.answer (n k : ℕ) : ℕ := by n:ℕk:ℕ⊢ ℕ sorry All goals completed! 🐙Estimate an upper bound for $f(n,k)$, the worst-case number of complete subgraphs needed to partition the edges of an $n$-vertex, $k$-edge graph, for $n^2/4 < k \le \binom{n}{2}$.
@[category research open, question value, AMS 5]
theorem erdos_1017.upper_bound :
∀ n k : ℕ, k ≤ n.choose 2 → n * n < 4 * k →
f n k ≤ erdos_1017.upper_bound.answer n k := by ⊢ ∀ (n k : ℕ), k ≤ n.choose 2 → n * n < 4 * k → f n k ≤ upper_bound.answer n k
sorry All goals completed! 🐙end Erdos1017