amsppt
C
by
Bull
London
Math
Soc
Bull
Amer
Math
Soc
Combinatorics
Probability
and
Computing
J
Amer
Math
Soc
J
London
Math
Soc
Proc
London
Math
Soc
J
Combinatorial
Theory
J
Combinatorial
Theory
Series
A
J
Combinatorial
Theory
Series
B
J
Graph
Theory
Combinatorica
Acta
Math
Acad
Sci
Hungar
Studia
Sci
Math
Hung
Europ
J
Combinatorics
Graphs
and
Combinatorics
Israel
J
Math
Discrete
Math
Ann
Discrete
Math
Trans
Amer
Math
Soc
Proc
Amer
Math
Soc
Periodica
Math
Hungar
Proc
Cambridge
Phil
Soc
Math
Proc
Cambridge
Phil
Soc
Random
Structures
and
Algorithms
Ajtai
M
Alon
N
Beck
J
Bollob
as
B
Chung
F
R
K
Erd
os
P
Frankl
P
F
uredi
Z
Graham
R
L
Katona
G
O
H
Kleitman
D
J
Koml
os
J
Lov
asz
L
Ne
set
ril
J
P
osa
L
R
odl
V
Seymour
P
Shearer
J
B
Simonovits
M
S
os
V
T
Spencer
J
H
Szemer
edi
E
Tur
an
P
Tutte
W
T
Tuza
Zs
by
e
by
eqno
by
eqno
Claim
em
pt
Assertion
Case
Case
em
pt
TeXbook
p
Proof
of
the
Claim
ind
J
P
Z
G
F
B
U
E
a
b
d
f
g
f
g
G
W
k
p
d
Y
d
G
p
d
H
p
d
J
p
d
F
p
d
H
r
p
d
H
r
d
G
p
x
G
p
Bi
ex
S
V
U
Z
m
H
F
H
V
V
m
A
S
H
S
d
Ave
Forb
G
p
E
On
free
subgraphs
of
random
graphs
FREE
SUBGRAPHS
OF
RANDOM
GRAPHS
Y
Kohayakawa
T
uczak
and
V
R
odl
Instituto
de
Matem
atica
e
Estat
stica
Universidade
de
S
ao
Paulo
Rua
do
Mat
ao
S
ao
Paulo
SP
Brazil
yoshi
usp
br
Department
of
Discrete
Mathematics
Adam
Mickiewicz
University
ul
Matejki
Pozna
n
Poland
tomasz
amu
edu
pl
tomasz
emory
edu
Department
of
Mathematics
and
Computer
Science
Emory
University
Atlanta
Georgia
USA
rodl
emory
edu
Tur
an
s
extremal
problem
forbidden
subgraphs
extremal
subgraphs
cliques
random
graphs
Primary
C
C
Secondary
D
The
first
author
was
partially
supported
by
FAPESP
Proc
and
by
CNPq
Proc
and
ProTeM
CC
II
Project
ProComb
Part
of
this
work
was
done
while
the
second
author
was
visiting
the
University
of
S
ao
Paulo
supported
by
FAPESP
Proc
The
third
author
was
partially
supported
by
the
NSF
grant
DMS
For
and
graphs
and
write
if
any
proportion
of
the
edges
of
span
at
least
one
copy
of
in
As
customary
write
for
the
complete
graph
on
vertices
We
show
that
for
every
fixed
real
there
exists
a
constant
such
that
almost
every
random
graph
with
satisfies
The
proof
makes
use
of
a
variant
of
Szemer
edi
s
regularity
lemma
for
sparse
graphs
and
is
based
on
a
certain
superexponential
estimate
for
the
number
of
pseudo
random
tripartite
graphs
whose
triangles
are
not
too
well
distributed
Related
results
and
a
general
conjecture
concerning
free
subgraphs
of
random
graphs
in
the
spirit
of
the
Erd
os
Stone
Simonovits
theorem
are
discussed
Introduction
A
classical
area
of
extremal
graph
theory
investigates
numerical
and
structural
problems
concerning
free
graphs
namely
graphs
that
do
not
contain
a
copy
of
a
given
fixed
graph
as
a
subgraph
Let
be
the
maximal
number
of
edges
that
an
free
graph
on
vertices
may
have
A
basic
question
is
then
to
determine
or
estimate
for
any
given
and
large
A
solution
to
this
problem
is
given
by
the
celebrated
Erd
os
Stone
Simonovits
theorem
which
states
that
as
we
have
where
as
usual
is
the
chromatic
number
of
Furthermore
as
proved
independently
by
Erd
os
and
Simonovits
every
free
graph
that
has
as
many
edges
as
in
is
in
fact
very
close
in
a
certain
precise
sense
to
the
densest
vertex
partite
graph
For
these
and
related
results
see
for
instance
Bollob
as
Here
we
are
interested
in
a
variant
of
the
function
Let
and
be
graphs
and
write
for
the
maximal
number
of
edges
that
an
free
subgraph
of
may
have
Formally
where
stands
for
the
size
of
Clearly
As
an
example
of
a
problem
involving
with
let
us
recall
that
a
well
known
conjecture
of
Erd
os
states
that
where
stands
for
the
dimensional
hypercube
and
is
the
cycle
For
several
results
concerning
this
conjecture
see
Chung
Our
aim
here
is
to
study
when
is
a
typical
graph
by
which
we
mean
a
random
graph
Let
and
be
given
The
standard
binomial
random
graph
has
as
vertex
set
a
fixed
set
of
cardinality
and
two
such
vertices
are
adjacent
in
with
probability
with
all
such
adjacencies
independent
The
random
graph
is
simply
a
graph
on
a
fixed
element
vertex
set
chosen
uniformly
at
random
from
all
the
possible
candidates
For
concepts
and
results
concerning
random
graphs
not
given
in
detail
below
see
e
g
Bollob
as
Here
we
wish
to
investigate
the
random
variables
and
Let
be
a
graph
of
order
Let
us
write
for
the
density
of
that
is
Given
a
real
and
an
integer
let
us
say
that
a
graph
is
quasi
partite
if
may
be
made
partite
by
the
deletion
of
at
most
of
its
edges
A
general
conjecture
concerning
is
as
follows
For
simplicity
below
we
restrict
our
attention
to
the
binomial
random
graph
Much
of
what
follows
may
be
restated
in
terms
of
As
is
usual
in
the
theory
of
random
graphs
we
say
that
a
property
holds
almost
surely
or
that
almost
every
random
graph
or
satisfies
if
holds
with
probability
tending
to
as
Conjecture
Let
be
a
non
empty
graph
of
order
at
least
and
let
be
such
that
as
Then
the
following
assertions
hold
i
Almost
every
satisfies
ii
Suppose
Then
for
any
there
is
a
such
that
almost
every
has
the
property
that
any
free
subgraph
of
with
is
quasi
partite
Recall
that
any
graph
contains
an
partite
subgraph
with
Thus
the
content
of
Conjecture
i
is
that
is
at
most
as
large
as
the
right
hand
side
of
or
in
other
words
that
holds
almost
surely
for
any
fixed
There
are
a
few
results
in
support
of
Conjecture
i
Any
result
concerning
the
tree
universality
of
expanding
graphs
or
else
a
simple
application
of
Szemer
edi
s
regularity
lemma
for
sparse
graphs
see
Lemma
below
give
Conjecture
i
for
forests
The
cases
in
which
and
are
essentially
proved
in
Frankl
and
R
odl
and
F
uredi
respectively
in
connection
with
problems
concerning
the
existence
of
some
graphs
with
certain
extremal
properties
The
case
in
which
is
a
general
cycle
was
settled
by
Haxell
Kohayakawa
and
uczak
see
also
Kohayakawa
Kreuter
and
Steger
Conjecture
ii
in
the
case
in
which
is
a
constant
follows
easily
from
Szemer
edi
s
regularity
lemma
A
variant
of
this
lemma
for
sparse
graphs
cf
Lemma
below
and
a
lemma
from
Kohayakawa
uczak
and
R
odl
concerning
induced
subgraphs
of
bipartite
graphs
may
be
used
to
verify
Conjecture
for
in
full
See
comments
following
Conjecture
for
further
details
Still
in
the
case
in
which
for
sufficiently
close
to
a
much
stronger
result
than
Conjecture
ii
was
proved
by
Babai
Simonovits
and
Spencer
Finally
let
us
note
that
a
result
concerning
Ramsey
properties
of
random
graphs
in
the
spirit
of
Conjecture
was
proved
by
R
odl
and
Ruci
nski
Here
we
prove
Conjecture
i
for
Our
results
are
as
follows
Theorem
For
any
constant
there
is
a
constant
for
which
the
following
holds
If
is
such
that
for
all
large
enough
then
almost
every
is
such
that
Corollary
For
any
constant
there
is
a
constant
for
which
the
following
holds
If
is
such
that
for
all
large
enough
then
almost
every
is
such
that
In
below
we
formulate
an
auxiliary
conjecture
Conjecture
that
if
proved
would
imply
Conjecture
in
full
for
all
graphs
Finally
let
us
mention
that
Conjecture
if
true
would
immediately
imply
the
existence
of
very
sparse
graphs
satisfying
the
property
that
for
any
A
simple
corollary
of
Theorem
is
that
for
any
there
is
a
graph
that
contains
no
but
we
have
see
Erd
os
and
Ne
set
ril
have
asked
whether
such
graphs
exist
This
note
is
organised
as
follows
In
Section
we
give
a
short
outline
of
the
proof
of
our
main
result
Theorem
and
in
Section
some
preliminary
results
are
given
In
the
distribution
of
triangles
in
random
and
pseudo
random
graphs
is
studied
In
we
prove
a
key
lemma
in
the
proof
of
our
main
result
Lemma
Theorem
is
proved
in
In
we
discuss
a
deterministic
corollary
to
Theorem
concerning
the
Erd
os
Ne
set
ril
problem
Our
last
paragraph
contains
Conjecture
Outline
of
Proof
and
Preliminaries
Outline
of
the
proof
of
Theorem
The
proof
of
our
main
result
is
somewhat
long
and
hence
for
convenience
in
this
section
we
describe
its
main
steps
Here
we
try
to
avoid
being
too
technical
The
proof
of
Theorem
naturally
splits
into
two
parts
Suppose
where
is
some
large
constant
and
let
be
a
spanning
subgraph
of
with
relative
density
Let
us
say
that
two
vertices
are
connected
by
if
there
are
two
other
vertices
such
that
both
and
induce
triangles
in
Sometimes
we
also
say
that
such
a
pair
is
a
pivotal
pair
In
the
first
part
of
our
proof
we
show
that
the
number
of
pairs
of
vertices
that
are
connected
by
is
roughly
at
least
as
long
as
is
a
large
enough
constant
The
precise
statement
of
this
result
is
given
in
Section
Lemma
The
second
part
of
the
proof
consists
of
deducing
our
Theorem
from
Lemma
This
part
is
less
technical
than
the
first
and
is
also
considerably
shorter
The
method
used
here
was
inspired
by
an
argument
in
R
odl
and
Ruci
nski
and
a
version
of
this
technique
was
used
in
Haxell
Kohayakawa
and
uczak
Let
us
give
a
brief
description
of
this
method
Thus
let
be
the
binomial
random
graph
with
where
is
some
large
constant
and
let
a
constant
be
fixed
For
simplicity
let
us
also
assume
that
as
We
may
write
as
the
union
of
independent
random
graphs
where
is
some
large
constant
to
be
carefully
chosen
later
Since
below
we
may
ignore
the
edges
of
that
belong
to
more
than
one
of
the
Let
us
now
ask
an
adversary
to
choose
a
subgraph
of
of
size
at
least
where
or
equivalently
let
us
ask
our
adversary
to
choose
a
set
of
edges
with
Our
aim
is
to
show
that
such
a
set
must
span
a
Instead
of
asking
our
adversary
to
pick
directly
we
ask
him
to
pick
for
all
For
some
we
must
have
We
may
in
fact
ask
our
adversary
to
pick
first
and
and
leave
the
choice
of
for
later
By
Lemma
we
know
that
at
least
edges
of
join
pairs
of
vertices
that
are
connected
by
We
now
show
to
our
adversary
and
ask
him
to
pick
Note
that
with
very
high
probability
at
least
of
the
edges
of
will
be
formed
by
connected
pairs
and
if
our
adversary
puts
any
of
these
edges
into
then
will
span
a
copy
of
However
since
contains
an
extremely
large
proportion
of
the
edges
of
we
choose
very
large
our
adversary
is
forced
to
pick
at
least
of
the
edges
of
and
hence
he
is
forced
to
close
a
by
picking
a
connected
pair
for
an
edge
of
Let
us
close
this
section
with
a
few
words
on
the
proof
of
Lemma
Recall
that
in
that
lemma
we
are
concerned
with
estimating
the
number
of
connected
pairs
induced
by
subgraphs
of
random
graphs
A
very
simple
lower
bound
for
the
number
of
such
pairs
induced
by
an
arbitrary
graph
is
given
in
assertion
in
Section
This
estimate
is
far
too
weak
to
be
of
any
use
when
dealing
with
subgraphs
of
random
graphs
but
a
weighted
version
of
this
estimate
Lemma
is
important
in
the
proof
of
Lemma
Another
important
and
a
much
deeper
ingredient
in
the
proof
of
Lemma
is
a
version
of
Szemer
edi
s
regularity
lemma
for
sparse
graphs
see
Lemma
in
Section
below
A
simple
application
of
Lemmas
and
allows
us
to
focus
our
attention
on
certain
regular
quadruples
The
key
lemma
concerning
such
quadruples
is
Lemma
in
Section
The
proof
of
Lemma
is
based
on
certain
results
concerning
the
number
and
the
distribution
of
triangles
in
random
and
pseudo
random
graphs
Paragraph
is
entirely
devoted
to
those
results
The
main
lemmas
in
are
Lemmas
and
Preliminaries
Let
a
graph
of
order
be
fixed
For
with
we
write
for
the
set
of
edges
of
that
have
one
endvertex
in
and
the
other
in
We
set
The
following
notion
will
be
needed
in
what
follows
Suppose
and
We
say
that
is
upper
uniform
with
density
if
for
all
with
and
we
have
Clearly
if
is
upper
uniform
with
density
then
it
is
also
upper
uniform
with
density
for
any
and
any
In
the
sequel
for
any
two
disjoint
non
empty
sets
let
be
the
relative
density
or
for
short
the
density
of
between
and
Now
suppose
and
We
say
that
the
pair
is
regular
if
for
all
with
and
we
have
We
say
that
a
partition
of
is
equitable
if
and
Also
we
say
that
is
the
exceptional
class
of
When
the
value
of
is
not
relevant
we
refer
to
an
equitable
partition
as
a
equitable
partition
Similarly
is
an
equitable
partition
of
if
it
is
a
equitable
partition
for
some
Finally
we
say
that
an
equitable
partition
of
is
regular
if
at
most
pairs
with
are
not
regular
We
may
now
state
an
extension
of
Szemer
edi
s
lemma
to
subgraphs
of
upper
uniform
graphs
Lemma
For
any
given
and
there
are
constants
and
that
depend
only
on
and
such
that
any
upper
uniform
graph
with
density
admits
an
regular
equitable
partition
of
its
vertex
set
with
Using
standard
estimates
for
tails
of
the
binomial
distribution
it
is
easy
to
check
that
a
e
is
upper
uniform
with
density
for
any
constant
if
is
larger
than
some
constant
Let
us
introduce
a
piece
of
notation
before
we
proceed
If
are
pairwise
disjoint
sets
of
vertices
of
a
given
graph
we
write
for
the
partite
subgraph
of
naturally
defined
by
the
Thus
has
vertex
set
and
two
of
its
vertices
are
adjacent
if
and
only
if
they
are
adjacent
in
and
moreover
they
belong
to
distinct
Now
suppose
we
have
real
numbers
and
an
integer
Suppose
the
above
all
have
cardinality
and
write
for
the
density
for
all
distinct
and
Suppose
is
a
graph
on
such
that
for
any
the
pair
is
regular
and
whenever
We
may
now
state
our
next
lemma
In
what
follows
we
write
for
any
term
satisfying
Also
as
usual
we
write
for
the
maximal
degree
of
and
we
write
for
the
neighbourhood
of
a
vertex
Lemma
Let
and
the
sets
be
as
above
and
let
Suppose
and
put
and
Then
there
are
sets
with
for
all
such
that
for
all
and
any
we
have
for
any
with
Lemma
above
is
very
similar
to
Lemma
in
and
hence
its
rather
elementary
proof
is
omitted
We
close
this
section
with
a
very
simple
large
deviation
inequality
for
the
hypergeometric
distribution
This
inequality
will
be
used
in
Section
below
Lemma
Let
and
be
integers
and
suppose
is
an
element
subset
of
chosen
uniformly
at
random
Then
Triangles
in
Pseudo
Random
and
Random
Graphs
The
counting
lemma
Let
be
an
integer
In
this
section
we
shall
consider
a
fixed
triple
of
pairwise
disjoint
sets
with
for
all
We
shall
also
suppose
that
satisfies
for
all
large
enough
and
moreover
that
as
In
this
section
all
the
asymptotic
notation
refers
to
Our
aim
is
to
estimate
from
above
the
number
of
certain
pseudo
random
tripartite
graphs
with
tripartition
that
contain
unexpectedly
few
triangles
given
the
number
of
edges
that
they
have
or
else
whose
triangles
are
not
too
regularly
distributed
Before
we
may
describe
precisely
which
graphs
are
of
interest
to
us
we
need
to
introduce
a
few
definitions
In
what
follows
indices
will
be
tacitly
taken
modulo
when
convenient
Let
be
given
Suppose
and
let
be
the
number
of
triangles
of
that
contain
We
shall
say
that
is
poor
if
The
graph
is
unbalanced
if
for
some
the
number
of
poor
edges
in
is
at
least
For
simplicity
below
we
write
and
if
and
we
let
Now
suppose
integers
and
and
real
constants
and
are
given
and
let
and
be
as
above
Let
us
write
for
the
set
of
tripartite
graphs
with
tripartition
that
satisfy
the
following
properties
i
is
an
regular
triple
ii
for
all
iii
for
all
and
any
choice
of
and
such
that
iv
has
size
Moreover
for
any
given
let
be
the
set
of
unbalanced
graphs
in
Put
Sometimes
the
labelling
of
the
vertices
of
the
graphs
in
or
in
is
not
relevant
and
in
that
case
we
may
replace
by
in
our
notation
Our
crucial
counting
lemma
is
as
follows
Lemma
Let
and
be
given
Then
there
is
a
constant
that
depends
only
on
and
for
which
the
following
holds
Suppose
is
such
that
for
all
large
enough
and
moreover
as
Then
if
and
is
sufficiently
large
we
have
for
all
and
all
with
Most
of
the
rest
of
Section
is
dedicated
to
the
proof
of
Lemma
above
Our
general
strategy
in
this
proof
is
as
follows
We
randomly
generate
a
tripartite
graph
with
tripartition
and
size
and
show
that
the
probability
that
the
graph
we
obtain
will
be
a
member
of
is
suitably
small
We
generate
in
steps
we
first
generate
We
then
generate
and
analyse
the
structure
of
the
graph
We
then
finally
generate
and
show
that
the
appropriate
probability
is
indeed
small
Let
us
now
make
precise
the
process
by
which
we
generate
We
first
of
all
fix
a
partition
of
such
that
putting
we
have
for
all
Note
that
because
of
condition
ii
above
for
we
may
disregard
the
for
which
such
a
partition
does
not
exist
Let
us
suppose
that
the
bipartite
graph
has
been
fixed
and
that
the
following
properties
hold
cf
i
iv
above
a
the
pair
is
regular
b
for
all
where
and
c
We
now
fix
the
degree
sequence
for
the
vertices
in
the
bipartite
graph
and
generate
this
graph
respecting
this
sequence
Thus
let
with
and
for
all
be
fixed
and
generate
the
bipartite
graph
by
selecting
the
neighbourhoods
randomly
and
independently
for
all
Thus
for
every
all
the
element
subsets
of
are
equally
likely
to
be
chosen
as
the
neighbourhood
of
within
We
now
analyse
the
structure
of
For
convenience
let
us
put
for
all
and
with
and
Put
also
and
Thus
for
all
and
for
all
Let
be
given
For
all
put
where
Note
that
the
set
is
defined
in
such
a
way
that
the
following
fact
holds
if
is
an
edge
of
then
is
a
poor
edge
if
and
only
if
Now
let
be
given
Below
we
say
that
is
faulty
if
Note
that
clearly
since
we
are
conditioning
on
the
event
that
a
vertex
should
be
faulty
depends
only
on
the
random
set
that
is
chosen
as
the
neighbourhood
of
within
Our
next
lemma
is
the
key
technical
result
in
the
proof
of
the
main
lemma
in
this
section
Lemma
Lemma
Suppose
the
constants
and
are
such
and
Then
for
all
sufficiently
large
the
probability
that
a
given
vertex
is
faulty
is
at
most
Proof
Let
us
fix
and
assume
that
Let
be
such
that
The
following
assertion
whose
proof
we
omit
is
very
similar
to
Lemma
There
exist
sets
and
for
which
we
have
and
and
furthermore
for
all
and
for
all
Using
Assertion
we
prove
next
that
there
exists
a
small
set
of
vertices
from
whose
neighbourhood
uniformly
cover
essentially
all
of
We
need
to
introduce
some
notation
Let
us
set
and
let
for
all
and
all
Put
also
for
all
There
is
a
set
of
cardinality
such
that
and
such
that
for
all
Let
and
be
as
in
Assertion
To
prove
Assertion
we
construct
by
randomly
selecting
its
elements
from
the
set
Let
Note
that
for
all
large
enough
Put
the
vertices
of
into
randomly
each
with
probability
and
with
all
these
events
independent
The
expected
cardinality
of
is
then
and
the
expected
degree
of
a
vertex
into
is
From
standard
bounds
for
the
tail
of
the
binomial
distribution
we
may
deduce
that
there
is
a
set
such
that
is
as
required
in
Assertion
and
such
that
every
satisfies
Note
that
for
such
a
set
we
have
and
hence
It
now
suffices
to
notice
that
every
is
such
that
since
and
relation
in
Assertion
holds
This
completes
the
proof
of
Assertion
The
probability
that
our
fixed
vertex
admits
a
set
as
in
Assertion
is
at
most
Let
us
first
sketch
the
idea
in
the
proof
of
Assertion
Roughly
speaking
the
set
is
such
that
the
neighbourhoods
of
the
vertices
within
are
about
of
the
same
size
and
the
vertices
in
are
by
definition
covered
by
those
sets
quite
uniformly
Now
since
the
vertices
in
are
all
in
we
have
that
the
neighbourhood
of
within
intersects
all
the
neighbourhoods
too
little
Thus
it
intersects
the
sets
too
little
as
well
and
this
is
possible
only
if
it
in
fact
intersects
in
an
unexpectedly
small
set
It
then
suffices
to
estimate
the
probability
that
should
be
as
small
Let
us
now
formalise
the
argument
above
Assume
that
a
set
as
in
Assertion
exists
We
consider
the
vectors
and
with
entries
and
We
first
estimate
for
For
any
fixed
we
have
We
have
and
since
we
have
Therefore
for
large
enough
and
similarly
if
is
sufficiently
large
Given
two
vectors
and
let
We
now
estimate
We
have
Therefore
We
have
from
our
assumptions
on
our
constants
that
Hence
with
plenty
to
spare
Thus
We
now
give
a
lower
estimate
for
the
left
hand
side
of
in
terms
of
the
Let
and
recall
that
we
let
for
all
Put
and
for
all
Fix
Clearly
Thus
Write
Recalling
we
see
that
where
we
used
that
trivially
and
that
and
are
all
since
by
assumption
as
However
which
is
Therefore
Using
that
and
that
we
deduce
from
inequality
above
that
We
now
claim
that
Indeed
otherwise
we
would
have
that
and
hence
comparing
inequalities
and
we
would
have
that
and
consequently
that
which
is
a
contradiction
Recall
that
and
that
Also
Thus
we
deduce
from
the
existence
of
the
set
that
at
least
elements
of
are
confined
to
a
subset
of
of
cardinality
at
most
Thus
by
Lemma
the
probability
that
such
a
set
exists
is
at
most
completing
the
proof
of
Assertion
We
may
now
finish
the
proof
of
Lemma
combining
Assertions
and
above
Indeed
writing
for
the
sum
over
all
satisfying
we
have
from
the
above
two
assertions
that
probability
that
the
vertex
should
be
faulty
is
for
large
enough
at
most
where
in
the
last
inequality
we
used
that
which
follows
easily
from
our
assumption
that
for
all
sufficiently
large
Thus
Lemma
is
proved
We
are
now
in
position
to
finish
the
proof
of
Lemma
Proof
of
Lemma
Let
us
first
state
a
simple
fact
concerning
the
For
all
we
have
Indeed
and
therefore
for
any
we
have
as
required
Our
next
observation
is
an
immediate
consequence
of
Lemma
and
Assertion
Let
be
given
The
probability
that
at
least
vertices
in
are
faulty
is
at
most
Indeed
by
Lemma
and
Assertion
above
the
probability
in
question
is
at
most
completing
the
proof
of
Assertion
We
now
describe
the
last
step
in
the
generation
of
Recall
that
we
have
generated
so
far
Let
be
the
complete
bipartite
graph
with
bipartition
To
generate
we
randomly
pick
for
a
element
subset
of
uniformly
chosen
from
all
such
sets
Suppose
that
fewer
than
vertices
in
are
faulty
Then
the
probability
that
at
least
edges
in
are
poor
is
no
larger
than
Recall
that
an
edge
is
poor
if
and
only
if
The
probability
in
question
is
the
probability
that
at
least
edges
with
are
selected
to
be
elements
of
The
number
of
such
potentially
poor
edges
in
is
at
most
and
hence
by
Lemma
and
Assertion
we
have
proving
Assertion
We
may
now
finish
the
proof
of
Lemma
Let
the
constants
and
as
in
the
statement
of
our
lemma
be
given
We
then
let
be
such
that
and
moreover
and
for
all
We
now
apply
Assertions
and
above
with
suitably
chosen
and
Let
and
fix
any
Let
and
Recall
that
To
complete
the
proof
we
proceed
as
follows
we
suppose
that
is
given
and
that
is
sufficiently
large
for
the
inequalities
below
to
hold
Fix
the
partition
of
the
bipartite
graph
and
the
degree
sequence
as
above
Then
generate
The
probability
that
at
least
vertices
in
are
faulty
is
by
Assertion
at
most
Let
us
now
assume
that
fewer
than
vertices
in
are
faulty
and
let
us
generate
Then
the
probability
that
edges
in
are
poor
is
by
Assertion
at
most
We
now
note
that
the
argument
above
is
symmetric
with
respect
to
the
indices
note
the
factor
below
and
thus
we
may
conclude
that
completing
the
proof
of
Lemma
Recall
that
and
are
integers
and
are
fixed
reals
is
such
that
and
as
and
and
where
the
are
pairwise
disjoint
sets
with
cardinality
Our
next
lemma
concerns
a
property
of
graphs
namely
graphs
in
that
are
balanced
For
a
vertex
let
denote
the
number
of
triangles
of
that
contain
Lemma
Suppose
is
a
balanced
graph
in
Put
Then
for
any
there
are
at
most
vertices
in
such
that
Proof
By
symmetry
it
suffices
to
prove
the
statement
for
In
the
sequel
we
freely
use
the
notation
introduced
before
Lemma
Also
let
us
put
for
all
and
with
Below
we
say
that
a
vertex
is
bad
if
at
least
edges
in
incident
to
are
poor
edges
The
number
of
such
bad
vertices
is
at
most
as
otherwise
the
number
of
poor
edges
in
would
be
more
than
contradicting
the
fact
that
is
balanced
Note
that
an
edge
that
is
not
poor
contributes
with
at
least
triangles
to
Supposing
that
is
not
a
bad
vertex
summing
over
all
for
which
is
not
a
poor
edge
we
obtain
that
Since
as
we
saw
above
at
most
vertices
are
bad
the
proof
is
complete
Distribution
of
triangles
in
random
graphs
In
this
section
we
look
at
the
random
graph
and
study
the
distribution
of
the
triangles
it
contains
The
aim
will
be
to
prove
that
the
triangles
of
do
not
unduly
concentrate
on
any
fixed
set
of
edges
and
vertices
To
be
precise
let
be
any
given
vertex
of
and
let
be
a
set
of
edges
of
taken
from
the
subgraph
induced
by
the
neighbourhood
of
in
Also
let
be
a
subset
of
vertices
of
disjoint
from
where
we
write
for
the
set
of
vertices
of
that
are
incident
to
at
least
one
edge
from
Our
aim
is
to
find
an
upper
bound
for
the
number
of
triangles
of
that
are
determined
by
an
edge
from
and
a
vertex
in
Note
that
the
expected
value
of
this
number
is
We
shall
show
that
this
is
an
upper
bound
in
probability
up
to
for
any
fixed
as
long
as
and
are
reasonably
large
and
does
not
tend
to
too
fast
Lemma
Let
and
be
given
Then
there
is
a
constant
that
depends
only
on
and
for
which
the
following
holds
Suppose
where
Then
almost
every
is
such
that
if
and
for
some
then
as
long
as
and
Most
of
the
remainder
of
this
section
is
devoted
to
the
proof
of
Lemma
Unfortunately
our
proof
below
is
a
little
indirect
and
is
based
on
a
few
auxiliary
lemmas
moreover
this
proof
makes
use
of
a
technical
condition
that
should
not
be
too
large
The
obvious
direct
approaches
based
on
simple
large
deviation
inequalities
seem
to
fail
to
give
Lemma
To
see
why
this
might
be
expected
note
that
i
for
the
sets
and
of
interest
the
expected
value
of
is
of
order
only
while
the
number
of
sets
that
we
have
to
handle
is
and
ii
is
a
sum
of
positively
correlated
indicator
variables
and
the
most
common
large
deviation
inequalities
for
such
sums
do
not
seem
to
be
strong
enough
for
our
purposes
Let
us
turn
to
the
proof
of
Lemma
For
the
rest
of
this
section
we
assume
that
where
and
is
some
large
constant
The
main
result
for
with
larger
will
be
deduced
from
the
small
case
cf
Lemma
Let
be
the
path
of
length
and
the
vertex
graph
with
no
edges
We
write
for
the
graph
on
vertices
we
obtain
from
the
disjoint
union
of
and
by
adding
all
the
edges
between
and
A
little
piece
of
arithmetic
shows
that
almost
no
contains
a
copy
of
Thus
for
the
rest
of
this
section
we
may
and
shall
assume
that
our
is
free
We
may
clearly
assume
that
the
degree
of
any
vertex
of
is
and
also
that
any
vertex
of
is
contained
in
at
most
triangles
Furthermore
the
expected
number
of
common
neighbours
of
any
two
fixed
vertices
of
is
Thus
we
may
and
shall
condition
on
our
being
such
that
for
any
pair
of
distinct
vertices
Finally
we
may
assume
that
is
upper
uniform
Suppose
and
For
a
vertex
let
be
the
set
of
edges
of
that
the
neighbourhood
of
in
induces
in
Clearly
We
shall
say
that
a
vertex
is
bad
or
simply
bad
if
is
not
an
independent
set
of
edges
Lemma
Almost
every
is
such
that
for
any
and
any
at
most
vertices
are
bad
Proof
Fix
a
vertex
Let
us
generate
as
follows
we
first
choose
the
neighbourhood
of
in
and
once
this
set
is
fixed
we
decide
which
edges
within
should
be
in
Put
and
let
be
the
set
of
vertices
in
that
are
incident
to
at
least
one
edge
in
For
the
rest
of
the
proof
we
assume
that
the
edges
generated
so
far
are
fixed
Let
us
now
consider
a
vertex
and
let
us
decide
which
edges
between
and
should
be
in
our
Notice
that
whether
or
not
is
bad
depends
solely
on
these
edges
In
particular
the
events
is
bad
are
all
independent
Let
us
estimate
the
probability
that
a
given
vertex
turns
out
to
be
bad
We
first
observe
that
with
probability
we
have
and
In
the
sequel
we
assume
that
these
two
inequalities
hold
In
particular
the
number
of
copies
of
spanned
by
is
crudely
at
most
Thus
the
probability
that
is
bad
is
where
denotes
the
number
of
copies
of
in
Now
from
the
independence
of
the
events
is
bad
we
have
that
the
probability
that
at
least
such
vertices
are
bad
satisfies
Thus
if
we
have
with
plenty
to
spare
The
above
argument
proves
our
lemma
with
replaced
by
To
complete
the
proof
we
make
the
following
simple
observation
Suppose
is
fixed
and
Then
is
necessarily
bad
whenever
it
is
bad
Thus
an
bad
vertex
is
either
contained
in
or
else
it
is
bad
Since
we
may
assume
that
our
lemma
follows
Lemma
above
tells
us
that
for
any
and
any
we
have
for
most
Of
course
since
is
supposed
not
to
contain
we
have
for
any
vertex
For
each
vertex
let
and
let
be
the
cardinality
of
a
maximum
matching
in
Since
we
have
for
any
Moreover
for
any
that
is
not
bad
we
clearly
have
Let
us
now
fix
Put
and
similarly
Let
us
write
for
sum
over
all
that
are
bad
and
for
sum
over
all
that
are
not
bad
Then
Now
our
aim
is
to
bound
the
last
two
summands
in
For
any
two
distinct
vertices
and
let
be
the
number
of
edges
induced
by
the
set
in
Thus
and
Lemma
For
almost
every
we
have
for
any
pair
of
distinct
vertices
Proof
Let
be
the
maximum
cardinality
of
a
matching
in
We
claim
that
For
convenience
put
By
Lemma
in
Janson
for
any
we
have
We
now
check
that
follows
from
Suppose
Then
we
take
in
and
note
that
then
Suppose
now
that
Then
we
take
in
to
obtain
Thus
the
claimed
inequality
does
hold
In
particular
almost
surely
for
any
distinct
Our
lemma
now
follows
since
and
hence
By
Lemmas
and
above
an
almost
sure
upper
bound
for
the
last
summand
in
is
Our
aim
now
is
to
estimate
Fortunately
the
method
of
proof
of
Lemma
in
Janson
gives
the
following
result
immediately
Lemma
Suppose
Then
for
any
we
have
Proof
We
follow
an
argument
of
Janson
cf
the
proof
of
Lemma
in
Fix
and
let
Let
be
the
family
of
all
copies
of
with
middle
vertex
and
endvertices
coinciding
with
endvertices
of
edges
in
in
the
complete
graph
on
Thus
each
such
corresponds
to
a
triangle
determined
by
and
one
edge
from
Let
be
the
collection
of
all
tuples
of
pairwise
edge
disjoint
elements
from
Let
be
the
indicator
variable
of
the
event
that
a
fixed
should
be
present
in
Thus
We
have
where
Now
the
are
independent
and
therefore
Let
Note
that
then
by
Markov
s
inequality
we
have
Taking
we
have
Our
lemma
follows
by
setting
in
this
last
inequality
We
are
finally
ready
to
prove
Lemma
Proof
of
Lemma
Take
We
proceed
to
show
that
this
choice
for
will
do
Thus
let
and
as
in
the
statement
of
our
lemma
be
given
To
prove
it
suffices
to
put
together
and
Lemmas
and
Indeed
with
the
notation
as
above
by
Lemma
we
have
where
in
the
last
inequality
we
used
that
and
The
number
of
choices
for
the
triple
is
at
most
Indeed
it
suffices
to
notice
that
we
may
assume
that
and
hence
the
number
of
choices
for
is
at
most
Thus
almost
every
is
such
that
From
and
Lemmas
and
we
have
for
almost
every
which
is
at
most
as
required
In
our
next
lemma
we
give
a
set
of
conditions
that
ensures
that
concentrates
around
its
mean
Lemma
Suppose
as
Let
with
be
given
Then
almost
every
is
such
that
for
any
and
with
and
we
have
Proof
Let
be
fixed
Let
be
a
matching
in
the
complete
graph
and
set
Suppose
that
as
Let
be
such
that
Let
us
write
for
the
number
of
triangles
in
that
are
determined
by
an
edge
of
and
a
vertex
of
Note
that
has
binomial
distribution
with
parameters
and
Thus
with
probability
The
number
of
matchings
of
cardinality
is
no
larger
than
and
the
number
of
sets
as
above
is
no
larger
than
Hence
we
see
that
holds
a
s
for
any
matching
with
and
any
with
since
Thus
let
us
assume
that
our
does
have
this
property
Clearly
we
may
also
assume
that
We
claim
that
under
these
assumptions
our
necessarily
satisfies
with
replaced
by
for
all
and
as
in
the
statement
of
our
lemma
To
see
this
fix
and
as
in
the
lemma
We
shall
now
make
use
of
the
following
simple
fact
that
may
be
easily
deduced
from
Vizing
s
theorem
if
is
a
graph
of
maximum
degree
then
admits
a
proper
edge
colouring
with
at
most
colours
such
that
the
cardinality
of
any
two
colour
classes
differ
by
at
most
Note
that
and
hence
by
the
observation
above
we
may
write
where
the
are
matchings
satisfying
for
all
and
and
moreover
In
particular
for
all
Therefore
applies
with
and
since
our
claim
does
hold
Lemma
follows
by
letting
tend
to
Pivotal
Pairs
of
Vertices
A
weighted
Tur
an
type
result
Let
be
a
graph
and
an
integer
Let
us
write
for
the
graph
with
vertices
and
edges
and
let
us
say
that
its
two
vertices
of
degree
are
the
endvertices
of
Let
us
say
that
the
unordered
pair
of
distinct
vertices
of
is
a
connected
pair
if
there
is
a
copy
of
in
with
endvertices
and
Hence
if
is
a
connected
pair
of
non
adjacent
vertices
then
the
addition
of
to
creates
a
new
copy
of
in
Thus
we
shall
also
say
that
a
connected
pair
is
pivotal
or
simply
pivotal
For
technical
reasons
let
us
also
say
that
the
vertex
is
by
itself
a
connected
pair
if
lies
in
a
copy
of
in
The
following
is
an
asymptotic
version
of
Tur
an
s
theorem
for
Any
graph
with
vertices
and
edges
contains
at
least
connected
pairs
of
vertices
To
check
that
is
indeed
an
asymptotic
form
of
Turan
s
theorem
observe
that
if
is
the
density
of
then
the
lower
bound
in
for
the
number
of
connected
pairs
in
is
for
large
Note
that
is
bigger
than
for
Therefore
we
may
deduce
that
any
large
with
necessarily
contains
a
which
is
of
course
a
weak
form
of
Tur
an
s
theorem
Unfortunately
does
not
seem
to
imply
Tur
an
s
theorem
for
in
its
precise
form
In
the
sequel
we
shall
need
however
a
weighted
version
of
for
To
describe
this
version
we
need
some
technical
definitions
Also
to
simplify
the
notation
we
restrict
ourselves
to
the
case
The
general
case
does
not
present
any
further
difficulty
We
start
with
a
graph
of
order
and
assume
is
an
assignment
of
weights
to
the
edges
of
Suppose
is
an
ordering
of
the
vertices
of
For
any
two
not
necessarily
distinct
vertices
that
form
a
connected
pair
in
we
let
For
convenience
if
do
not
form
a
connected
pair
we
put
Let
and
Our
weighted
version
of
for
is
given
in
Lemma
below
We
remark
that
to
deduce
the
unweighted
case
for
from
this
lemma
it
suffices
to
take
and
for
all
edges
Lemma
Let
be
a
graph
of
order
and
edge
weights
with
for
all
where
Then
there
is
an
ordering
of
the
vertices
of
for
which
we
have
Proof
Our
proof
is
by
induction
on
Since
the
case
is
trivial
we
assume
that
and
that
our
lemma
holds
for
graphs
with
at
most
vertices
Note
that
if
then
is
trivially
true
as
in
this
case
Thus
we
may
assume
that
Since
for
all
we
have
that
has
more
than
edges
Therefore
there
are
three
vertices
and
inducing
a
triangle
in
For
let
us
write
for
the
degree
of
We
may
assume
that
Put
and
by
induction
let
be
an
ordering
of
the
vertices
of
such
that
For
simplicity
above
stands
for
the
restriction
of
to
Our
aim
now
is
to
estimate
from
below
For
set
if
and
set
otherwise
Now
observe
that
since
for
any
reals
and
we
have
Therefore
Hence
with
we
have
as
required
Pivotal
pairs
in
subgraphs
of
random
graphs
In
this
section
we
turn
to
the
study
of
connected
pairs
in
subgraphs
of
random
graphs
Recall
that
given
a
graph
and
two
distinct
vertices
we
say
that
the
unordered
pair
is
a
connected
pair
if
they
are
the
endvertices
of
a
copy
of
in
and
that
a
single
vertex
by
itself
forms
a
connected
pair
if
it
belongs
to
a
triangle
of
Our
main
aim
here
is
to
prove
Lemma
below
which
roughly
says
that
if
a
subgraph
of
is
such
that
for
some
fixed
and
is
not
too
small
then
the
number
of
connected
pairs
in
is
almost
surely
This
result
is
similar
in
spirit
to
assertion
in
Section
but
note
that
applied
to
above
gives
nothing
if
as
Lemma
below
remedies
this
situation
and
recovers
essentially
the
same
lower
bound
for
the
number
of
connected
pairs
In
the
sequel
for
any
given
graph
it
will
be
convenient
to
define
a
graph
on
by
letting
two
distinct
vertices
be
adjacent
in
if
and
only
if
they
form
a
connected
in
Lemma
Let
a
constant
be
given
Then
there
is
a
constant
that
depends
only
on
for
which
the
following
holds
If
and
then
almost
every
is
such
that
for
any
subgraph
of
we
have
where
Before
we
proceed
let
us
remark
that
we
shall
apply
Lemma
above
with
much
smaller
than
In
fact
we
shall
be
interested
in
the
case
in
which
is
a
little
greater
than
and
is
very
small
The
proof
of
Lemma
is
based
on
the
results
of
the
previous
three
sections
and
on
a
further
technical
lemma
Lemma
which
we
now
describe
The
context
in
which
Lemma
applies
is
as
follows
Suppose
and
are
constants
and
let
and
be
integers
Let
also
be
given
Let
and
be
pairwise
disjoint
sets
of
cardinality
and
Suppose
is
a
graph
with
a
tripartite
graph
with
tripartition
and
such
that
for
both
For
simplicity
put
and
let
for
Suppose
further
that
the
following
conditions
hold
i
We
have
and
for
all
ii
At
least
vertices
in
are
such
that
where
is
the
number
of
triangles
of
that
contain
iii
At
least
edges
in
are
such
that
where
denotes
the
number
of
triangles
in
determined
by
the
edge
and
some
vertex
in
iv
Let
For
any
and
with
and
we
have
v
For
all
with
and
with
we
have
We
may
now
state
a
key
technical
lemma
in
the
proof
of
Lemma
Lemma
Let
constants
and
be
given
Then
with
the
notation
above
if
and
then
the
number
of
connected
pairs
with
is
at
least
Proof
Let
us
put
and
note
that
then
Let
and
be
given
and
suppose
that
is
as
described
before
our
lemma
In
the
sequel
an
edge
will
be
said
to
be
poor
if
fails
For
let
us
write
for
the
number
of
poor
edges
induced
by
the
neighbourhood
of
in
Let
us
say
that
is
unusable
if
The
proof
is
now
split
into
a
few
claims
At
most
vertices
in
are
unusable
Suppose
the
contrary
Let
us
consider
the
number
of
pairs
with
a
vertex
in
and
a
poor
edge
in
such
that
there
is
a
triangle
of
containing
both
and
Since
we
are
assuming
that
more
than
vertices
are
unusable
we
have
We
now
use
condition
v
above
to
deduce
that
Comparing
and
we
obtain
that
contradicting
the
fact
that
Thus
Assertion
holds
We
now
observe
that
condition
ii
above
immediately
implies
the
following
For
at
least
vertices
in
we
have
where
Now
let
be
given
Let
be
the
set
of
edges
induced
by
the
neighbourhood
of
in
that
are
not
poor
Thus
Let
For
at
least
vertices
we
have
Let
be
such
that
and
suppose
that
We
now
use
iv
above
to
deduce
that
which
is
a
contradiction
since
Thus
any
with
is
such
that
and
hence
Assertion
follows
from
Assertion
From
Assertion
we
deduce
that
at
least
pairs
are
connected
with
respect
to
thereby
proving
Lemma
We
are
now
ready
to
prove
Lemma
Our
proof
will
make
use
of
several
of
our
previous
lemmas
Proof
of
Lemma
Let
be
given
We
now
define
the
many
constants
with
which
we
shall
apply
Lemmas
and
Let
and
Let
where
Note
that
is
as
given
in
Lemma
We
now
let
where
is
as
defined
in
Lemma
Put
and
For
later
reference
note
that
and
if
then
with
plenty
to
spare
we
have
and
Set
where
is
as
given
in
Lemma
Now
let
and
be
as
given
by
Lemma
We
may
assume
that
Put
and
let
Finally
let
where
is
as
given
by
Lemma
We
claim
that
this
choice
of
will
do
in
Lemma
and
proceed
to
prove
this
assertion
Let
where
Let
us
consider
the
following
conditions
for
a
is
upper
uniform
and
has
size
b
Suppose
Then
for
any
and
any
with
our
contains
no
copy
of
any
graph
as
a
subgraph
c
Inequality
in
Lemma
holds
for
all
and
as
in
the
statement
of
that
lemma
with
and
d
Relation
in
Lemma
holds
for
all
and
with
and
Conditions
a
d
hold
for
almost
every
Condition
a
clearly
holds
almost
surely
We
use
Lemma
to
prove
that
b
holds
almost
surely
as
well
Let
and
be
as
in
b
Note
that
the
number
of
choices
for
and
is
trivially
at
most
The
number
of
copies
of
a
fixed
graph
that
the
complete
graph
on
vertices
contains
is
clearly
at
most
Thus
since
see
and
Lemma
applies
to
give
that
the
expected
number
of
copies
of
elements
from
that
contains
is
for
sufficiently
large
at
most
which
since
is
at
most
Summing
over
all
we
obtain
that
b
holds
almost
always
Condition
c
holds
almost
surely
for
by
Lemma
and
the
choice
of
To
check
that
d
holds
for
a
e
by
Lemma
it
suffices
to
see
that
and
that
as
This
completes
the
proof
of
our
claim
In
the
remainder
of
the
proof
we
show
that
holds
for
any
subgraph
whenever
satisfies
conditions
a
d
above
This
clearly
proves
our
lemma
Thus
let
us
assume
that
is
given
and
that
satisfies
a
d
We
may
clearly
assume
that
is
a
spanning
subgraph
of
Let
us
apply
Lemma
to
the
upper
uniform
graph
with
parameters
and
Let
be
the
regular
equitable
partition
we
obtain
in
this
way
Let
be
the
subgraph
of
on
with
an
edge
of
if
and
only
if
joins
two
vertices
that
belong
to
distinct
classes
of
our
regular
partition
say
and
with
an
regular
pair
and
In
the
sequel
we
let
stand
for
the
common
cardinality
of
the
sets
Recall
that
We
now
check
the
following
simple
fact
We
have
provided
is
sufficiently
large
From
the
upper
uniformity
of
it
follows
that
if
then
Hence
Also
is
at
most
Thus
the
number
of
edges
of
incident
to
is
at
most
for
large
enough
Now
note
that
with
the
sum
over
all
such
that
is
not
regular
is
at
most
Also
with
the
sum
extended
over
all
such
that
is
at
most
Finally
we
have
that
Therefore
if
is
sufficiently
large
as
required
We
now
define
a
graph
on
by
letting
be
an
edge
of
if
and
only
if
is
an
regular
pair
and
We
write
for
for
all
and
put
Now
put
and
notice
that
then
the
definition
of
and
a
above
gives
that
for
all
Lemma
now
tells
us
that
suitably
adjusting
the
notation
the
ordering
of
the
vertices
of
is
such
that
In
our
next
assertion
we
bound
We
have
Indeed
we
have
and
hence
by
Assertion
Our
next
step
relates
the
number
of
connected
pairs
meeting
two
fixed
classes
and
with
the
summand
appearing
in
Suppose
are
two
distinct
vertices
of
Then
the
number
of
connected
pairs
with
is
at
least
The
above
assertion
is
an
easy
consequence
of
Lemma
although
we
shall
have
to
work
a
little
to
check
that
that
lemma
does
apply
here
Let
us
start
by
observing
that
trivially
if
and
are
not
connected
in
then
by
definition
and
hence
there
is
nothing
to
prove
Thus
let
us
assume
that
this
is
not
the
case
and
let
be
two
vertices
of
such
that
Choosing
and
suitably
we
may
further
assume
that
We
may
now
restrict
our
attention
to
the
partite
subgraph
of
induced
by
the
Let
and
write
for
the
graph
on
isomorphic
to
with
and
as
the
endvertices
We
first
apply
Lemma
to
to
obtain
such
that
the
following
holds
Putting
we
have
for
all
and
furthermore
if
and
then
Let
Since
and
we
have
Moreover
as
we
have
Thus
relation
gives
that
for
any
where
as
defined
above
Note
also
that
cf
condition
a
above
Our
immediate
aim
now
is
to
apply
Lemma
To
make
our
current
notation
the
same
as
the
one
used
in
that
lemma
let
us
put
and
for
and
Clearly
and
Also
let
and
Let
and
Observe
that
by
b
above
we
may
conclude
that
for
both
We
shall
now
invoke
Lemma
but
to
see
that
that
lemma
does
apply
we
verify
the
following
claim
Conditions
i
v
given
before
the
statement
of
Lemma
hold
Condition
i
has
already
been
seen
to
hold
To
see
that
ii
holds
we
simply
apply
Lemma
to
the
balanced
graph
Now
condition
iii
clearly
holds
as
is
balanced
Finally
condition
iv
is
equivalent
to
c
while
condition
v
follows
from
d
This
finishes
the
proof
of
our
claim
In
view
of
the
above
claim
and
the
definitions
of
and
we
see
that
we
may
indeed
apply
Lemma
to
deduce
that
the
number
of
connected
pairs
with
is
at
least
We
now
use
that
for
we
have
since
Thus
the
quantity
in
is
at
least
which
concludes
the
proof
Assertion
since
and
were
chosen
so
as
to
have
The
proof
of
our
lemma
is
completed
in
the
next
assertion
Recall
that
stands
for
the
graph
on
with
two
vertices
of
adjacent
in
if
and
only
if
they
are
connected
in
We
have
By
Assertion
we
have
that
Now
clearly
we
have
since
Thus
recalling
and
using
that
we
have
from
that
is
at
least
which
by
Assertion
is
at
least
which
is
as
one
may
check
using
and
at
least
proving
Assertion
The
proof
of
Lemma
is
complete
Proof
of
the
Main
Result
We
first
prove
Theorem
under
the
extra
hypothesis
that
should
not
be
too
large
More
precisely
we
prove
the
following
result
Recall
that
we
write
if
any
subgraph
of
with
contains
a
copy
of
Lemma
Let
a
constant
be
given
Then
there
is
a
constant
that
depends
only
on
for
which
the
following
holds
If
and
then
almost
every
is
such
that
Proof
Let
and
Let
where
is
as
given
in
Lemma
We
shall
show
that
this
choice
of
will
do
in
our
result
Thus
let
be
as
in
the
statement
of
Theorem
and
consider
the
space
of
the
random
graphs
In
this
proof
we
shall
write
as
a
union
of
sparser
independent
random
graphs
Let
be
such
that
and
note
that
then
Put
We
shall
write
for
a
general
random
element
of
Thus
the
are
independent
random
graphs
each
taken
from
For
any
given
let
us
put
and
note
that
then
the
map
is
measure
preserving
We
may
thus
study
investigating
the
random
elements
Let
us
define
by
letting
belong
to
if
and
only
if
i
ii
for
all
and
finally
iii
for
all
the
graph
has
the
property
that
if
and
then
For
simplicity
above
stands
for
where
is
the
graph
on
with
edge
set
Elementary
facts
concerning
random
graphs
and
Lemma
gives
that
In
the
sequel
we
shall
often
condition
on
and
we
shall
write
for
the
conditional
probability
for
any
event
Let
be
the
set
of
that
admit
a
set
with
but
We
need
to
show
that
or
equivalently
that
Let
us
put
For
each
let
us
fix
once
and
for
all
a
set
as
required
in
the
definition
of
Let
us
also
put
and
set
and
Now
let
and
note
that
then
we
have
and
hence
that
from
which
we
conclude
that
where
the
last
inequality
follows
from
the
choice
of
Let
us
also
note
that
since
we
are
assuming
that
ii
above
holds
For
each
let
Clearly
and
hence
it
suffices
to
show
that
for
all
Thus
we
now
fix
and
proceed
to
show
that
almost
surely
does
not
hold
We
have
where
ranges
over
all
graphs
on
with
and
such
that
holds
for
all
with
We
now
fix
one
such
and
proceed
to
show
an
upper
bound
for
For
each
let
Then
We
now
fix
and
estimate
the
last
term
in
from
above
We
may
of
course
assume
that
for
the
fixed
triple
under
consideration
as
otherwise
there
is
nothing
to
prove
Thus
we
may
in
particular
assume
that
Let
us
write
for
the
set
of
such
that
and
To
show
that
is
small
we
argue
that
if
then
the
edges
of
the
graphs
are
distributed
in
a
rather
unlikely
way
Let
be
such
that
and
note
that
then
For
any
given
we
write
for
where
the
union
is
taken
over
all
Thus
is
a
random
element
from
and
Note
also
that
if
then
For
any
let
Also
let
for
any
Clearly
is
binomially
distributed
with
parameters
and
In
fact
it
is
clear
that
has
this
distribution
even
if
we
condition
on
being
such
that
We
now
verify
the
following
claim
from
which
we
shall
deduce
an
exponential
upper
estimate
for
In
the
sequel
we
write
for
the
expectation
in
the
space
If
then
Let
us
fix
Let
and
put
Clearly
and
since
spans
no
we
have
Thus
we
have
and
hence
where
We
now
show
that
is
suitably
large
We
have
and
hence
Therefore
where
the
last
inequality
follows
from
Thus
we
conclude
that
We
now
note
that
Note
that
in
particular
by
and
the
choice
of
we
have
Let
denote
the
right
hand
side
of
Then
and
therefore
as
claimed
We
now
use
our
claim
to
bound
which
we
recall
is
defined
in
above
Recall
also
that
We
have
where
as
remarked
before
Thus
from
we
deduce
that
We
now
recall
to
deduce
that
completing
the
proof
of
Lemma
We
next
show
that
loosely
speaking
the
quantity
is
non
increasing
in
probability
for
any
fixed
graph
In
particular
this
shows
that
Lemma
implies
Theorem
Lemma
Suppose
and
are
such
that
as
Suppose
also
that
holds
almost
surely
for
some
graph
Then
if
is
such
that
for
all
large
enough
we
almost
surely
have
Proof
Write
Let
be
as
in
the
statement
of
our
lemma
Suppose
for
a
contradiction
that
fails
with
probability
at
least
for
arbitrarily
large
values
of
where
is
some
positive
absolute
constant
Put
Note
that
we
may
generate
by
first
generating
and
then
randomly
removing
its
edges
each
with
probability
and
with
all
these
deletions
independent
Looking
at
this
method
for
generating
we
shall
deduce
below
that
the
probability
that
fails
is
at
least
for
arbitrarily
large
which
is
a
contradiction
Let
For
arbitrarily
large
with
probability
at
least
we
have
that
fails
and
Suppose
that
when
generating
by
the
above
method
we
first
generated
a
satisfying
above
Let
be
an
free
subgraph
of
with
Clearly
the
free
subgraph
of
is
a
subgraph
of
our
We
have
and
with
probability
and
hence
we
have
with
probability
Therefore
given
that
satisfies
above
the
probability
that
we
generate
a
for
which
fails
is
Since
the
probability
that
we
generate
satisfying
is
at
least
for
arbitrarily
large
we
conclude
that
our
will
fail
to
satisfy
with
probability
at
least
for
arbitrarily
large
which
is
the
contradiction
we
were
after
Proof
of
Theorem
Theorem
follows
at
once
from
Lemmas
and
A
simple
variant
of
the
method
used
in
the
proof
of
Lemma
gives
the
following
equivalence
result
between
the
binomial
and
the
uniform
models
of
random
graphs
with
respect
to
the
property
Lemma
Let
be
a
graph
Consider
the
following
two
assertions
holds
almost
surely
holds
almost
surely
where
and
are
arbitrary
functions
Suppose
as
Then
the
following
holds
i
Suppose
and
Let
and
Then
implies
ii
Suppose
and
Let
and
Then
implies
Proof
Let
us
prove
i
Assume
holds
We
may
generate
by
first
generating
conditioned
on
the
event
and
then
randomly
adding
edges
to
it
so
as
to
have
a
graph
with
edges
For
clarity
let
us
write
for
our
binomial
random
graph
conditioned
on
Note
that
and
hence
the
effect
of
conditioning
on
is
so
to
speak
negligible
We
now
claim
that
holds
with
probability
Suppose
our
claim
fails
and
hence
for
arbitrarily
large
there
exists
with
probability
at
least
an
free
subgraph
of
with
where
is
some
positive
absolute
constant
Observe
that
if
is
an
free
subgraph
of
then
obviously
is
an
free
subgraph
of
Now
note
that
almost
surely
we
have
and
hence
almost
surely
Since
we
are
assuming
that
with
probability
for
arbitrarily
large
we
have
with
probability
for
arbitrarily
large
Since
is
the
binomial
random
graph
conditioned
on
the
almost
sure
event
we
deduce
that
with
probability
at
least
for
arbitrarily
large
contradicting
Thus
follows
The
proof
of
ii
is
similar
Proof
of
Corollary
Corollary
follows
easily
from
Theorem
and
Lemma
Deterministic
Consequences
In
this
section
we
give
a
few
results
concerning
the
existence
of
very
sparse
graphs
that
satisfy
for
any
fixed
If
is
a
graph
of
order
and
size
recall
that
its
density
is
For
an
integer
let
be
the
family
of
all
graphs
with
and
Also
let
be
the
collection
of
all
graphs
that
are
free
for
all
The
following
result
may
be
proved
by
the
so
called
deletion
method
For
details
see
Theorem
Let
and
be
fixed
Then
there
exists
a
graph
such
that
We
now
single
out
a
corollary
to
Theorem
In
Corollary
below
the
property
that
belongs
to
in
Theorem
is
replaced
by
a
collection
of
simpler
and
more
concrete
conditions
For
instance
one
of
these
conditions
is
that
should
not
contain
a
copy
of
To
state
another
condition
that
appears
in
Corollary
we
need
to
introduce
a
definition
Let
be
a
graph
Suppose
are
distinct
copies
of
in
and
are
edges
of
such
that
and
for
all
Then
we
say
that
is
an
path
in
Now
assume
that
is
an
path
in
and
that
the
edge
joins
a
vertex
in
to
a
vertex
in
Then
is
said
to
be
an
quasi
cycle
in
It
is
immediate
to
check
that
if
is
an
path
then
has
density
Also
if
is
an
quasi
cycle
then
has
density
Corollary
For
any
and
there
is
a
graph
such
that
i
contains
no
ii
any
two
copies
of
in
share
at
most
two
vertices
iii
contains
no
quasi
cycles
for
any
and
iv
We
remark
that
Erd
os
and
Ne
set
ril
have
raised
the
question
as
to
whether
the
graphs
as
in
Corollary
exist
A
Conjecture
In
this
short
paragraph
we
state
a
conjecture
from
which
if
true
one
may
deduce
Conjecture
Let
be
a
graph
of
order
and
suppose
has
vertices
Let
be
given
Let
also
be
a
family
of
pairwise
disjoint
sets
each
of
cardinality
Suppose
reals
and
and
an
integer
are
given
We
say
that
an
partite
graph
with
partition
and
size
is
an
graph
if
the
pair
is
regular
and
has
density
whenever
Conjecture
Let
constants
and
be
given
Then
there
are
constants
and
such
that
if
the
number
of
free
graphs
is
at
most
for
all
and
all
sufficiently
large
If
above
is
a
forest
Conjecture
holds
trivially
since
in
this
case
all
graphs
contain
a
copy
of
A
lemma
in
Kohayakawa
uczak
and
R
odl
may
be
used
to
show
that
Conjecture
holds
for
the
case
in
which
In
fact
this
lemma
from
is
similar
in
spirit
to
Lemma
above
although
much
simpler
Acknowledgements
We
are
indebted
to
B
Kreuter
for
a
careful
reading
of
the
manuscript
Babai
L
Extremal
subgraphs
of
random
graphs
Extremal
Graph
Theory
Academic
Press
London
Random
Graphs
Academic
Press
London
Subgraphs
of
a
hypercube
containing
no
small
even
cycles
Large
triangle
free
subgraphs
in
graphs
without
Random
Ramsey
graphs
for
the
four
cycle
Haxell
P
E
Kohayakawa
Y
uczak
T
The
induced
size
Ramsey
number
of
cycles
Tur
an
s
extremal
problem
in
random
graphs
forbidding
odd
cycles
Tur
an
s
extremal
problem
in
random
graphs
forbidding
even
cycles
Janson
S
Poisson
approximation
for
large
deviations
Kohayakawa
Y
Kreuter
B
Steger
A
An
extremal
problem
for
random
graphs
and
the
number
of
graphs
with
large
even
girth
submitted
Kohayakawa
Y
uczak
T
Arithmetic
progressions
of
length
three
in
subsets
of
a
random
set
Acta
Arithmetica
Ruci
nski
A
Lower
bounds
on
probability
thresholds
for
Ramsey
properties
Comb
in
ator
ics
Paul
Erd
os
is
Eighty
Volume
Mikl
os
D
S
os
V
T
Sz
onyi
T
Budapest
Bolyai
Soc
Math
Studies
Threshold
functions
for
Ramsey
properties
Regular
partitions
of
graphs
Probl
emes
Combinatoires
et
Th
eorie
des
Gra
phes
Proc
Colloque
Inter
CNRS
Bermond
J
C
Fournier
J
C
Las
Vergnas
M
Sotteau
D
CNRS
Paris