# A problem on bipartite subgraphs of triangle-free graphs[2]

Let $$f(m)$$ denote that largest integer $$t$$ so that a triangle-free graph on $$m$$ edges always contains a bipartite graph of $$f(m)$$ edges. Determine $$f(m)$$.

Erdös and Lovász[2] proved that

$$\displaystyle f(m) \geq \frac 1 2 m + c m^{2/3} (\frac {\log m }{\log \log m})^{1/3}.$$

This was improved by Poljak and Tuza [3] to a lower bound of

$$\displaystyle f(m) \geq m/2 + c (m \log m)^{2/3}.$$

This was further improved by Shearer [4] to

$$\displaystyle f(m) \geq \frac 1 2 m + c m^{3/4}.$$

In 1996, Alon[1] proved that

$$\displaystyle \frac 1 2 m + c m^{4/5} \leq f(m) \leq \frac 1 2 m + c' m^{4/5}.$$

Bibliography
1 N. Alon. Bipartite subgraphs. Combinatorica 16 (1996), 301-311.

2 F. R. K. Chung, P. Erdös and R. L. Graham, 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, 597-602, New York Acad. Sci., New York, 1979.

3 S. Poljak and Z. Tuza. Bipartite subgraphs of triangle-free graphs. SIAM J. Discrete Math. 7 (1994), 307-313.

4 J. B. Shearer, A note on bipartite subgraphs of triangle-free graphs, Random Structures and Algorithms 3 (1992), 223-226.