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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page