Fractional Chromatic Numbers and Spectra of Graphs

<p>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.</p> <p>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.</p> <p>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}$.</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>A natural question is: what are the Laplacian eigenvalues of a random hypergraph? Let H^r(n,p) be a random hypergraph.</p> <p>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$.</p>

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Campus Access Dissertation

Discipline thesis:degree_discipline

Mathematics

Year

2012

Author dc:creator

• Peng, Xing

Contributors dc:contributor

• Lu, Linyuan

• Mathematics
• Physical Sciences and Mathematics
• chromatic number
• edge-independent random graph
• fractional chromatic number
• Generalized Laplacian matrix
• Laplacian matrix

Statement dc:rights

• © 2012, Xing Peng

Repository record dc:identifier

https://scholarcommons.sc.edu/etd/1610

OAI identifier oai:identifier

oai:scholarcommons.sc.edu:etd-2611