/-
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 81
References:
[EOZ93] Erdős, Paul and Ordman, Edward T. and Zalcstein, Yechezkel, Clique partitions of chordal graphs. Combin. Probab. Comput. (1993), 409–415.
[CEO94] Chen, Guan-Tao and Erdős, Paul and Ordman, Edward T., Clique partitions of split graphs. Combinatorics, graph theory, algorithms and applications (Beijing, 1993) (1994), 21–30.
@[expose] public sectionnamespace Erdos81open SimpleGraphLet $G$ be a chordal graph on $n$ vertices - that is, $G$ has no induced cycles of length greater than $3$. Can the edges of $G$ be partitioned into $n^2/6+O(n)$ many cliques?
@[category research open, question, AMS 5]
theorem erdos_81 :
∃ C : ℝ, ∀ n : ℕ, ∀ G : SimpleGraph (Fin n), G.IsChordal →
∃ P : Finset (Finset (Fin n)), G.IsCliqueEdgePartition P ∧
(P.card : ℝ) ≤ (n : ℝ) ^ 2 / 6 + C * n := ⊢ ∃ C, ∀ (n : ℕ) (G : SimpleGraph (Fin n)), G.IsChordal → ∃ P, G.IsCliqueEdgePartition P ∧ ↑P.card ≤ ↑n ^ 2 / 6 + C * ↑n
All goals completed! 🐙Chen, Erdős, and Ordman [CEO94] have shown that any split graph can be partitioned into $\frac{3}{16}n^2+O(n)$ many cliques.
@[category research solved, AMS 5]
theorem erdos_81.variants.split :
∃ C : ℝ, ∀ n : ℕ, ∀ G : SimpleGraph (Fin n), G.IsSplitGraph →
∃ P : Finset (Finset (Fin n)), G.IsCliqueEdgePartition P ∧
(P.card : ℝ) ≤ 3 * (n : ℝ) ^ 2 / 16 + C * n := ⊢ ∃ C,
∀ (n : ℕ) (G : SimpleGraph (Fin n)),
G.IsSplitGraph → ∃ P, G.IsCliqueEdgePartition P ∧ ↑P.card ≤ 3 * ↑n ^ 2 / 16 + C * ↑n
All goals completed! 🐙end Erdos81