Dense induced bipartite subgraphs in triangle-free graphs (Q2003768): Difference between revisions

Let \(b(G)\) denote the size of the largest bipartite subgraph of a graph \(G\) with \(n\) vertices and \(e\) edges. The extremal aspect of the Max Cut problem asks for lower bounds on \(b(G)\) in terms of \(n\) and \(e\). A classical result of \textit{P. Erdős} [Isr. J. Math. 3, 113--116 (1965; Zbl 0134.43403)] states that \(b(G)\ge e/2\), and the complete graph on \(n\) vertices shows that the constant \(1/2\) in this bound is asymptotically tight. One class which has drawn most of the attention is \(H\)-free graphs, see \textit{P. Erdős} [Problems and results in graph theory and combinatorial analysis. (English), Proc. 5th Br. comb. Conf., Aberdeen 1975, 169--192 (1976; Zbl 0335.05002)]. There are only a few graphs \(H\) for which optimal lower bounds on \(b(G)-e/2\), as \(G\) ranges over all \(H\)-free graph on \(e\) edges. \par This paper is structured on six sections. In Section 1, some basic notations and results are presented, which are used in the rest of the paper. The induced bipartite subgraphs with many edges are presented in Section 2. Section 3 is devoted to prove the lower bounds for triangle-free graphs with minimum degree. In Section 4 the authors show the reduction from H-free graphs to triangle-free graphs. Section 5 is devoted to describe both probabilistic and explicit constructions of triangle-free graphs which have no high-degree bipartite induced subgraphs and in Section 6 there are presented the concluding remarks.