ErdosProblems · research open · AMS 5

unsolvedsorry — nobody on it

Erdős Problem 563

Conjecture 563 · Erdős

Let F(n,α)F(n,\alpha) denote the smallest mm such that there exists a 22-colouring of the edges of KnK_n so that every X⊆[n]X\subseteq [n] with ∣X∣≥m\lvert X\rvert\geq m contains more than α(∣X∣2)\alpha \binom{\lvert X\rvert}{2} many edges of each colour.

Prove that, for every 0≤α<1/20\leq \alpha < 1/2, F(n,α)∼cαlog⁡nF(n,\alpha)\sim c_\alpha\log n for some constant cαc_\alpha depending only on α\alpha.

This problem is #39 in Ramsey Theory in the graphs problem collection.

Formal statement · Lean 4.lean
theorem erdos_563 :
    ∀ (α : ℝ), 0 ≤ α → α < 1 / 2 →
      ∃ (c : ℝ), 0 < c ∧
        Tendsto (fun n : ℕ => (F n α : ℝ) / Real.log n) atTop (nhds c) := by
  sorry

Proof. sorry

Nobody has tried yet.

Reference ↗ · Lean source ↗