Erdős problem #162, wave 5k
Date: 2026-07-26 (UTC)
Claim labels
- (a) elementary-rigorous: a complete elementary proof is given here.
- (b) rigorous-modulo-named-theorem: no claim in this report uses this label.
- (c) plausible/structural-unverified: an interpretation is suggested but not adopted as the problem.
- (d) computational-only: a live-page observation, bibliographic search result, or finite exact computation. Such a claim is not promoted to a theorem.
Step 0: live-page audit
I fetched the JavaScript-rendered live problem page, its discussion thread, its LaTeX endpoint, and its revision history through a Bright Data browser on 2026-07-26. (d)
The live page said OPEN, 0 claimed proofs for this problem, Interested in collaborating: None, and Currently working on this problem: None. It listed four comments and was last edited on 30 December 2025. Thus neither mandatory stop condition applied. (d)
Verbatim live statement
> 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{\lvert H\rvert}{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$.
The only listed known result was, verbatim:
> 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.\]
All four comments and activity markers
The comments, in their displayed order, were as follows. These are page observations, not endorsed mathematical claims. (d)
1. yeyito, 28 April 2026, pointed out that “largest \(k\)” may need to be “smallest \(k\)”: every \(k>n\) is vacuous; even with \(k\le n\), a nearly balanced coloring makes \(k=n\) admissible for fixed \(\alpha<1/2\); and \(\alpha=1/2\) is incompatible with strict “more than.” The comment suggested “smallest \(k\)” and \(0\le\alpha<1/2\).
2. KoishiChan, 4 December 2025, asked whether “in any 2-coloring” should be “there exists some 2-coloring.” The page says it was updated in response.
3. TerenceTao, 29 December 2025, said that, judging from the original source, the preceding interpretation appears correct.
4. Wouter CvB, 29 December 2025, suggested changing “subgraph” to “induced subgraph.” The page says it was updated in response.
The other displayed markers—likes, “looks difficult,” “looks tractable,” formalisability interest, and active formalisation—were all None. (d)
Result: the live statement is not a well-defined open problem
1. Literal reading: there is no largest \(k\)
Fix any \(n\ge1\), any \(\alpha\), and any integer \(k>n\). There is no induced subgraph of \(K_n\) on at least \(k\) vertices. Therefore the universal assertion about all such induced subgraphs is true vacuously, for every two-coloring. Hence every integer
\[ k=n+1,n+2,n+3,\ldots \]is admissible. The admissible set is unbounded and has no largest member. Thus the displayed definition does not define \(F(n,\alpha)\). (a)
This is already a complete fatal obstruction, independent of probability, Ramsey theory, or computation. (a)
2. Even after imposing the unstated restriction \(1\le k\le n\), the answer is eventually \(n\)
Suppose, only to test the strongest obvious repair, that “largest \(k\)” implicitly means largest \(k\in\{1,\ldots,n\}\). Fix \(0\le\alpha<1/2\), let
\[ M=\binom n2, \]and color \(\lfloor M/2\rfloor\) edges red and all other edges blue. If \(k=n\), the only tested induced subgraph is \(K_n\) itself. Each color has at least \(\lfloor M/2\rfloor\) edges. Since
\[ \left\lfloor\frac M2\right\rfloor\ge \frac{M-1}{2}, \]both color counts are strictly greater than \(\alpha M\) whenever
\[ (1-2\alpha)M>1. \tag{1} \]For fixed \(\alpha<1/2\), (1) holds for every sufficiently large \(n\). Therefore \(k=n\) is admissible, and as \(n\) is the largest allowed value,
\[ F(n,\alpha)=n \]for all sufficiently large \(n\) under this hypothetical restriction. In particular \(F(n,\alpha)/\log n\to\infty\), not to a finite constant. (a)
This proof includes \(\alpha=0\): condition (1) holds once \(\binom n2>1\). (a)
3. The endpoint \(\alpha=1/2\) is impossible under the restriction \(k\le n\)
For any induced subgraph \(H\), let \(r(H)\) and \(b(H)\) be its red and blue edge counts. Then
\[ r(H)+b(H)=\binom{|H|}{2}. \]They cannot both be strictly greater than half of their sum. If \(k\le n\), the full vertex set \(H=K_n\) is among the tested subgraphs, so no coloring and no such \(k\) is admissible at \(\alpha=1/2\). The restricted definition is again undefined. (a)
4. Consequence for the page's displayed “known result”
On the literal reading, \(F(n,\alpha)\) is undefined. Under the unstated \(k\le n\) reading, it equals \(n\) eventually for every fixed \(\alpha<1/2\). Thus the displayed logarithmic upper and lower bounds cannot apply to the definition currently printed on #162. (a)
What appears to have been intended
The site's separate problem #563, also attributed to [Er90b,p.21], defines \(F(n,\alpha)\) using the smallest \(m\) and states the range \(0\le\alpha<1/2\). It was live, open, had zero claimed proofs, and no current worker when checked. (d)
Together with the first #162 comment, this strongly suggests that #162 is a malformed duplicate of #563. This is an inference only; under the task's instruction that #162's live statement is authoritative, I did not replace the statement by #563 and did not claim progress on that different problem. (c)
Literature search
The page's cited item really exists: Paul Erdős, “Problems and Results on Graphs and Hypergraphs: Similarities and Differences,” in Mathematics of Ramsey Theory, pp. 12–28 (1990), DOI 10.1007/978-3-642-72905-8_2. Springer verifies the title, author, year, page range, and DOI. (d)
Springer's available view was a subscription preview and did not expose p. 21, so I could not independently quote the original wording. I therefore make no claim here about which of #162 or #563 exactly transcribes Erdős's quantifiers. (d)
I searched exact fragments of the displayed definition and formula, the title/DOI citation graph, and combinations of “induced subgraph,” “edges of each colour,” \(F(n,\alpha)\), and \(c_\alpha\log n\). The only exact candidates found were the Erdős Problems entries and their mirrors/search indexes; I found no primary paper that addresses the malformed literal definition. This is a search miss, not a proof that no such literature exists. (d)
No named theorem is needed for the diagnosis above. (a)
Independent exact checker
The standalone checker is runs/erdos162_wave5k_verify.py. It uses only the Python standard library and fractions.Fraction. It:
1. directly enumerates the family of tested vertex subsets and confirms vacuity for representative \(k>n\);
2. constructs the balanced coloring and verifies its \(k=n\) certificate for exact rational \(\alpha\)'s;
3. exhausts all \(2^{\binom n2}\) colorings for \(n\le5\) at \(\alpha=1/2\); and
4. separately checks every possible red/blue total-edge split for \(n\le50\).
These finite checks are only sanity checks; unbounded vacuity and the eventual balanced construction are established by the elementary proofs above. (d)/(a)
Run:
$ python3 runs/erdos162_wave5k_verify.py
vacuity: exact checks passed for k=n+1,...,10^6
balanced k=n certificates under the hypothetical restriction k<=n:
alpha sufficient N checks
0 3 all n in [3,28]
1/4 3 all n in [3,28]
2/5 4 all n in [4,29]
49/100 11 all n in [11,36]
499/1000 33 all n in [33,58]
alpha=1/2: exhausted 1099 colorings for n<=5 and all edge-count splits for n<=50
ALL CHECKS PASSED
The complete checker source is:
#!/usr/bin/env python3
"""From-scratch exact checks for the diagnosis of Erdős Problems page #162.
Only the Python standard library is used. All density comparisons are made
with fractions, so no floating-point rounding enters the certificates.
"""
from __future__ import annotations
from fractions import Fraction
from itertools import combinations
from math import comb
Edge = tuple[int, int]
def all_edges(n: int) -> list[Edge]:
return list(combinations(range(n), 2))
def balanced_coloring(n: int) -> frozenset[Edge]:
"""Color floor(C(n,2)/2) lexicographically first edges red; the rest blue."""
edges = all_edges(n)
return frozenset(edges[: len(edges) // 2])
def property_holds(
n: int, alpha: Fraction, k: int, red_edges: frozenset[Edge]
) -> bool:
"""Check the property printed on page #162 for one coloring."""
assert n >= 1
assert k >= 1
assert Fraction(0) <= alpha <= Fraction(1, 2)
universe = set(all_edges(n))
assert set(red_edges) <= universe
vertices = range(n)
for size in range(k, n + 1):
for subset_tuple in combinations(vertices, size):
subset = set(subset_tuple)
total = comb(size, 2)
red = sum(
(u, v) in red_edges
for u, v in combinations(sorted(subset), 2)
)
blue = total - red
if not (red > alpha * total and blue > alpha * total):
return False
return True
def eventual_threshold(alpha: Fraction) -> int:
"""A sufficient N such that the balanced k=n certificate works for n>=N.
We use floor(M/2) >= (M-1)/2. Thus it suffices that
(1-2*alpha) M > 1, M=C(n,2).
"""
assert Fraction(0) <= alpha < Fraction(1, 2)
n = 1
while (1 - 2 * alpha) * comb(n, 2) <= 1:
n += 1
return n
def check_vacuity() -> None:
# For k>n, range(k,n+1) is empty: there are no tested induced subgraphs.
for n in range(1, 10):
for alpha in (
Fraction(0),
Fraction(1, 10),
Fraction(2, 5),
Fraction(1, 2),
):
red = balanced_coloring(n)
for k in (n + 1, n + 2, 2 * n + 17, 10**6):
number_of_tested_subsets = sum(
comb(n, size) for size in range(k, n + 1)
)
assert number_of_tested_subsets == 0
assert property_holds(n, alpha, k, red)
print("vacuity: exact checks passed for k=n+1,...,10^6")
def check_balanced_certificates() -> None:
alphas = (
Fraction(0),
Fraction(1, 4),
Fraction(2, 5),
Fraction(49, 100),
Fraction(499, 1000),
)
print("balanced k=n certificates under the hypothetical restriction k<=n:")
print("alpha\tsufficient N\tchecks")
for alpha in alphas:
threshold = eventual_threshold(alpha)
for n in range(threshold, threshold + 26):
m = comb(n, 2)
red = balanced_coloring(n)
assert len(red) == m // 2
assert m - len(red) == (m + 1) // 2
assert (1 - 2 * alpha) * m > 1
assert property_holds(n, alpha, n, red)
print(f"{alpha}\t{threshold}\tall n in [{threshold},{threshold + 25}]")
def check_endpoint() -> None:
half = Fraction(1, 2)
# Exhaust all 2^C(n,2) colorings for n<=5. The full vertex set already
# prevents the page's property for every k<=n.
checked_colorings = 0
for n in range(1, 6):
edges = all_edges(n)
for mask in range(1 << len(edges)):
red = frozenset(
edge for index, edge in enumerate(edges) if mask & (1 << index)
)
checked_colorings += 1
for k in range(1, n + 1):
assert not property_holds(n, half, k, red)
# Direct arithmetic certificate for every possible red count and n<=50:
# red+blue=M makes red>M/2 and blue>M/2 mutually impossible.
for n in range(1, 51):
m = comb(n, 2)
for red_count in range(m + 1):
blue_count = m - red_count
assert not (2 * red_count > m and 2 * blue_count > m)
print(
"alpha=1/2: exhausted "
f"{checked_colorings} colorings for n<=5 and all edge-count splits for n<=50"
)
def main() -> None:
check_vacuity()
check_balanced_certificates()
check_endpoint()
print("ALL CHECKS PASSED")
if __name__ == "__main__":
main()
FOUND: 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.