✦ LIBER ✦

Random maximal H-free graphs

✍ Scribed by Deryk Osthus; Anusch Taraz

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 197 KB
Volume: 18
Category: Article
ISSN: 1042-9832
DOI: 10.1002/1098-2418(200101)18:1<61::aid-rsa5>3.0.co;2-t

No coin nor oath required. For personal study only.

✦ Synopsis

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 edge is born, it is included in the graph if this does not create a copy of H. The question is then how many edges such a graph will have when p = 1. Here we give asymptotically almost sure bounds on the number of edges if H is a strictly 2-balanced graph, which includes the case when H is a complete graph or a cycle. Furthermore, we prove the existence of graphs with girth greater than and chromatic number n 1/ -1 +o 1 , which improves on previous bounds for > 3.

📜 SIMILAR VOLUMES

On triangle-free random graphs

✍ Tomasz Łuczak 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 2 views

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 th

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

✍ 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

Bisecting sparse random graphs

✍ Malwina J. Luczak; Colin McDiarmid 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB

The Geometry of Convex Affine Maximal Gr

The Geometry of Convex Affine Maximal Graphs

✍ Jose Antonio Gálvez; Antonio Martínez; Francisco Milán 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB 👁 1 views

Hamilton cycles in random graphs and dir

Hamilton cycles in random graphs and directed graphs

✍ Colin Cooper; Alan Frieze 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB 👁 2 views