Problem 581

Let $f(m)$ be the maximal $k$ such that a triangle-free graph on $m$ edges must contain a bipartite graph with $k$ edges. Determine $f(m)$ .

Source: erdosproblems.com/581

Graph theory

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

Solved, in the site's estimate sense adopted by this corpus: Alon's Theorem 1.2 [Al96] (Combinatorica 16 (1996), 301--311, refereed; result page) gives absolute constants $c',C'>0$ with

\frac m2+c'm^{4/5}\le f(m)\le\frac m2+C'm^{4/5}\qquad(m>1),

the lower bound for every triangle-free graph with $m$ edges and the upper bound by explicit triangle-free graphs (Proposition 3.2 (Alon 1996)), so $f(m)=m/2+\Theta(m^{4/5})$ and the exponent $4/5$ cannot be improved. The exact value of $f(m)$ and the best constants are not known from any source on record; Alon writes that determining the minimum precisely "seems more difficult" (p. 8). Earlier bounds: Erdős and Lovász, $m/2+\Omega(m^{2/3}(\log m/\log\log m)^{1/3})$ ; Poljak and Tuza, a logarithmic factor better; Shearer, $m/2+\Omega(m^{3/4})$ , and independently the exponent $4/5-\epsilon$ (all quoted from [Al96], pp. 2 and 8). The result and its acceptance evidence are recorded on the claim page Alon's order-of-magnitude determination of f(m), from which the frontmatter is derived with this reading.

Al96: Alon, Noga, Bipartite subgraphs. Combinatorica 16 (1996), no. 3, 301--311, doi:10.1007/BF01261315 (issued September 1996, by its Crossref record); Theorem 1.2 on p. 2 of the author's final version, proof pp. 5--7, Proposition 3.2 p. 7, concluding remarks and Note added in proof p. 8. Library home: Alon 1996 (the author's final version, the copy on Alon's Princeton page; the journal's pagination is not attached to its pages).
CEG79: Chung, F. R. K. and Erdős, P. and Graham, R. L., On the product of the point and line covering numbers of a graph. Second International Conference on Combinatorial Mathematics (New York, 1978), Ann. N. Y. Acad. Sci. 319 (1979), 597--602 (the site's reference text, with the volume from the Rényi archive index). The site's source key. Library home: Chung and Graham 1979 (the Rényi archive's scan 1979-16.pdf; the card carries the row for this problem). The paper does not mention triangle-free graphs or bipartite subgraphs.
Er79: Erdős, P., Problems and results in graph theory and combinatorial analysis. Graph Theory and Related Topics (Proc. Conf. Waterloo, 1977), Academic Press (1979), 153--163. Not held; [Al96] (p. 2, its [6]) cites it for the Erdős--Lovász bound. Library home: Erdős 1979.
Sh92: Shearer, J. B., A note on bipartite subgraphs of triangle-free graphs. Random Structures and Algorithms 3 (1992), 223--226 (as [Al96] lists it, its [16], p. 10). Not held; the bound (3) and inequality (8) of [Al96] are quoted from it.
PoTu94: Poljak, S. and Tuza, Zs., Bipartite subgraphs of triangle-free graphs. SIAM J. Discrete Math. 7 (1994), 307--313. Not held; cited by [Al96] (its [14]).

Problem 581

Status

Proof claims

Discussion