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 1If 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.