Abstract
dc:description.abstractLet \mathcal Tn,m denote the set of triangle-free graphs on $n$ vertices with $m$ edges where $m = m(n)$. A natural and well-studied question in random graph theory is ``for large $n$, how large is \mathcal Tn,m?" This question has been answered when m \le n3/2-\eps for some $\eps>0$, or m \geq \frac{13}{56}n3/2\sqrt{\log n}. These results depend on the typical structure of graphs in \mathcal Tn,m, where in the sparse regime these graphs are unstructured and in the dense regime these graphs are rigidly structured. One such result is that m = \frac{\sqrt 3}{4}n3/2\sqrt{\log n} is the tight threshold for a graph chosen uniformly at random from \mathcal Tn,m to be bipartite. Another popular topic in random graph theory is the study of random regular graphs. Let $G'$ be random graph chosen uniformly from all $d$-regular graphs on $n$ vertices. Let $X$ be the number of triangles in $G'$. One particular question that has been considered recently is ``what is the distribution of $X$?'' The answer to this question is well understood when $X$ is near its mean for certain values of $d$, but is not well understood in the lower or upper tail of the distribution; in particular, when $X=0$. In this thesis, we establish that $d = \frac{\sqrt 3}{2} \sqrt{n\log n}$ is the sharp threshold for random $d$-regular triangle-free graphs being bipartite, which implies an asymptotic enumeration of $d$-regular triangle-free graphs when (1 + \eps)\frac{\sqrt 3}{2}\sqrt{n \log n} \leq d \leq μ0 n for any $\eps > 0$ and sufficiently small μ0 > 0 (the restriction of d\le μ0 n is due to some technical considerations). This extends the enumeration of triangle-free graphs to the regular setting and broadens our understanding of the extreme lower tail of the distribution of the number of triangles in a random regular graph.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- DeCamillis, Gregory
Subjects
dc:subject × 6Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/10012/24014