On the existence of loose cycle tilings and rainbow cycles
Description
Extremal graph theory results often provide minimum degree
conditions which guarantee a copy of one graph exists within
another. A perfect $F$-tiling of a graph $G$ is a collection
$\mathcal{F}$ of subgraphs of $G$ such that every element of
$\mathcal{F}$ is isomorphic to $F$ and such that every vertex in $G$
is in exactly one element of $\mathcal{F}$. Let $C^{3}_{t}$ denote
the loose cycle on $t = 2s$ vertices, the $3$-uniform hypergraph
obtained by replacing the edges $e = \{u, v\}$ of a graph cycle $C$
on $s$ vertices with edge triples $\{u, x_e, v\}$, where $x_e$ is
uniquely assigned to $e$. This dissertation proves for even
$t \geq 6$, that any sufficiently large $3$-uniform hypergraph $H$
on $n \in t \mathbb{Z}$ vertices with minimum $1$-degree
$\delta^1(H) \geq {n - 1 \choose 2} - {\Bsize \choose 2} + c(t,n) +
1$, where $c(t,n) \in \{0, 1, 3\}$, contains a perfect
$C^{3}_{t}$-tiling. The result is tight, generalizing previous
results on $C^3_4$ by Han and Zhao. For an edge colored graph $G$,
let the minimum color degree $\delta^c(G)$ be the minimum number of
distinctly colored edges incident to a vertex. Call $G$ rainbow if
every edge has a unique color. For $\ell \geq 5$, this dissertation
proves that any sufficiently large edge colored graph $G$ on $n$
vertices with $\delta^c(G) \geq \frac{n + 1}{2}$ contains a rainbow
cycle on $\ell$ vertices. The result is tight for odd $\ell$ and
extends previous results for $\ell = 3$. In addition, for even
$\ell \geq 4$, this dissertation proves that any sufficiently large
edge colored graph $G$ on $n$ vertices with
$\delta^c(G) \geq \frac{n + c(\ell)}{3}$, where
$c(\ell) \in \{5, 7\}$, contains a rainbow cycle on $\ell$
vertices. The result is tight when $6 \nmid \ell$. As a related
result, this dissertation proves for all $\ell \geq 4$, that any
sufficiently large oriented graph $D$ on $n$ vertices with
$\delta^+(D) \geq \frac{n + 1}{3}$ contains a directed cycle on
$\ell$ vertices. This partially generalizes a result by Kelly,
K\uhn" and Osthus that uses minimum semidegree rather than minimum
out degree."
conditions which guarantee a copy of one graph exists within
another. A perfect $F$-tiling of a graph $G$ is a collection
$\mathcal{F}$ of subgraphs of $G$ such that every element of
$\mathcal{F}$ is isomorphic to $F$ and such that every vertex in $G$
is in exactly one element of $\mathcal{F}$. Let $C^{3}_{t}$ denote
the loose cycle on $t = 2s$ vertices, the $3$-uniform hypergraph
obtained by replacing the edges $e = \{u, v\}$ of a graph cycle $C$
on $s$ vertices with edge triples $\{u, x_e, v\}$, where $x_e$ is
uniquely assigned to $e$. This dissertation proves for even
$t \geq 6$, that any sufficiently large $3$-uniform hypergraph $H$
on $n \in t \mathbb{Z}$ vertices with minimum $1$-degree
$\delta^1(H) \geq {n - 1 \choose 2} - {\Bsize \choose 2} + c(t,n) +
1$, where $c(t,n) \in \{0, 1, 3\}$, contains a perfect
$C^{3}_{t}$-tiling. The result is tight, generalizing previous
results on $C^3_4$ by Han and Zhao. For an edge colored graph $G$,
let the minimum color degree $\delta^c(G)$ be the minimum number of
distinctly colored edges incident to a vertex. Call $G$ rainbow if
every edge has a unique color. For $\ell \geq 5$, this dissertation
proves that any sufficiently large edge colored graph $G$ on $n$
vertices with $\delta^c(G) \geq \frac{n + 1}{2}$ contains a rainbow
cycle on $\ell$ vertices. The result is tight for odd $\ell$ and
extends previous results for $\ell = 3$. In addition, for even
$\ell \geq 4$, this dissertation proves that any sufficiently large
edge colored graph $G$ on $n$ vertices with
$\delta^c(G) \geq \frac{n + c(\ell)}{3}$, where
$c(\ell) \in \{5, 7\}$, contains a rainbow cycle on $\ell$
vertices. The result is tight when $6 \nmid \ell$. As a related
result, this dissertation proves for all $\ell \geq 4$, that any
sufficiently large oriented graph $D$ on $n$ vertices with
$\delta^+(D) \geq \frac{n + 1}{3}$ contains a directed cycle on
$\ell$ vertices. This partially generalizes a result by Kelly,
K\uhn" and Osthus that uses minimum semidegree rather than minimum
out degree."
Date Created
The date the item was original created (prior to any relationship with the ASU Digital Repositories.)
2019
Agent
- Author (aut): Oursler, Roy
- Publisher (pbl): Arizona State University