<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T13:38:48Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/24014" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/24014</identifier><datestamp>2026-08-21T17:38:07Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9928</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author">DeCamillis, Gregory</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2026-08-21T17:38:06Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2026-08-21</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2026-08-17</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/10012/24014</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract">Let $\mathcal T_{n,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 T_{n,m}$?&amp;quot; This question has been answered when $m \le n^{3/2-\eps}$ for some $\eps&amp;gt;0$, or $m \geq \frac{13}{56}n^{3/2}\sqrt{\log n}$. These results depend on the typical structure of graphs in $\mathcal T_{n,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}n^{3/2}\sqrt{\log n}$ is the tight threshold for a graph chosen uniformly at random from $\mathcal T_{n,m}$ to be bipartite.

Another popular topic in random graph theory is the study of random regular graphs. Let $G&amp;apos;$ be random graph chosen uniformly from all $d$-regular graphs on $n$ vertices. Let $X$ be the number of triangles in $G&amp;apos;$. One particular question that has been considered recently is ``what is the distribution of $X$?&amp;apos;&amp;apos; 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 \mu_0 n$ for any $\eps &amp;gt; 0$ and sufficiently small $\mu_0 &amp;gt; 0$ (the restriction of $d\le \mu_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.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject">random graph theory</dim:field>
   <dim:field mdschema="dc" element="subject">regular graphs</dim:field>
   <dim:field mdschema="dc" element="subject">triangle-free graphs</dim:field>
   <dim:field mdschema="dc" element="subject">switching method</dim:field>
   <dim:field mdschema="dc" element="subject">bipartite graphs</dim:field>
   <dim:field mdschema="dc" element="subject">asymptotic enumeration</dim:field>
   <dim:field mdschema="dc" element="title">When are random regular triangle-free graphs bipartite?</dim:field>
   <dim:field mdschema="dc" element="type">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree">Master of Mathematics</dim:field>
   <dim:field mdschema="uws-etd" element="embargo" qualifier="terms">0</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Gao, Pu</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>