Scribed by Theo McKenzie
In which we study the spectrum of random graphs.
1. Overview
When attempting to find in polynomial time an upper bound certificate on the max cut and maximum independent set of a graph, we have used the following property. If , then with high probability
, where
is the spectral norm. Generally, if
and
then w.h.p.
Today we will prove how to obtain the bound in Proposition 1 with an extra term of , as well as show an outline of the method of finding the bound in Proposition 1. We will also show how when
is small this bound breaks down, namely how when
,
2. Introducing the Trace
Henceforth signifies
. Take
symmetric and real. All eigenvalues of this matrix are real, and we can enumerate them
such that
.
The trace is defined to be
where
is an
matrix.
Moreover we know that \textnormal{Tr}. If we take
large and even, the eigenvalues of
are
. Therefore we have
Moreover we have
This gives us an estimation of the norm, , which for
gives a constant factor approximation of
.
3. Using the Trace to Bound the Spectral Norm
Assume that and
is the adjacency matrix of
. We will prove the following.
is bounded above by
. If
, by taking the
th root we achieve a bound of
on
.
3.1. Expected Value of Matrix Entries
First, we examine the matrix . We have
and
with equal probability of each when
. Moreover
. If
if
is odd and
for
even.
by the linearity of expectation and symmetry between the entries. We evalute
.
where represents the intermediate steps on a “path” between vertices that starts at 1 and returns to 1. For example,
. Note that we can repeat edges in these paths. By the linearity of expectation
If any pair occurs
times in the sequence of pairs
, where
is odd, then as the value of this term is independent from all other terms and
for odd
, then
. If all pairs occur an even number of times, their product’s expectation is 1. Therefore
is the number of sequences
such that, in the sequence of pairs
, each pair occurs an even number of times.
3.2. Encoding argument
In order to give an upper bound on the number of such sequences, we will show how to encode a sequence where there are distinct edges. In the sequence
, the element
is represented either as
, which takes
bits, if
appears for the first time in the sequence at location
, and as
otherwise, where
is such that
, which requires
bits. Notice that, if
occurs for the first time at location
, then the pair
also occurs for the first time at the location
and
. Thus the number of times that we encounter a vertex for the first time is at most the number of distinct edges. If we have
distinct vertices (other than vertex 1), then we are using
; for
, this value increases with
, but we have
(because every edge has to appear an even number of times and so there can be at most
distinct edges. This means that we use at most
bits in the encoding. The number of strings that can be encoded using at most
bits is
. If we assume
, we have the bound
, meaning
Therefore using suitable and
we achieve our bound on
. For example, choose
and
. We use Markov’s inequality to obtain
4. Tightening the Bound
To obtain the sharper bound of , we need to count the number of pairs more sharply and remove the
term, namely improve the way we talk about repetitions. Here we give an outline for how to find a tighter bound.
The worst case in the above analysis is when the number of distinct vertices (not counting vertex ) is maximal, which is
. In that case, the number of distinct “edges”
is
, and they must form a connected graph over
vertices, that is, they have to form a tree. Furthermore, each edges is repeated exactly twice in the closed walk, otherwise we would not have enough distinct edges to connect
distinct vertices.
If the pairs form a tree, then the only way we can have closed walk in which every edge is repeated twice is that the closed walk is a depth-first visit of the tree. In this case, we can improve our encoding in the following way. In a depth-first visit of a tree only two events are possible at each step: either we discover a new vertex, or we backtrack on the edge between the current node and the parent node. Thus we only need to pay bits to encode a new node in the sequence and
bit to encode an already seen node, and we obtain a bound of
. By taking the
th root we obtain a bound on
of
.
5. Generalizing to any
Now assume and
is the adjacency matrix of
. We also assume
. We define
In this matrix and if
with probability
and
with probability
. Therefore
. In fact,
for all
.
From this we see we need to sum over sequences such that the multiset has each pair occuring at least two times, as if any pair occurs once, the expectation is .
Therefore the bound is
where is the number of distinct pairs and the sum is taken over multisets where each pair occurs at least twice. For large
, the number of sequences where each pair occurs at least twice with
distinct pairs is approximately
. This would give us
so the bound on is
. However, the bound on the number of sequences with
distict pairs breaks down when
is much smaller than
. In a full proof much more complicated calculations must be done.
6. Problems with sparse graphs
If , then
w.h.p.
This breaks down the nice bound we obtained in section 5. This follows from the irregularity of sparse graphs. There will be isolated vertices and vertices with degree much higher than average.
Lemma 1 If
then w.h.p. the highest degree vertex of
is of order
.
If G has a node of degree , then, for every
,
. This implies that
.
Proof: We have
where the maximum is taken over all nonzero vectors . Call
a node of degree
and call
of its neighbors
.
Consider the vector such that
and
for other vertices
. We have
Therefore if ,
yielding the desired bound.
Theorem 4 proceeds immediately from Proposition 5 and Lemma 1.