Back to search

University of Waterloo

When are random regular triangle-free graphs bipartite?

Abstract

dc:description.abstract

Let \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 × 6

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/24014

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

DeCamillis, Gregory. When are random regular triangle-free graphs bipartite?. University of Waterloo, 2026. https://hdl.handle.net/10012/24014