Date of Award

1-1-2012

Document Type

Campus Access Dissertation

Department

Mathematics

First Advisor

Lu, Linyuan

Abstract

This dissertation mainly comes from my recent study of fractional chromatic numbers of graphs, spectra of edge-independent random graphs, Laplacian spectra of hypergraphs, and loose Laplacian spectra of random hypergraphs.

For a graph $G$, let $\chi_f(G)$ be the fractional chromatic number of $G$. Based on the study of independence numbers of triangle-free graphs with maximum degree at most three, Heckman and Thomas conjectured that $\chi_f(G) \leq 3-\frac{1}{5}$ if $G$ is triangle-free and has maximum degree at most three. Since the fractional chromatic number of the generalized Peterson graph $P(7,2)$ is $3-\frac{1}{5}$, the conjecture is tight if it is true.

The first result on this conjecture is due to Hatami and Zhu who proved $\chi_f(G) \leq 3-\frac{3}{64}$. We prove $\chi_f(G) \leq 3-\frac{3}{43}$. We also consider the following general question. What is the fractional chromatic number of a $K_{\Delta}$-free graph with maximum degree $\Delta $ for $\Delta \geq 3$? Heckman and Thomas' conjecture is a special case of this question for $\Delta=3$. We are able to prove that except for two graphs, the fractional chromatic number of each $K_{\Delta}$-free graph with maximum degree $\Delta$ is at most $\Delta-\frac{2}{67}$.

There are a lot of literature addressing the spectra of random graphs. Recently, a new random graph model (edge-independent random graphs) attracted more and more attention.

Let $A(G)$ and $L(G)$ be the adjacency matrix and the Laplacian matrix of an edge-independent graph $G$. Oliveira and Chung-Radcliffe showed eigenvalues of $A(G)$ (and $L(G)$) can be approximated by those of the ``expectation'' of $A$ (and the ``expectation'' of $L$) with some error term involving the maximum expected degree (and the minimum expected degree) and the number of vertices. We improve previous results by removing the $\sqrt{\ln n}$-factor from the error terms with a slightly stronger condition.

Laplacians of graphs are studied extensively in the literature. There are some attempts to investigate the Laplacian matrices of hypergraphs. For an $r$-uniform hypergraph $H$, we will define the $s$-th Laplacian matrix $L^{(s)}(H)$ for each $1 \leq s \leq r-1$; we will also show some applications of Laplacians of hypergraphs.

A natural question is: what are the Laplacian eigenvalues of a random hypergraph? Let $H^r(n,p)$ be a random hypergraph.

For each $1 \leq s \leq r/2$, we prove that the eigenvalues of the $s$-th Laplacian $L^{(s)}(H^{r}(n,p))$ can be approximated by those of the complete hypergraph. Moreover, we show the distribution of eigenvalues of $L^{(s)}(H^r(n,p))$ satisfies the Semicircle Law for $1 \leq s \leq r/2$.

Rights

© 2012, Xing Peng

Download

Share

COinS