\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\lecture{1: Spectral Theory and Decomposition Problems, day 1/2}{Week 4}

Welcome to week 2!  Last week was all about building intuition and techinques within the world of spectral graph theory: specifically, in the span of a week, we introduced the ideas of the adjacency and Laplacian matrices, re-examined many of the basic questions of an intro to graph theory course (i.e. bounds on the chromatic number, characterizing bipartite graphs, counting trees,) and hopefully saw just how much more firepower the language of linear algebra offers us in attacking graph-theoretic questions.

This week, we're going to switch to a much more applied and graph-theory-centric approach.  Instead of last week, where our theorems and proofs explicitly related graphs to their spectra, this week's classes will pose questions that (on their face) have nothing to do with spectral graph theory, but yet can often only be answered using these tools!  

Specifically, in the next two lectures we're going to talk about some results in graph \textbf{structures} and \textbf{decompositions}, concepts we define in the next section:

\section{Motivation/Definitions}
\begin{definition}
Given a graph $G$, a \textbf{graph decomposition} $\mathcal{H}$ is a collection $\{H_1, \ldots H_n\}$ of subgraphs of $G$, such that every edge of $G$ lies in at least one $H_i$ and no edge lies in more than 1 $H_i$.  For example, the following picture is a decomposition of the drawn graph $G$ into 9 triangles $H_1, \ldots H_9$:
\begin{center}
\includegraphics[width=3in]{graph_decomposition_ex.pdf}
\end{center}
If all of the $H_i$'s are isomorphic to some graph $H$, we will call such a decomposition a $H$-decomposition of $G$.  As a quick example, take the above picture: the right-hand side is a triangle-decomposition of $G$.  
\end{definition}

Given a collection $\mathcal{H}$ and a graph $G$, finding a $\mathcal{H}$-decomposition of $G$ is generally a fairly hard problem, and one that my research is currently focusing on!  Specifically, in 1975, my advisor proved the following claim, which was a large part of how he got his name in combinatorics:
\begin{theorem}
(Wilson:)  Let $\mathcal{H}$ be a collection of simple graphs, and $d$ be the GCD of the degrees of the vertices in all of the graphs in $\mathcal{H}$.  Then, there is some sufficiently large integer $N_D$ such that for any $n > N_D$, if
\begin{itemize}
\item $n(n-1)$ is divisible by $|E(D)|$, and 
\item $n$ is divisible by $d$, 
\end{itemize}
then the complete graph $K_n$ has a $\mathcal{H}$-decomposition.
\end{theorem}

My current research is into a generalization of this: suppose that we work with ``almost-complete'' graphs, i.e. graphs where the degree of every vertex is $\geq n \cdot (1-\epsilon)$, for some small epsilon.  Does the same result hold?

In this class, we're not going to directly attack the above question -- it's mostly there as motivation for *why* we study graph decompositions.  Instead, we're going to focus on graph decompositions where we're breaking a graph up into relatively few pieces, and discuss when such things are even possible!  We start in this section:

\section{Warmup: The Petersen Graph}
\begin{question}
Can $K_{10}$ be decomposed into three copies of the Petersen graph?
\end{question}
At first glance, this seems plausible: $K_{10}$ has 45 edges and 10 vertices, all regular of degree 9, while each Petersen graph has 15 edges, 10 vertices, and is regular of degree 3.  

However, repeated attempts to find such a decomposition will quickly start to persuade you that no such thing exists.  A proof that no such decomposition exists can be brute-forced by simply checking all of the ways to draw a pair of edge-disjoint Petersen graphs on ten vertices, but a far more elegant and beautiful way to do this is via the tools we've just developed in spectral graph theory!


Specifically: take any edge-disjoint pair of Petersen graphs that are subgraphs of $K_{10}$; color the first of these Petersen subgraphs red and the second blue.  Color the remaining edges green.  Thinking of these three colored subgraphs as graphs in their own right, denote their adjacency matrices as $A_{P_R}, A_{P_B},$ and $A_{G}$ respectively.  Then, because the union of these three graphs is $K_{10}$, we have
\begin{align*}
A_{P_R} + A_{P_B} + A_{G} = A_{K_{10}} = J - I,
\end{align*}
where $J$ is the $10 \times 10$ all-1's matrix, and $I$ is the identity matrix.

Our plan from here is the following: 1 is not an eigenvalue of the complete graph, yet it shows up an awful lot as an eigenvalue of the Petersen graph (recall from class/the HW that the spectrum of the Petersen graph is $\{3^1, 1^5, (-2)^4\}$.)  We are going to show that this causes a contradiction.

To do this, recall that we actually know the Petersen graph's eigenvector for the eigenvalue 3: specifically, because the Petersen graph is regular of degree 3, we have
\begin{align*}
A_P \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right) = \left( \begin{array}{c} \deg(v_1) \\ \deg(v_2) \\ \vdots \\ \deg(v_{10}) \end{array} \right) = \left( \begin{array}{c} 3 \\ 3 \\ \vdots \\ 3 \end{array} \right),
\end{align*}
and thus that the all 1's vector is the eigenvector for the eigenvalue 3.  

Consequently, we know that (because eigenvectors for different eigenvalues are orthogonal) all of the eigenvalues for $1$ are orthogonal to this all-1's vector.  Take $U_{R,1}$ to be the 5-dimensional eigenspace corresponding to the red Petersen graph's eigenvalue 1, and define $U_{B,1}$ similarly.  Then, because these all live in the 9-dimensional space $\{\mathbf{v}: \mathbf{v} \perp (1,1,\ldots 1) \},$ any two of them must share a vector in common!  Let $\mathbf{v} \in U_{B,1} \cap U_{R,1}$ be such a vector. 

Then, what happens when we multiply $A_{K_{10}}$ by $\mathbf{v}$?  Well: $\mathbf{v}$ is orthogonal to the all-1's vector, so we have
\begin{align*}
A_{K_{10}} \mathbf{v} = (J - I)\mathbf{v} = \left[ \begin{array}{cccc}  1& 1 & \ldots & 1\\1& 1 & \ldots & 1\\\vdots & \vdots & \ddots & \vdots \\ 1& 1 & \ldots & 1\\ \end{array} \right] \mathbf{v} - I\mathbf{v} = 0-\mathbf{v} = (-1)\mathbf{v}.
\end{align*}
But, on the other hand, if we use our decomposition of $K_{10}$, we instead have
\begin{align*}
A_{K_{10}} \mathbf{v} = (A_{P_R} + A_{P_B} + A_{G})\mathbf{v} = A_{P_R}\mathbf{v} + A_{P_B}\mathbf{v} + A_{P_G}\mathbf{v} = 2\mathbf{v} + A_{P_G}\mathbf{v}.
\end{align*}
Combining these results, we have
\begin{align*}
-\mathbf{v} = 2\mathbf{v} + A_{P_G}\mathbf{v} \Rightarrow A_{G}\mathbf{v} = -3\mathbf{v}
\end{align*}

In other words, $\mathbf{v}$ is an eigenvector of $A_G$, with eigenvalue $-3$.  Because $-3$ is not an eigenvalue of the Petersen graph, we can conclude that our green graph is not the Petersen graph.

\section{The Lagrangian}
The above was a beautiful proof!  As mathematicians, a natural thing to want to do with any such proofs is to try to find ways to \textbf{extend} their concepts to other questions; how can we do this here?

Well: in some sense, the main trick we used in the proof above was the idea that we were trying to decompose a graph that didn't have a given eigenvalue into a relatively small number of copies of a second graph that *did* have that eigenvalue, and specifically had that eigenvalue a ton of times!  However, one issue with the example above is that it relied on us knowing the given eigenvalues *specifically* for our graphs, and kind-of came down to a calculation at the end that was a little out of nowhere.  Often, we might not know the precise eigenvalues of the graph we're looking to study, nor the precise eigenvalues of the graphs we're trying to decompose into, but rather just (say) their signs: one of them will have lots of negative small eigenvectors, while the other will just have one or two rather big negative ones.

Can we make a tool that is ``fuzzy'' enough to not need us to know all of the eigenvalues, but still cares enough about them to distinguish between (say) things that are like the complete graphs $K_n$ (spectrum $\{(n-1)^1,(-1)^{n-1}\}$) and things like the complete bipartite graphs $K_{n,m}$ (spectrum $\{\pm(\sqrt{nm})^1,(0)^{n-2}\}$?)

As it turns out, yes!  We call this tool the \textbf{Lagrangian}, and define it here:
\begin{definition}
The \textbf{Lagrangian} of a graph $G$ is a function $\mathbb{R}^n \to \mathbb{R}$ defined as follows:
\begin{align*}
f_G(\mathbf{v}) = \langle A_G \mathbf{v}, \mathbf{v} \rangle = (A_G\mathbf{v})^T\cdot\mathbf{v} = \sum_{(i,j) \in E(G)} v_iv_j.\\
\end{align*}
On one hand, you can think of this function as being the sum of all of the edges in $G$, ``weighted'' by the components of $\mathbf{v}$.  On the other hand, you may recognize this from our earlier work as a really useful function, that had the nice property 
\begin{align*}
\lambda_{\textrm{min}} \cdot ||\mathbf{v}|| \leq f_G(\mathbf{v}) \leq \lambda_{\textrm{max}}||\mathbf{v}||,
\end{align*}
and attained these minima and maxima values on values of $\mathbf{v}$ that were eigenvectors for $\lambda_{\textrm{min}}, \lambda_{\textrm{max}}$.
\end{definition}

This tool has a number of properties!  We state one of the most useful of them here:
\begin{proposition}
Setup: Given a graph $G$, let $W^+$ denote the space generated by all of the positive eigenvectors of $A_G$, $W^-$ the space generated by all of the negative eigenvectors, and $W^0$ the eigenspace corresponding to 0.  Notice that because $A_G$ is symmetric, by the spectral theorem, we can write any element in $\mathbb{R}^n$ as a sum of one element from each of these spaces.

We claim that our function $f_G$ is positive-semidefinite\footnote{A function is \textbf{positive-semidefinite} if its values are always $\geq 0$.} on the space $W^+ \oplus W^0$ (i.e. the space generated by all of the nonnegative eigenvectors,) and negative-semidefinite on the space $W^- \oplus W^0$.
\end{proposition}
\begin{proof}
On the HW!
\end{proof}

So: this is an easily-calculated function that does the ``fuzzy'' thing we wanted it to do: find eigenvalues! We close this section by mentioning a famous result we'll prove next class in like five minutes with this tool, which (I think) really doesn't admit any nice non-spectral proofs:

\begin{theorem}
The complete graph $K_n$ cannot be decomposed into $\leq n-2$ complete bipartite graphs.
\end{theorem}
\end{document}