/-
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.
-/modulepublicimportFormalConjecturesUtil
[Er91] Erdős, P., Problems and results in combinatorial analysis and combinatorial number
theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991),
397-406.
[AlSu07] Alon, N. and Sudakov, B., On graphs with subgraphs having large independence
numbers. J. Graph Theory 56 (2007), 149-157.
arXiv:0706.4099
[ABS21] Alon, N., Bucić, M. and Sudakov, B., Large cliques and independent sets all over the
place. Proc. Amer. Math. Soc. 149 (2021), 3145-3157.
arXiv:2004.04718
@[expose]publicsectionopenFilternamespaceErdos805
IsLocallyRamsey G m k: every set of m vertices of G contains a clique with at least k
vertices and an independent set with at least k vertices.
If every set of m vertices contains a clique and an independent set of size k, so does
every set of m' ≥ m vertices. Thus "every induced subgraph on exactly m vertices" and "every
set of at least m vertices" (the formulation of [ABS21]) agree.
HasRamseyGraphs g: for all sufficiently large n there is a graph on n vertices in
which every induced subgraph on g n vertices contains a clique and an independent set of size
at least $\log n$ (that is, of at least ⌈log n⌉ vertices; log is the natural logarithm).
The answer: the set of functions g with $n>g(n)\geq(\log n)^2$ for which such graphs
exist.
deferdos_805.parts.i.answer:Set(ℕ→ℕ):=sorry
For which functions $g(n)$ with $n>g(n)\geq (\log n)^2$ is there a graph on $n$ vertices in which
every induced subgraph on $g(n)$ vertices contains a clique of size $\geq \log n$ and an
independent set of size $\geq \log n$?
In particular, is there such a graph for $g(n)=(\log n)^3$?
This is the first part. A problem of Erdős and Hajnal [Er91]; see also
erdosproblems.com/804. The inequalities
on g are required for all large n, and a graph is required for all large n.
For which functions $g(n)$ with $n>g(n)\geq (\log n)^2$ is there a graph on $n$ vertices in which
every induced subgraph on $g(n)$ vertices contains a clique of size $\geq \log n$ and an
independent set of size $\geq \log n$?
In particular, is there such a graph for $g(n)=(\log n)^3$?
This is the second part. Erdős and Hajnal thought that there is no such graph for
$g(n)=(\log n)^3$ [AlSu07]; we state the positive proposition, with $g(n)=\lfloor(\log n)^3\rfloor$
and a graph required for all large $n$, as in the first part.
Alon, Bucić, and Sudakov [ABS21] construct such a graph with
$$g(n)\leq 2^{2^{(\log\log n)^{1/2+o(1)}}}.$$
Here all logarithms are to base $2$, as in [ABS21], so the cliques and independent sets have at
least $\lceil\log_2 n\rceil$ vertices; this implies the natural-logarithm version of the problem.
The $o(1)$ is expressed as: for every $0<\varepsilon<1/2$ and all large $n$ there is such a graph
with $g(n)=\lceil 2^{2^{(\log_2\log_2 n)^{1/2+\varepsilon}}}\rceil$. This form, with the rounding,
follows from [ABS21, Theorem 2].