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) = maxn f(n, e). Then for some constants c1 and c2, c1 e1/3 \leq g(e) \leq c2 e1/3 ln2 e; these bounds also apply to f(n, e) if e < c5 n3/2 for some fixed c5. On the other hand, there exist c4, c5 such that if e \geq c5 n3/2, then
c3 e3 n- 4 \leq f(n, e) \leq c4 e4 n- 4 ln2 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