The thesis describes new results for several problems in random graph theory.
The first problem relates to the uniform random graph model in
the supercritical phase; i.e. a graph, uniformly distributed, on $n$ vertices
and $M=n/2+s$ edges for $s=s(n)$ satisfying
$n^{2/3}=o(s)$ and $s=o(n)$. The property studied is the length of the
longest cycle in the graph. We give a new upper bound, which holds
asymptotically almost surely, on this length.
As part of our proof we establish a result about the heaviest cycle in a certain
randomly-edge-weighted nearly-3-regular graph, which may be of independent interest.
Our second result is a new contiguity result for a random $d$-regular
graph. Let $j=j(n)$ be a function that is linear in $n$.
A $(d,d-1)$-irregular graph is a graph which is $d$-regular except for $2j$
vertices of
degree $d-1$. A $j$-edge matching in a graph is a set of $j$ independent edges.
In this thesis we prove the new result that a random
$(d,d-1)$-irregular graph plus a random $j$-edge matching is contiguous to a random
$d$-regular graph, in the sense that
in the two spaces,
the same events have probability approaching 1 as $n\to\infty$.
This allows one to deduce properties, such as colourability,
of the random irregular graph from
the corresponding properties of the random regular one. The proof
applies the small subgraph conditioning method to the number of $j$-edge matchings
in a random $d$-regular graph.
The third problem is about the 3-colourability of
a random 5-regular graph. Call a colouring balanced
if the number of vertices of each colour
is equal, and locally rainbow if every vertex is adjacent to vertices
of all the other
colours. Using the small subgraph conditioning method, we give a
condition on the variance of the number of locally rainbow balanced 3-colourings which, if
satisfied, establishes that the chromatic number of the random 5-regular graph is
asymptotically almost surely equal to 3.
We also describe related work which provides evidence that the condition is
likely to be true.
The fourth problem is about the chromatic number of a random $d$-regular
graph for fixed $d$.
Achlioptas and Moore recently announced a proof that a random $d$-regular
graph asymptotically almost surely has chromatic number $k-1$, $k$, or $k+1$,
where $k$ is the smallest integer satisfying $d < 2(k-1)\log(k-1)$. In
this thesis we prove that, asymptotically almost surely, it is not $k+1$,
provided a certain second moment condition holds.
The proof applies the small subgraph conditioning method to
the number of balanced $k$-colourings, where a colouring is balanced
if the number of vertices of each colour is equal.
We also give evidence that suggests that the required
second moment condition is true.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/4006 |
| Date | January 2008 |
| Creators | Kemkes, Graeme |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0019 seconds