/-
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 78
References:
[Co15] Cohen, Gil, Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs. arXiv:1506.04428 (2015).
[Er47] Erdős, P., Some remarks on the theory of graphs. Bull. Amer. Math. Soc. (1947), 292-294.
[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.
[Er88] Erdős, P, Problems and results in combinatorial analysis and graph theory. Discrete Math. (1988), 81-92.
[Er93] Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. (1993), 333-350.
[Er95] Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186.
[Er97c] Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67.
[Li23b] Li, Xin, Two source extractors for asymptotically optimal entropy, and (many) more. arXiv:2303.06802 (2023).
[Va99] Various, Some of Paul's favorite problems. Booklet produced for the conference "Paul Erdős and his mathematics", Budapest, July 1999 (1999).
@[expose] public sectionopen Filter Real ComplexityTheorynamespace Erdos78
The graph on Fin n described by an adjacency oracle adj. Two distinct vertices u and v
are adjacent if adj (1ⁿ, u, v) or adj (1ⁿ, v, u) is true.
The number of vertices is given in unary, as the list List.replicate n true. So if adj is
computable in polynomial time, then the whole graph on n vertices is computable in time
polynomial in n. This is the notion of a weakly explicit family of graphs; compare
stronglyExplicitGraph.
def explicitGraph (adj : List Bool × ℕ × ℕ → Bool) (n : ℕ) : SimpleGraph (Fin n) :=
SimpleGraph.fromRel fun u v ↦ adj (List.replicate n true, u, v)
The graph on Fin n described by an adjacency oracle adj which receives n in binary. Two
distinct vertices u and v are adjacent if adj (n, u, v) or adj (n, v, u) is true.
If adj is computable in polynomial time, then each adjacency query is answered in time
polynomial in $\log n$. This is the notion of a strongly explicit family of graphs, which is
what "explicit Ramsey graph" usually means in the literature (e.g. [Co15], [Li23b]). Compare
explicitGraph, where only time polynomial in $n$ is allowed.
def stronglyExplicitGraph (adj : ℕ × ℕ × ℕ → Bool) (n : ℕ) : SimpleGraph (Fin n) :=
SimpleGraph.fromRel fun u v ↦ adj (n, u, v)
The graph G has no clique and no independent set with m vertices.
def NoHomogeneousSet {V : Type*} (G : SimpleGraph V) (m : ℕ) : Prop :=
G.CliqueFree m ∧ Gᶜ.CliqueFree mLet $R(k)$ be the Ramsey number for $K_k$. Give a constructive proof that $R(k) > C^k$ for some constant $C > 1$.
Equivalently, give an explicit construction of graphs on $n$ vertices which contain no clique and no independent set of size $\geq c \log n$, for some constant $c > 0$.
We formalise "explicit" as: the adjacency relation of the graph on $n$ vertices is decided by a
single algorithm that runs in time polynomial in $n$ (see explicitGraph). This is the weakest
reasonable notion ("weakly explicit"); even this is open. The strongly explicit version, with time
polynomial in $\log n$, is erdos_78.variants.strongly_explicit.
This problem is #4 in Ramsey Theory in the graphs problem collection.
@[category research open, AMS 5 68]
theorem erdos_78 :
∃ c > (0 : ℝ), ∃ adj : List Bool × ℕ × ℕ → Bool, IsPolyTime adj ∧
∀ᶠ n in atTop, NoHomogeneousSet (explicitGraph adj n) ⌈c * log n⌉₊ := ⊢ ∃ c > 0, ∃ adj, IsPolyTime adj ∧ ∀ᶠ (n : ℕ) in atTop, NoHomogeneousSet (explicitGraph adj n) ⌈c * log ↑n⌉₊
All goals completed! 🐙Erdős [Er47] gave a simple probabilistic, non-constructive proof that $R(k) > C^k$ for some constant $C > 1$. In fact $R(k) > 2^{k/2}$ for all $k \geq 3$.
@[category research solved, AMS 5]
theorem erdos_78.variants.nonconstructive :
∃ C > (1 : ℝ), ∀ᶠ k in atTop, C ^ k < (SimpleGraph.diagonalRamsey k : ℝ) := ⊢ ∃ C > 1, ∀ᶠ (k : ℕ) in atTop, C ^ k < ↑(SimpleGraph.diagonalRamsey k)
All goals completed! 🐙Erdős also asked for an explicit construction of graphs on $n$ vertices whose largest clique and independent set have size $o(n^{1/2})$. Such constructions are now known; see [Co15] for the history.
@[category research solved, AMS 5 68]
theorem erdos_78.variants.little_o_sqrt :
∃ f : ℕ → ℝ, f =o[atTop] (fun n ↦ √(n : ℝ)) ∧
∃ adj : List Bool × ℕ × ℕ → Bool, IsPolyTime adj ∧
∀ᶠ n in atTop, NoHomogeneousSet (explicitGraph adj n) ⌈f n⌉₊ := ⊢ ∃ f,
(f =o[atTop] fun n ↦ √↑n) ∧ ∃ adj, IsPolyTime adj ∧ ∀ᶠ (n : ℕ) in atTop, NoHomogeneousSet (explicitGraph adj n) ⌈f n⌉₊
All goals completed! 🐙Cohen [Co15] constructed explicit graphs on $n$ vertices with no clique and no independent set of size $2^{(\log \log n)^C}$, for some constant $C > 0$.
@[category research solved, AMS 5 68]
theorem erdos_78.variants.cohen :
∃ C > (0 : ℝ), ∃ adj : List Bool × ℕ × ℕ → Bool, IsPolyTime adj ∧
∀ᶠ n in atTop,
NoHomogeneousSet (explicitGraph adj n) ⌈(2 : ℝ) ^ (log (log n)) ^ C⌉₊ := ⊢ ∃ C > 0, ∃ adj, IsPolyTime adj ∧ ∀ᶠ (n : ℕ) in atTop, NoHomogeneousSet (explicitGraph adj n) ⌈2 ^ log (log ↑n) ^ C⌉₊
All goals completed! 🐙Li [Li23b] improved this to explicit graphs on $n$ vertices with no clique and no independent set of size $(\log n)^C$, for some constant $C > 0$.
@[category research solved, AMS 5 68]
theorem erdos_78.variants.li :
∃ C > (0 : ℝ), ∃ adj : List Bool × ℕ × ℕ → Bool, IsPolyTime adj ∧
∀ᶠ n in atTop, NoHomogeneousSet (explicitGraph adj n) ⌈(log n) ^ C⌉₊ := ⊢ ∃ C > 0, ∃ adj, IsPolyTime adj ∧ ∀ᶠ (n : ℕ) in atTop, NoHomogeneousSet (explicitGraph adj n) ⌈log ↑n ^ C⌉₊
All goals completed! 🐙
The strongly explicit version of erdos_78: an explicit family of graphs on $n$ vertices with no
clique and no independent set of size $\geq c \log n$, where each adjacency query is answered in
time polynomial in $\log n$ (see stronglyExplicitGraph).
@[category research open, AMS 5 68]
theorem erdos_78.variants.strongly_explicit :
∃ c > (0 : ℝ), ∃ adj : ℕ × ℕ × ℕ → Bool, IsPolyTime adj ∧
∀ᶠ n in atTop, NoHomogeneousSet (stronglyExplicitGraph adj n) ⌈c * log n⌉₊ := ⊢ ∃ c > 0, ∃ adj, IsPolyTime adj ∧ ∀ᶠ (n : ℕ) in atTop, NoHomogeneousSet (stronglyExplicitGraph adj n) ⌈c * log ↑n⌉₊
All goals completed! 🐙The construction of Li [Li23b] is strongly explicit: there are graphs on $n$ vertices with no clique and no independent set of size $(\log n)^C$, for some constant $C > 0$, whose adjacency queries are answered in time polynomial in $\log n$.
@[category research solved, AMS 5 68]
theorem erdos_78.variants.li_strongly_explicit :
∃ C > (0 : ℝ), ∃ adj : ℕ × ℕ × ℕ → Bool, IsPolyTime adj ∧
∀ᶠ n in atTop, NoHomogeneousSet (stronglyExplicitGraph adj n) ⌈(log n) ^ C⌉₊ := ⊢ ∃ C > 0, ∃ adj, IsPolyTime adj ∧ ∀ᶠ (n : ℕ) in atTop, NoHomogeneousSet (stronglyExplicitGraph adj n) ⌈log ↑n ^ C⌉₊
All goals completed! 🐙end Erdos78