On Spectral Properties of Graph Coloring, Directed Graphs, and Hypergraphs.

摘要

In this thesis, we study the connections between several characteristics of graphs, including directed graphs, and hypergraphs to the spectra of related matrices.;For graphs, we focus on relating the minimal and maximal eigenvalues of the adjacency matrix, μmin and μmax, to graph coloring. In particular, we generalize several classical results: First, a classical result in spectral graph theory says that a graph is bipartite (i.e., 2-colorable) if and only if μmax = μmin. We give a generalization of this theorem for k-colors. Second, a theorem of Hoffman says that χ(G) ≥ 1 – μ max / μmin where χ(G is the chromatic number. We give a new proof of this theorem using a probabilistic technique and adapt this technique to consider several different variants of graph coloring.;For hypergraphs, we use the eigenvalues of the adjacency matrix for the underlying graph to derive necessary conditions for a 3-uniform hypergraph to be 2-colorable. We further extend this result to 4- and 5- uniform graph by considering variants of the underlying graph.;For directed graphs, we consider discrepancy. Loosely speaking, the discrepancy of a graph is the difference between the actual number of edges between two sets and the “expected'' number of edges between them. We establish three new types of discrepancy using a random walk process on the graph, some unique to directed graphs. Using techniques established by Bilu and Linial we show that these three types of discrepancy are tightly bounded, to within a logarithmic factor, of the extremal eigenvalues of various matrices associated with the directed graph.