Erdős Problem #162 — Let α>0\alpha>0 and n≥1n\geq 1.

About 36 years old · traced to

Let α>0\alpha>0 and n≥1n\geq 1. Let F(n,α)F(n,\alpha) be the largest kk such that there exists some 2-colouring of the edges of KnK_n in which any induced subgraph HH on at least kk vertices contains more than α(∣H∣2)\alpha\binom{\lvert H\rvert}{2} many edges of each colour. Prove that for every fixed 0≤α≤1/20\leq \alpha \leq 1/2, as n→∞n\to\infty, F(n,α)∼cαlog⁡nF(n,\alpha)\sim c_\alpha \log n for some constant cαc_\alpha.

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.