Premium
On triangle‐free random graphs
Author(s) -
Łuczak Tomasz
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(200005)16:3<260::aid-rsa3>3.0.co;2-q
Subject(s) - combinatorics , random regular graph , struct , mathematics , random graph , bipartite graph , graph , discrete mathematics , line graph , computer science , pathwidth , programming language
We show that for every k ≥1 and δ>0 there exists a constant c >0 such that, with probability tending to 1 as n →∞, a graph chosen uniformly at random among all triangle‐free graphs with n vertices and M ≥ cn 3/2 edges can be made bipartite by deleting ⌊δ M ⌋ edges. As an immediate consequence of this fact we infer that if M / n 3/2 →∞ but M / n 2 →0, then the probability that a random graph G ( n , M ) contains no triangles decreases as 2 −(1+ o (1)) M . We also discuss possible generalizations of the above results. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 260–276, 2000