Graphs, Polytopes, Quadrics

Chris Godsil

University of Waterloo

Outline

  • Eigenvectors and polytopes.
  • Parallel faces and cocliques.
  • Quadrics...
  • ...and spherical designs.

A Graph:

Eigenvalues

\[ 3,\\ \sqrt{5},\ \sqrt{5},\ \sqrt{5},\\ 1,\ 1,\ 1,\ 1,\ 1,\\ 0,\ 0,\ 0,\ 0,\\ -2, -2, -2, -2,\\ -\sqrt{5}, -\sqrt{5}, -\sqrt{5} \]

Eigenvectors

\[ U = \begin{pmatrix} -0.3873& 0.0& 0.0\\ -0.2887& -0.1706& 0.1938\\ -0.1291& -0.0228& 0.3644\\ -0.1291& 0.2391& 0.2760\\ 0.1291& 0.3042& 0.2020\\ 0.2887& 0.0826& 0.2446\\ 0.1291& -0.1195& 0.3450\\ 0.1291& -0.3270& 0.1625\\ -0.1291& -0.3586& 0.0690\\ & \vdots& \end{pmatrix} \]

An Embedding

Properties of $U$

  • $U^TU=I$
  • $UU^TUU^T=UU^T$ and consequently $UU^T$ represents orthogonal projection on the $\sqrt{5}$-eigenspace.

Eigenvectors and Faces

  • Any vector $Uh$ is an eigenvector for $A$.
  • The vertices $i$ such that $(Uh)_i$ is maximal form a face of the polytope.
  • Each eigenvector determines a parallel pair of faces.

Bounding Cocliques

  • Let $X$ be a $k$-regular graph on $n$ vertices with least eigenvalue $\tau$. If $S$ is a coclique in $X$ then \[ |S| \le \frac{n}{1-\frac{k}{\tau}}. \]
  • If equality holds and $x$ is the characteristic vector of $S$, then \[ x - \frac{|S|}{n}\one \] is an eigenvector for $X$ with eigenvalue $\tau$.

Parallel Faces

Let $U$ be an $m\times m$ matrix whose columns form an orthonormal basis for the $\tau$-eigenspace. Then there is a vector $h$ in $\re^m$ such that \[ x - \frac{|S|}{n}\one = Uh. \]

It follows that we can partition the $\tau$-eigenpolytope into a parallel pair of faces.

Vanishing Quadratics

Suppose $Uh$ is the shifted characteristic vector of a coclique, and denote its entries by $\alpha$ and $\beta$. Then the function \[ (h^Tx-\alpha)(h^Tx-\beta) \] is a quadratic polynomial that vanishes on the image of each vertex of $X$.

Veroneses

The Veronese map $\ver_k$ is a mapping from a vector space of dimension $m$ to a vector space of dimension $\binom{m+k}{k}$ such that the entries of $\ver_k(x)$ are all monomials of degree at most $k$ in the entries of $x$.

An example: if \[ x = \begin{pmatrix}a&b\end{pmatrix} \] then \[ \ver_2(x)= \begin{pmatrix}1&a&b&a^2&ab&b^2\end{pmatrix} \]

No Quadrics

If $U$ is a matrix, then $\ver_k(U)$ is the matrix we get by applying $\ver_k$ to each row.

Lemma: There is a quadratic polynomial that vanishes on each row of $U$ if and only if the columns of $\ver_2(U)$ are linearly dependent.

What can I hit, Dad?

Find graphs where we can use the rank of the Veronese of an eigenspace to rule out the existence of ratio-tight cocliques.

Spherical Designs

A subset $S$ of the unit sphere in $\re^d$ has strength $t$ if the average value over $S$ of any polynomial of degree at most $t$ is equal to its average over the entire sphere. We say $S$ is a $t$-design if its strength is at least $t$.

Thus $S$ is a 1-design if and only if the sum of its elements is zero.

Walks and Angles

  • We have the spectral decomposition $A^k = \sum_r \theta_r^k E_r$ where $E_r$ represents orthogonal projection on the $\theta_r$-eigenspace.
  • If $U_r$ is a matrix whose columns form an orthonormal basis for the $\theta_r$-eigenspace, then $E_r=U_rU_r^T$ and so $(E_r)_{i,j}$ is the inner product of the $i$-th and $j$-th rows of $U_r$.
  • The distance between the images of $i$ and $j$ in the $\theta_r$-eigenspace is determined by the sequence $((A^k)_{i,j})_{k\ge0}$ (ie, by the walk generating function).

1-Designs

If $X$ is $k$-regular and $\theta_r\ne k$, then $\one^TU_r=0$. Hence the vertices of $X$ form a 1-design.

2-Designs

  • If the diagonal of $A^k$ is constant for all $k$ then the images of the vertices of $X$ all have the same length. (If the condition holds, $X$ is walk regular.)
  • If $\seq x1n$ are unit vectors in $\re^d$, they form a 2-design if and only if $\sum x_i=0$ and $\sum x_i x_i^T= (n/d)I$.

2-Designs ctd.

  • Let $u(i)$ denote the $i$-th column of $U_r^T$. Then \[ I=U_r^TU_r=\sum u(i)u(i)^T \] and hence, if $X$ is walk regular and $\theta_r\ne k$, the vertices of $X$ form a spherical 2-design.

Remarks

  • If we extend $x$ in $\re^d$ to a vector in $\re^{d+1}$ by putting a 1 on top, then the map $x\mapsto xx^T$ is (essentially) the Veronese map.
  • If the images of the vertices lie on a sphere, then they lie on a quadric and $\ver_2(U_r)$ cannot have linearly independent columns. (We can easily correct for this though.)

3-Designs

If $h$, $\alpha$, $\beta$ are such that $(h^Tx-\alpha)(h^Tx-\beta)$ is zero on all vertices of $X$, then \[ (h^Tx-\alpha)(h^Tx-\beta) \ell^Tx \] is zero on all vertices.

If the vertices of $X$ form a 3-design, then it follows that $(h^Tx-\alpha)(h^Tx-\beta)$ is orthogonal to all linear functions.

In particular it must be orthogonal to $h^Tx$.

3-Designs, ctd.

  • $(h^Tx-\alpha)(h^Tx-\beta)h^Tx$ is equal to \[ (h^Tx)^3 -(\alpha+\beta)(h^Tx)^2 +\alpha\beta h^Tx \]
  • $(h^Tx)^3$ and $h^Tx$ are odd functions, hence their average over the sphere is zero.
  • The average of $(h^Tx)^2$ over the sphere is not zero. If the coclique has size $s$ then $\alpha=1/s$ and $\beta=-1/(n-s)$.

Corollary

If the $\tau$-eigenspace is a 3-design and there is a ratio-tight coclique, then $X$ is bipartite and the coclique is a color class.