REU 2005 · Potpourri · Lecture 2

Instructor: László Babai Scribes: Sourav Chakraborty

July 22, 2005. Last updated July 25, 2005

10 Potpourri 2

10.1 2-Distance set

Recall the definition of 2-distance sets in ℝ^{n}:

Definition 10.1. A 2-distance set in ℝ^{n} is a set of points {p_{1}, …, p_{m}} such that dist(p_{i}, p_{j}) ∈ {α, β} for i ≠ j. That is, the distance between any two distinct points in the set has one of two fixed values.

We denote by m_{2}(n) the maximum size of a 2-distance set in ℝ^{n}.

Exercise 10.2. Prove that m_{2}(n) > cn^{2} for some constant c.

Recall that a one-distance set in ℝ^{n} has ≤ (n+1) vertices. Recall that the set of standand unit vectors {e_{i} : 1 ≤ i ≤ n} is a set of size n and is a one-distance set in ℝ^{n}.

Taking clue from the above example we can say that the set {(e_{i} + e_{j}) : 1 ≤ i < j ≤ n} is a 2-distance set in ℝ^{n}. The size of this set is \binom{n}{2}.

Exercise 10.3. m_{2}(n) ≥ \binom{n+1}{2}.

10.2 Linear Algebra

Consult the Linear Algebra and appications to graphs Part I and II handouts.

10.3 Adjacency matrix of graph

Let G be a simple graph (that is, no multiple edges and no self loop). Let the adjacency matrix is A. And let λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n} be the eigenvalues of the adjacency matrix of G.

In other words the charecteristic polynomial f_{A}(x) factors as f_{A}(x) = Π(x − λ_{i}).

Exercise 10.4. Prove that deg_{min} ≤ λ_{1} ≤ deg_{max}, where deg_{min} and deg_{max} are the minimum and maximum degrees of the graph, respectively.

Exercise 10.5. λ_{1} ≥ average degree. Here “average degree” is \frac{Σ_{i∈V} deg(i)}{n} = \frac{2m}{n}, where m is number of edges. Exercise 10.6. Σ_{i=1}^{n}λ_{i} = 0.

By the trace of a matrix we mean the sum of the diagonal entries. Exercise 10.7. For any square matrix the sum of the eigenvalues is same as the trace.

From this it follows that unless G is the empty graph (no edges) λ_{1} > 0 and λ_{n} < 0. Exercise 10.8. Prove that |λ_{n}| ≤ λ_{1}. Exercise 10.9. If G is bipartite then prove that λ_{n−i} = −λ_{i+1} for all 0 ≤ i < n.

Conversely, Exercise 10.10. Prove that if G is connected and λ_{n} = −λ_{1} then G is bipartite. Show that this statement fails if we drop the assumption of connectedness. Exercise 10.11. If M is a square matrix over ℂ with eigenvalues μ_{1}, μ_{2}, …, μ_{n}, then the eigenvalues of M^{2} are μ_{1}^{2}, μ_{2}^{2}, …, μ_{n}^{2}.

The proof of the above exercise is easier when M is real symmetric. Corollary 10.12. Σ_{i=1}^{n}μ_{i}^{2} = trace of M^{2}. Exercise 10.13. Give a combinatorial meaning to Σ_{i=1}^{n}λ_{i}^{2}.

[HINT (1) : The answer is very simple]

[HINT (2) : The above corollary] Exercise 10.14. Find the combinatorial meaning of each entry of A^{2}. Definition 10.15. A regular graph of degree r is a graph for which the degree of all the vertices is r.

From a previous exercise we get that for a regular graph λ_{i} = r. Exercise 10.16. Find a eigenvector corresponding to eigenvalue r of the regular graph of degree r. Exercise 10.17. What is the multiplicity of the eigenvalue r? [HINT: Answer is a very simple combinatorial parameter of G.]

10.4 Interlacing

Exercise* 10.18. Let G be a general graph with eigenvalues λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n}. Let H = G\v (that is, the graph G with the vertex v deleted) and let μ_{1} ≥ μ_{2} ≥ ⋯ ≥ μ_{n−1} be the eigenvalues of H. Then,

λ_{1} ≥ μ_{1} ≥ λ_{2} ≥ μ_{2} ≥ ⋯ ≥ μ_{n−1} ≥ λ_{n}

This property is called interlacing.

We can actually prove a more general statement.

Exercise* 10.19. Let A be a n × n real symmetric matrix. Let B is the matrix obtained by deleting the i-th row and i-th column of A. Prove that the eigenvalues of B interlace the eigenvalues of A.

[HINT (1): Use Spectral Theorem]

[HINT (2): Prove λ_{1} ≥ μ_{1} using the following exercise]

Exercise 10.20 (Courant-Fisher Equality). λ_{1} = max_{∥x∥=1} x^{T} Ax.

10.5 Chebyshev’s Polynomial

Consider the following functions:

T_{n}(cos θ) = cos(nθ)

.

Exercise 10.21. Prove that T_{n} is a polynomial of degree n. Find its leading coefficient.

These polynomials are called Chebyshev’s Polynomials of the first kind.

For example T_{0}(x) = 0.

T_{1}(x) = x.

T_{2}(x) = 2x^{2} − 1. This follows from the fact cos(2θ) = 2 cos^{2}(θ) − 1.

Exercise 10.22. 1. Calculate T_{3}(x)andT_{4}(x).

2. Give a recursive formula for T_{n}.

3. Show all roots of T_{n} are real and are interlaced by the roots of T_{n−1}.

Exercise 10.23. Calculate the eigenvalues of the

1. Path of length (n − 1).

2. Cycle of length n.

Exercise 10.24. Find the connection between the previous two exercises.