%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This is mydata.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% You and your thesis
\newcommand{\myname}{Victor O. Larsen}
\newcommand{\mytitle}{An $\epsilon$ improvement to the asymptotic density of $k$-critical graphs}
\newcommand{\mydegree}{M.S. Mathematics, Emory University, 2014}
\newcommand{\mydegreetwo}{B.A. Mathematics, Middlebury College, 2009}
\newcommand{\thisyear}{2015}
\newcommand{\mydepartment}{Mathematics}
%%% can be 'Master of Science' or 'Doctor of Philosophy'
\newcommand{\thisdegree}{Doctor of Philosophy}
%%% type of thesis, can be 'thesis' (for M.S.) or 'dissertation' (for Ph.D.)
\newcommand{\typeofthesis}{dissertation}

% Your committee
\newcommand{\myadvisor}{Ronald Gould, Ph.D.}
\newcommand{\myadvisortwo}{Luke Postle, Ph.D.}
% other committee members should be in alphabetical order
\newcommand{\committeeone}{Dwight Duffus, Ph.D.}
\newcommand{\committeetwo}{Vojt{\v{e}}ch R{\"o}dl, Ph.D.}

%%% Acknowledgments
\newcommand{\myacknowledgments}{
There are a great number of people whose influence, large or small, has shaped not only this thesis but also my mathematical career and educational outlook.  I would like to extend my thanks to each one of these people even though only a small percentage are named below.

I would like to thank all of my past teachers including those who inspired my love of learning and teaching, those who focused my attention on mathematics, and those who have provided me exemplary role models as an educator.  In particular, I appreciate the willingness of John Schmitt, Chuck Dunn, and Skip Garibaldi to serve as mentors long after my role as their student had ended.

I would like to thank my both of my advisors; Ron Gould for his guidance and mentorship, and Luke Postle for his seemingly unending supply of ideas and techniques.  I could not imagine having achieved this much without both of their support, time, and feedback.  The other members of my committee, Dwight Duffus and Vojt\v{e}ch R\"{o}dl, also deserve much appreciation for their time and thoughtful comments.

I am forever grateful to Terry Ingram for all that she has helped me with at Emory.  Life would be endlessly better if every office had a Terry Ingram.

Lastly, and most importantly, I must thank my family.  A double helping of thanks to my mother, who in childhood harnessed my limitless energy into education (and into the math problems she wrote on church bulletins).  My future wife Rachel DeNeui also deserves a double thanks.  Her support (both moral and physical), company, and encouragement were absolutely necessary to bring this momentous project to a close.  
}

%%% Abstract
\newcommand{\myabstract}{
Given a graph $G$ the \emph{chromatic number}, denoted $\chi(G)$, is smallest number of colors necessary to color $V(G)$ such that no adjacent vertices receive the same color.  A graph $G$ is $k$-critical if $\chi(G)=k$ but every proper subgraph has chromatic number less than $k$.
As $k$-critical graphs can be viewed as minimal examples of graphs with chromatic number $k$, it is natural to ask how small such a graph can be.

Let $f_k(n)$ denote the minimum number of edges in a $k$-critical graph on $n$ vertices.  The Ore construction, used to build larger $k$-critical graphs, implies that
\[f_k(n+k-1)\leq f_k(n)+(k-1)\left(\frac{k}{2}-\frac{1}{k-1}\right).\]
A recent paper by Kostochka and Yancey provides a lower bound for $f_k(n)$ which implies that the asymptotic density $\phi_k:=\lim_{n\to\infty}f_k(n)/n = \frac{k}{2}-\frac{1}{k-1}$.

In this work, we use the method of discharging to prove a lower bound on the number of edges which includes structural information about the graph.
This lower bound shows that the asymptotic density of a $k$-critical graph can be increased by $\epsilon>0$ by restricting to $(K_{k-2})$-free $k$-critical graphs.

We also prove that the graphs constructible from the Ore construction and $K_k$, called \emph{$k$-Ore} graphs, are precisely the graphs which attain Kostochka and Yancey's bound.  Moreover, we also provide results regarding subgraphs which must exist in $k$-Ore graphs.
For the discharging argument, carried out in two stages, we also prove results regarding the density of nearly-bipartite subgraphs in $k$-critical graphs.

In the final chapter we examine the minimal set of subgraphs, called \emph{$k$-critical structures}, which one needs to forbid to obtain an $\epsilon$ increase in asymptotic density.
This lays the groundwork for future research into asymptotic density in $k$-critical graphs.
}

% If you want this, uncomment the lines at the end of preamble.tex as well
%%% Dedication
\newcommand{\mydedication}{
to Rachel
}