##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 842.05080

**Autor: ** Erdös, Paul; Janson, Svante; Luczak, Tomasz; Spencer, Joel

**Title: ** A note on triangle-free graphs. (In English)

**Source: ** Aldous, David (ed.) et al., Random discrete structures. Based on a workshop held November 15-19, 1993 at IMA, University of Minnesota, Minneapolis, MN, USA. Berlin: Springer-Verlag, IMA Vol. Math. Appl. 76, 117-119 (1996).

**Review: ** If G is a triangle-free graph with many edges, then it exhibits bipartite-like behavior. Let B(G) be the maximum number of edges over all induced bipartite subgraphs of G; let f(n, e) be the minimum of B(G) where G ranges over all n-vertex, e-edge triangle-free graphs, and let g(e) = **max**_{n} f(n, e). Then for some constants c_{1} and c_{2}, c_{1} e^{1/3} \leq g(e) \leq c_{2} e^{1/3} ln^{2} e; these bounds also apply to f(n, e) if e < c_{5} n^{3/2} for some fixed c_{5}. On the other hand, there exist c_{4}, c_{5} such that if e \geq c_{5} n^{3/2}, then

c_{3} e^{3} n^{- 4} \leq f(n, e) \leq c_{4} e^{4} n^{- 4} ln^{2} n. These results were obtained by probabilistic and combinatorial techniques. The authors expressed a desire to eliminate the polylogarithmic factor between the bounds.

**Reviewer: ** G.L.McColm (Tampa)

**Classif.: ** * 05C80 Random graphs

**Keywords: ** random grphs; triangle-free graph; bipartite subgraphs

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag