The Eigenvalue Method for Extremal Problems on Infinite Vertex-Transitive Graphs
More Info
expand_more
Abstract
This thesis is about maximum independent set and chromatic number problems on certain kinds of infinite graphs. A typical example comes from the Witsenhausen problem: For $n \geq 2$, let $S^{n-1} := \{ x \in \R^n : \|x\|_2 =1 \}$ be the unit sphere in $\R^n$, and let $G=(V,E)$ be the graph with $V = S^{n-1}$, in which two points in $S^{n-1}$ are adjacent if and only if their inner product is equal to $0$. What is the largest possible Lebesgue measure of an independent set in $G$? The problem is reminiscent of a coding theory problem, in which one asks for the size of a largest set of distinct points in some metric space so that the distance between each pair of points is at least some specified constant $d$. Such a problem can be framed as a maximum independent set problem: Define a graph whose vertex set is the metric space, and join two points with an edge whenever their distance is less than $d$. The codes of minimum distance $d$ are then precisely the independent sets in this graph. In the Witsenhausen problem, rather than asking for a set of points in the sphere in which all the distances less than $d$ are forbidden, we ask for a set of points in which only one distance is forbidden. And it turns out that the \emph{Delsarte} (also called \emph{linear programming}) upper bounds for the size of codes \cite{delsarte73} can be adjusted to give upper bounds for the measure of an independent set in the Witsenhausen graph. This was first done in \cite{bachoc09} and \cite{oliveira09}. The Witsenhausen problem was stated in \cite{witsenhausen74}, and in the same note it was shown that the fraction of the $n$-dimensional sphere which can be occupied by any measurable independent set is upper bounded by the function $1/n$. Frankl and Wilson \cite{frankl-wilson81} made a breakthrough in 1981 when they proved an upper bound which decreases exponentially in $n$. Despite this progress on asymptotics, the $1/3$ upper bound in the $n=3$ case has not moved since the original statement of the problem until now. In Chapter \ref{ch:opp} we give one of the main results of the thesis, which is an improvement of this upper bound to $0.313$. The proof works by strengthening the Delsarte-type bounds using some combinatorial arguments deduced in Chapters \ref{ch:opp-background} and \ref{ch:circular}. The next main result of the thesis answers a natural question about the graphs $G(S^{n-1}, X)$, whose vertex set is $S^{n-1}$ and where two points are joined with an edge if and only if their inner product belongs to the set $X \subset [-1,1]$ of forbidden inner products. These graphs generalize the Witsenhausen graph, and are called \emph{forbidden inner product graphs}. One may ask, Does there exist a measurable independent set of maximum measure? There is a graph $G = G(S^2, X)$ (many, in fact) having no such independent set. In Chapter \ref{ch:circular} we construct for every $\e>0$ an independent set in $G$ having measure at least $1/2 - \e$, but we show that there is no independent set of measure equal to $1/2$. In Chapters \ref{ch:adjacency} and \ref{ch:attainment} we build on the theory of adjacency operators for infinite graphs developed in \cite{bachoc13} to prove that maximum measurable independent sets exist in $G(S^{n-1},X)$ for all $n \geq 3$, and for all sets $X$. As a relatively easy application of the machinery developed here, we also obtain a third result, which is that the supremum of the measures of independent sets in $G(S^{n-1},X)$ depends only on the topological closure of $X$ in $[-1,1]$. In particular, every independent set has measure zero if $1$ belongs to the closure of $X$. Almost everything in this thesis relates to the Lov\'asz $\vartheta$-function of a graph, introduced in \cite{lovasz79}. The Delsarte bounds for binary codes can be regarded as coming from the $\vartheta$-function, and Delsarte's bounds for spherical codes \cite{delsarte77} can be thought of as coming from an extension of the $\vartheta$-function to forbidden inner product graphs on the unit sphere. Approaches inspired by the $\vartheta$-function have been successful in improving lower bounds for the measurable chromatic number of Euclidean space (see for instance \cite{bachoc09}, \cite{oliveira09}, \cite{filho+vallentin:10}, \cite{bachoc14}). In Chapters \ref{ch:pt-functions} to \ref{ch:dense-theta} we develop two extensions of the $\vartheta$-function to (possibly infinite) Cayley graphs over compact groups, which apply respectively to what we call \emph{sparse} and \emph{dense} graphs. Dense Cayley graphs have enough edges to guarantee that their independence numbers are finite, and in this case the applicable $\vartheta$-function gives an upper bound for the cardinality of any independent set. Infinite sparse Cayley graphs have infinite independent sets, and the applicable $\vartheta$-function then gives an upper bound for the Haar measure of any measurable independent set. The extensions we develop are based on the formulations of the $\vartheta$-function for finite Cayley graphs given in \cite{decorte14}. We also show how many of the $\vartheta$-function approaches taken in the literature can be seen as natural examples of our general framework. The $\vartheta$-function for finite graphs has formulations both as maximization and as minimization semidefinite programs which are mutually dual. In the approaches mentioned above in which the $\vartheta$-function is extended to infinite graphs, it is also common to make use of duality, although in the infinite case it had not been shown that the primal and dual problems have equal values, a property known as \emph{strong duality}. In this thesis we prove strong duality for our $\vartheta$-functions using a different approach from the known strong duality proofs in the finite case. The definitions and proofs related to the $\vartheta$-function build on a theory of positive type functions and measures which is developed in Chapters \ref{ch:pt-functions} to \ref{ch:cones}. In \cite{montina11}, Montina gives an application in quantum communication complexity of a natural conjecture about the Witsenhausen problem, the so-called \emph{Double Caps Conjecture}. The extremal example for a spherical set in any dimension avoiding orthogonal pairs of points is conjectured \cite{kalai09} to be the union of two opposite open spherical caps of geodesic radius $\pi/4$. In dimension $3$, this configuration occupies about a $0.293$-fraction of the unit sphere, so our new upper bound of $0.313$ gets roughly halfway from the previous $1/3$ upper bound to the Double Caps Conjecture. Assuming the Double Caps Conjecture, Montina is able to deduce a new lower bound on the cost of classically simulating a quantum channel.