← All problems

Erdős Problem #162 — Bichromatic density in large vertex subsets

36 years old · traced to

For an integer n≥1n\geq 1, two-colour the edges of the complete graph KnK_n red and blue. For X⊆V(Kn)X\subseteq V(K_n), let eR(X)e_R(X) and eB(X)e_B(X) count the red and blue edges, respectively, in the induced graph on XX. The stated definition takes F(n,α)F(n,\alpha) to be the largest integer kk for which some colouring satisfies

eR(X)>α(∣X∣2)andeB(X)>α(∣X∣2)e_R(X)>\alpha\binom{|X|}{2}\quad\text{and}\quad e_B(X)>\alpha\binom{|X|}{2}

for every XX with ∣X∣≥k|X|\geq k. The question asks whether, for each fixed 0≤α≤120\leq\alpha\leq\tfrac12, there is a constant cαc_\alpha such that

F(n,α)∼cαlog⁡n(n→∞).F(n,\alpha)\sim c_\alpha\log n\qquad(n\to\infty).

The statement first assumes α>0\alpha>0 but then includes α=0\alpha=0 in this request. Moreover, even with the natural restriction 1≤k≤n1\leq k\leq n, the definition makes the requested asymptotic false: for every fixed 0≤α<120\leq\alpha<\tfrac12, a nearly evenly split colouring has both colour classes larger than α(n2)\alpha\binom n2 for all sufficiently large nn. Thus k=nk=n qualifies and F(n,α)=nF(n,\alpha)=n. At α=12\alpha=\tfrac12, no colouring can have both colour classes strictly larger than half the edges, so no such kk qualifies. If kk is not restricted to at most nn, the condition is vacuous for k>nk>n, and a largest kk 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 kk weakens the condition rather than strengthening it. Erdős Problem #162

References

Progress summary

Never refreshed

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.