Randomness friendly graphs
Alexander Sidorenko · Random Structures and Algorithms · 1996
We consider the two problems from extremal graph theory: 1. Given integer N, real p ϵ (0, 1) and a graph G, what is the minimum number of copies of G a graph H with N vertices and pN2/2 edges can contain? 2. Given an integer N and a graph G, what is the minimum number of copies of G an 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.” © 1996 John Wiley & Sons, Inc.