Problem 127

Let $f(m)$ be maximal such that every graph with $m$ edges must contain a bipartite graph with

\geq \frac{m}{2}+\frac{\sqrt{8m+1}-1}{8}+f(m)

edges. Is there an infinite sequence of $m_i$ such that $f(m_i)\to \infty$ ?

Source: erdosproblems.com/127

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED (LEAN). The frontmatter standing is derived from the claim pages under claims/: Alon's refereed theorem is accepted on its publication and the site's acceptance (claim page (Alon, 1996)); the label's Lean suffix is the site's formal status, reflecting the outside Lean formalization of Alon's theorem that is linked on Alon's claim page and that this corpus has not built.

Al96: N. Alon, Bipartite subgraphs, Combinatorica 16 (1996), no. 3, 301-311.
Ed73: C. S. Edwards, Some extremal properties of bipartite subgraphs, Canadian J. Math. 25 (1973), no. 3, 475-485.
Er97b: P. Erdős, Some old and new problems in various branches of combinatorics, Discrete Math. 165/166 (1997), 227-231; item 6 poses the question, and the site cites the paper under this key.
EGK97: P. Erdős, A. Gyárfás, and Y. Kohayakawa, The size of the largest bipartite subgraphs, Discrete Math. 177 (1997), 267-271.
AlHa98: N. Alon and E. Halperin, Bipartite subgraphs of integer weighted graphs, Discrete Math. 181 (1998), 19-29. DOI.
HoLe98: T. Hofmeister and H. Lefmann, On k-partite subgraphs, Ars Combin. 50 (1998), 303-308.
BoSc02: B. Bollobás and A. D. Scott, Better bounds for Max Cut, in Contemporary Combinatorics, Bolyai Soc. Math. Stud. 10 (2002), 185-246.

Problem 127

Status

Proof claims

Discussion