Erdős Problem a Daythe open tracker
The board / combinatorics / #162

Erdős Problem #162

OPENdatabase updated 2025-08-31

No proof or disproof is known, and it isn't known whether a finite computation could settle it.

What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).

The number of edges of \(K_n\) inside `H` that get colour `b` under the colouring `c`.

Every set `H` of at least `k` vertices contains more than \(\alpha\binom{|H|}{2}\) edges of each colour under `c`.

\(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`).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 1 further variant / known partial result in the Lean file. The authoritative wording is on erdosproblems.com/162.
Prizenone
Topicscombinatorics, ramsey theory, discrepancy
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/162

Attempts

submit one →
WORKING REPORT BY THIS SITE · JUL 26, 2026

Read our working report →

The live #162 definition is ill-posed—every integer k>n is vacuously admissible, while restricting k≤n gives F(n,α)=n eventually for every α<1/2 and no admissible k at α=1/2.

FOUND
← #161the board#163 →