/-
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
$F(n, \alpha)$: the smallest k such that some 2-colouring of $K_n$ satisfies
IsBalancedAbove n α c k.
The source says "largest k". Read literally, every k > n works vacuously, so no largest k
exists. The smallest k is the reading consistent with the stated $\Theta(\log n)$ growth.
Let $\alpha > 0$ and $n \geq 1$. Let $F(n,\alpha)$ be the largest $k$ such that there exists some
2-colouring of the edges of $K_n$ in which any induced subgraph $H$ on at least $k$ vertices
contains more than $\alpha\binom{|H|}{2}$ many edges of each colour.
Prove that for every fixed $0 \leq \alpha \leq 1/2$, as $n \to \infty$,
$F(n,\alpha) \sim c_\alpha \log n$ for some constant $c_\alpha$.
We require $\alpha < 1/2$: at $\alpha = 1/2$ no colouring works for any k ≤ n
(see erdos_162.variants.half).
It is easy to show with the probabilistic method that there exist $c_1(\alpha), c_2(\alpha)$ such
that $c_1(\alpha)\log n < F(n,\alpha) < c_2(\alpha)\log n$.
At $\alpha = 1/2$ the two colour counts in $H$ add up to $\binom{|H|}{2}$, so both cannot exceed
half of it. Hence $F(n, 1/2) = n + 1$, and the claim fails at $\alpha = 1/2$.