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$.
","abstract_html":"<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 \\chif(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 \\chif(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 \\chif(G) \\leq 3-\\frac{3}{64}. We prove \\chif(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 Hr(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)(Hr(n,p)) can be approximated by those of the complete hypergraph. Moreover, we show the distribution of eigenvalues of L(s)(Hr(n,p)) satisfies the Semicircle Law for $1 \\leq s \\leq r/2$.</p>","abstract_has_math":true,"creators":["Peng, Xing"],"institution":null,"degree_name":"Ph.D.","degree_level":"Campus Access Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Lu, Linyuan"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-01-01T08:00:00Z","date_published":"2012-01-01T08:00:00Z","updated_at":"2026-07-24T04:38:14Z","subjects":["Mathematics","Physical Sciences and Mathematics","chromatic number","edge-independent random graph","fractional chromatic number","Generalized Laplacian matrix","Laplacian matrix"],"languages":[],"rights":["© 2012, Xing Peng"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://scholarcommons.sc.edu/etd/1610","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Lu, Linyuan"]},{"key":"dc:creator","label":"Author","values":["Peng, Xing"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Campus Access Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Physical Sciences and Mathematics","chromatic number","edge-independent random graph","fractional chromatic number","Generalized Laplacian matrix","Laplacian matrix"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["© 2012, Xing Peng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://scholarcommons.sc.edu/etd/1610"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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$.
"]},{"key":"dc:title","label":"Title","values":["Fractional Chromatic Numbers and Spectra of Graphs"]}]}],"canonical_facts":{"dc:contributor":["Lu, Linyuan"],"dc:creator":["Peng, Xing"],"dc:description.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$.
"],"dc:identifier":["https://scholarcommons.sc.edu/etd/1610"],"dc:rights":["© 2012, Xing Peng"],"dc:subject":["Mathematics","Physical Sciences and Mathematics","chromatic number","edge-independent random graph","fractional chromatic number","Generalized Laplacian matrix","Laplacian matrix"],"dc:title":["Fractional Chromatic Numbers and Spectra of Graphs"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Campus Access Dissertation"],"thesis:degree_name":["Ph.D."]},"updated_at":"2026-07-24T04:38:14Z"}