𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On triangle-free random graphs

✍ Scribed by Tomasz Łuczak

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
167 KB
Volume
16
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

2-factors in triangle-free graphs
2-factors in triangle-free graphs
✍ Bauer, D.; van den Heuvel, J.; Schmeichel, E. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 440 KB 👁 2 views

We study the cycle structure of I-tough, triangle-free graphs. In particular, w e prove that every such graph on n 2 3 vertices with minimum degree 6 2 i ( n + 2) has a 2-factor. W e also show this is best possible by exhibiting an infinite class of I-tough, triangle-free graphs having 6 = $ ( n + 1

Random maximal H-free graphs
Random maximal H-free graphs
✍ Deryk Osthus; Anusch Taraz 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB 👁 1 views

Given a graph H, a random maximal H-free graph is constructed by the following random greedy process. First assign to each edge of the complete graph on n vertices a birthtime which is uniformly distributed in [0, 1]. At time p = 0 start with the empty graph and increase p gradually. Each time a new

On decomposition of triangle-free graphs
On decomposition of triangle-free graphs under degree constraints
✍ Kaneko, Atsushi 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 1 views

We prove that if s and t are positive integers and if G is a triangle-free graph with minimum degree s + t, then the vertex set of G has a decomposition into two sets which induce subgraphs of minimum degree at least s and t, respectively.

Random trees and random graphs
Random trees and random graphs
✍ Tomasz Łuczak 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 205 KB 👁 1 views

In the paper we study the asymptotic behavior of the number of trees with n Ž . Ž . vertices and diameter k s k n , where n y k rnª a as n ª ϱ for some constant a-1. We use this result to determine the limit distribution of the diameter of the random graph Ž .

Random interval graphs
Random interval graphs
✍ Nicholas Pippenger 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB

We consider models for random interval graphs that are based on stochastic service systems, with vertices corresponding to customers and edges corresponding to pairs of customers that are in the system simultaneously. The number N of vertices in a connected component thus corresponds to the number o