✦ LIBER ✦

The perturbation method and triangle-free random graphs

✍ Scribed by Nicholas C. Wormald

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 742 KB
Volume: 9
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199608/09)9:1/2<253::aid-rsa15>3.0.co;2-o

No coin nor oath required. For personal study only.

✦ Synopsis

When a discrete random variable in a discrete space is asymptotically Poisson, there is often a powerful method of estimating its distribution, by calculating the ratio of the probabilities of adjacent values of the variable. The versatility of this method is demonstrated by finding asymptotically the probability that a random graph has no triangles, provided the edge density is not too large. In particular, the probability that G E %(n, p ) has no triangles is asymptotic to exp(-+ p 3 n 3 + + p 5 n 4 -I , 2 p 7 n 5 ) for p =

~( n -" ~) ,

and for G E %(n, rn) it is asymptotic to exp(-id3n3) for d = A = ~( n -" ~) .

📜 SIMILAR VOLUMES

On triangle-free random graphs

✍ Tomasz Łuczak 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 3 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

2-factors in triangle-free graphs

✍ Bauer, D.; van den Heuvel, J.; Schmeichel, E. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 440 KB 👁 3 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

Rooted induced trees in triangle-free gr

Rooted induced trees in triangle-free graphs

✍ Florian Pfender 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 68 KB

## Abstract For a graph __G__, let __t__(__G__) denote the maximum number of vertices in an induced subgraph of __G__that is a tree. Further, for a vertex __v__∈__V__(__G__), let __t__(__G, v__) denote the maximum number of vertices in an induced subgraph of __G__that is a tree, with the extra cond

A note on maximal triangle-free graphs

✍ Wayne Goddard; Daniel J. Kleitman 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 1 views

## Abstract We show that a maximal triangle‐free graph on __n__ vertices with minimum degree δ contains an independent set of 3δ − __n__ vertices which have identical neighborhoods. This yields a simple proof that if the binding number of a graph is at least 3/2 then it has a triangle. This was con

On minimal 5-chromatic triangle-free gra

On minimal 5-chromatic triangle-free graphs

✍ David Avis 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB 👁 1 views

## Abstract It is shown that the minimum number of vertices in a triangle‐free 5‐chromatic graph is at least 19.

On the asymptotic structure of sparse tr

On the asymptotic structure of sparse triangle free graphs

✍ Pr�mel, Hans J�rgen; Steger, Angelika 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 567 KB

An important result of Erdos, Kleitman, and Rothschild says that almost every triangle-free graph on n vertices has chromatic number 2. In this paper w e study the asymptotic structure of graphs in y0rb,,,(K3), i.e., in the class of trianglefree graphs on n vertices having rn = rn(n) edges. In parti