/-
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 611
References:
[EGT92] Erdős, Paul and Gallai, Tibor and Tuza, Zsolt, Covering the cliques of a graph with vertices. Discrete Math. (1992), 279-289.
[Er94] Erdős, P., Problems and results on set systems and hypergraphs. Extremal problems for finite sets (Visegrád, 1991) (1994), 217-227.
[Er99] Erdős, Paul, A selection of problems and results in combinatorics. Combin. Probab. Comput. (1999), 1-6.
@[expose] public sectionopen Filternamespace Erdos611
AllMaximalCliquesAtLeast G k means that every maximal clique of G has at least k
vertices.
def AllMaximalCliquesAtLeast {V : Type} (G : SimpleGraph V) (k : ℝ) : Prop :=
∀ s ∈ G.cliqueSizes, k ≤ (s : ℝ)
cliqueThreshold c n is $k_c(n)$: the least $k$ such that every graph on $n$ vertices whose
maximal cliques all have at least $k$ vertices satisfies $\tau(G) < (1 - c)n$.
For large $n$ only $k \geq 2$ matters, since some triangle-free graph has $\tau(G) \geq (1 - c)n$; so ignoring maximal cliques on one vertex does not change $k_c(n)$ asymptotically.
noncomputable def cliqueThreshold (c : ℝ) (n : ℕ) : ℕ :=
sInf {k : ℕ | ∀ G : SimpleGraph (Fin n), AllMaximalCliquesAtLeast G (k : ℝ) →
(G.cliqueTransversalNumber : ℝ) < (1 - c) * (n : ℝ)}For a graph $G$ let $\tau(G)$ denote the minimal number of vertices that include at least one from each maximal clique of $G$. Is it true that if all maximal cliques in $G$ have at least $cn$ vertices then $\tau(G) = o_c(n)$?
Here $n$ is the number of vertices, and $o_c(n)$ is uniform over all such graphs on $n$ vertices.
$\tau(G)$ is SimpleGraph.cliqueTransversalNumber, which (as in Erdős Problem 151) ignores
maximal cliques on one vertex; this makes no difference here, since for large $n$ every maximal
clique has at least $cn \geq 2$ vertices.
@[category research open, question, AMS 5]
theorem erdos_611.parts.i :
∀ c > (0 : ℝ), ∀ ε > (0 : ℝ), ∀ᶠ n : ℕ in atTop, ∀ G : SimpleGraph (Fin n),
AllMaximalCliquesAtLeast G (c * (n : ℝ)) →
(G.cliqueTransversalNumber : ℝ) ≤ ε * (n : ℝ) := ⊢ ∀ c > 0,
∀ ε > 0,
∀ᶠ (n : ℕ) in atTop,
∀ (G : SimpleGraph (Fin n)), AllMaximalCliquesAtLeast G (c * ↑n) → ↑G.cliqueTransversalNumber ≤ ε * ↑n
All goals completed! 🐙def erdos_611.parts.ii.answer : ℝ → ℕ → ℝ := sorryFor $0 < c < 1$, estimate the minimal $k_c(n)$ such that if every maximal clique in a graph $G$ on $n$ vertices has at least $k_c(n)$ vertices then $\tau(G) < (1 - c)n$.
We require $c < 1$: for $c \geq 1$ the bound $\tau(G) < (1 - c)n \leq 0$ is impossible, so $k_c(n)$ is degenerate. Erdős, Gallai, and Tuza [EGT92] proved a lower bound of the form $k_c(n) \geq n^{c'/\log\log n}$ for some $c' > 0$ (as reported on erdosproblems.com).
@[category research open, question value, AMS 5]
theorem erdos_611.parts.ii :
∀ c : ℝ, 0 < c → c < 1 →
(fun n ↦ (cliqueThreshold c n : ℝ)) =Θ[atTop] erdos_611.parts.ii.answer c := ⊢ ∀ (c : ℝ), 0 < c → c < 1 → (fun n ↦ ↑(cliqueThreshold c n)) =Θ[atTop] ii.answer c
All goals completed! 🐙Bollobás and Erdős proved that if every maximal clique of a graph $G$ on $n$ vertices has at least $n + 3 - 2\sqrt{n}$ vertices then $\tau(G) = 1$ (as reported on erdosproblems.com).
@[category research solved, AMS 5]
theorem erdos_611.variants.bollobas_erdos :
∀ n : ℕ, ∀ G : SimpleGraph (Fin n),
AllMaximalCliquesAtLeast G ((n : ℝ) + 3 - 2 * Real.sqrt (n : ℝ)) →
G.cliqueTransversalNumber = 1 := ⊢ ∀ (n : ℕ) (G : SimpleGraph (Fin n)), AllMaximalCliquesAtLeast G (↑n + 3 - 2 * √↑n) → G.cliqueTransversalNumber = 1
All goals completed! 🐙The threshold $n + 3 - 2\sqrt{n}$ of Bollobás and Erdős is best possible. We formalise this as: for every $n = m^2$ with $m \geq 2$ there is a graph on $n$ vertices whose maximal cliques all have at least $n + 2 - 2\sqrt{n} = m^2 + 2 - 2m$ vertices and with $\tau(G) \geq 2$.
@[category research solved, AMS 5]
theorem erdos_611.variants.bollobas_erdos_sharp :
∀ m : ℕ, 2 ≤ m → ∃ G : SimpleGraph (Fin (m ^ 2)),
AllMaximalCliquesAtLeast G ((m : ℝ) ^ 2 + 2 - 2 * (m : ℝ)) ∧
2 ≤ G.cliqueTransversalNumber := ⊢ ∀ (m : ℕ), 2 ≤ m → ∃ G, AllMaximalCliquesAtLeast G (↑m ^ 2 + 2 - 2 * ↑m) ∧ 2 ≤ G.cliqueTransversalNumber
All goals completed! 🐙end Erdos611