On the existence of loose cycle tilings and rainbow cycles

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."