Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let and . Let be the largest such that there exists some 2-colouring of the edges of in which any induced subgraph on at least vertices contains more than many edges of each colour.
Prove that for every fixed , as ,
for some constant .
Let and . Let be the smallest such that there exists some 2-colouring of the edges of in which any induced subgraph on at least vertices contains more than many edges of each colour.
Prove that for every fixed , as ,
for some constant .
Source: erdosproblems.com/162
No claim settles this problem.
Open, the site's label (page last edited 30 December 2025). The corrected Statement is the question of Problem 563, which is open.
The site's wording, accessed 2026-09-04 (last edited on the site on 30 December 2025), fails in three places. With "largest ", every qualifies vacuously, since has no induced subgraph on more than vertices, so no largest exists. If is imposed, a nearly balanced coloring makes qualify for each fixed and all large , so and fails. At no induced subgraph has more than half of its edges in each color, and the opening "Let " conflicts with the range of the display. The change replaces "largest" by "smallest", "" by "", and "Let " by "Let "; nothing else changes. The evidence is Erdős's source [Er90b, printed p. 21], which defines the threshold as "the smallest integer for which it is possible" to give every class more than the share on every large set, and prints the range with its endpoint, , which its next sentence, " as ", excludes. Conlon, Fox and Sudakov [CFS10, Section 6.2] print "largest", as the site does, with the range . So corrected, with two classes, the question is that of Problem 563, which is open; the only known result is the two-sided bound , asserted without proof by Erdős (display (29)) and by Conlon, Fox and Sudakov (Section 6.2). A comment in the site's thread raised the three failures on 28 April 2026; it is a thread post, so it has no claim page. The page's standing judges the corrected Statement.