Premium
Randomness friendly graphs
Author(s) -
Sidorenko Alexander
Publication year - 1996
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199605)8:3<229::aid-rsa6>3.0.co;2-#
Subject(s) - randomness , mathematics , combinatorics , discrete mathematics , computer science , statistics
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 pN 2 /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.