Matching Items (1)
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."
ContributorsOursler, Roy (Author) / Arizona State University (Publisher)
Created2019