Randomness friendly graphs

✍ Scribed by Alexander Sidorenko

• Book ID: 102656821
• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 500 KB
• Volume: 8
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199605)8:3<229::aid-rsa6>3.0.co;2-#

✦ Synopsis

We consider the two problems from extremal graph theory:

1. Given integer N, real pE(0, 1) and a graph G, what is the minimum number of 2. Given an integer N and a graph G, what is the minimum number of copies of G an copies of G a graph H with N vertices and p N 2 / 2 edges can contain? N-vertex graph H and its complement H can contain altogether?

In each of the problems, we say that G is "randomness friendly" if the number of its copies is nearly minimal when H is the random graph. We investigate how the two classes of graphs are related: the graphs which are "randomness friendly" in Problem 1 and those of Problem 2. In the latter problem, we discover new families of graphs which are "randomness friendly."