Erdős Problem #162 — Bichromatic density in large vertex subsets
For an integer , two-colour the edges of the complete graph red and blue. For , let and count the red and blue edges, respectively, in the induced graph on . The stated definition takes to be the largest integer for which some colouring satisfies
for every with . The question asks whether, for each fixed , there is a constant such that
The statement first assumes but then includes in this request. Moreover, even with the natural restriction , the definition makes the requested asymptotic false: for every fixed , a nearly evenly split colouring has both colour classes larger than for all sufficiently large . Thus qualifies and . At , no colouring can have both colour classes strictly larger than half the edges, so no such qualifies. If is not restricted to at most , the condition is vacuous for , and a largest does not exist. Erdős Problem #162
Background
The page indexes the problem under combinatorics, Ramsey theory, and discrepancy, and cites it as [Er90b, p. 21]. Its formulation concerns a hereditary balance condition: every induced subgraph above a size threshold must have substantial numbers of edges of both colours. The size-threshold direction is consequential here, because increasing weakens the condition rather than strengthening it. Erdős Problem #162
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.