Bipartite subgraphs (Q2563506): Difference between revisions

\(f(G)\) denotes the maximum number of edges in a bipartite subgraph of any simple graph \(G\); \(f(e)\) dentoes the minimum of \(f(G)\) as \(G\) ranges over all graphs \(G\) having \(e\) edges. Erdös has conjectured that \(\limsup_{e\to\infty} \Biggl(f(e)-{e\over 2}+{-1+\sqrt{8e+1}\over 8}\Biggr)=\infty\). Theorem 1.1. There exist a positive constant \(c\) and an integer \(n_0\) such that, for \(e={n^2\over 2}\), where \(n\) is any sufficiently large integer, \(f(e)\geq{e\over 2}+\sqrt{{e\over 8}}+ce^{{1\over 4}}\). It is observed that this result is ``tight'', in the sense that there exists a positive constant \(C\) such that, for every \(e\), \(f(e)\leq{e\over 2}+\sqrt{{e\over 8}}+Ce^{{1\over 4}}\). Theorem 1.2. There exists a positive constant \(c'\) such that, for every triangle-free graph \(G\) with \(e>1\) edges, \(f(G)\geq{e\over 2}+c'e^{{4\over 5}}\). This latter result is shown to be ``tight'' in the sense that there exists a positive constant \(C'\) such that, for every positive integer \(e\), there exists a triangle-free graph \(G\) having \(e\) edges, such that \(f(G)\leq{e\over 2}+C'e^{{4\over 5}}\). In a note added in proof the author observes that J. Shearer has independently shown earlier that, for any \(\varepsilon>0\), any triangle-free graph with \(e\) edges and sufficiently many vertices contains a bipartite subgraph with at least \({e\over 2}+\Omega(e^{{4\over 5}-\varepsilon})\) edges. There are misprints.