Forbidding Monchromatic and Rainbow Cycles and Families of Cycles

Abstract

In this dissertation, we avoid certain cycles and families of cycles in complete graphs. Introduced by Axenovich and Choi \cite{2011NoteMonotonicity}, the mixed Ramsey spectrum, $\mrs{F}{H}$, is the set of numbers $k$ such that for some $k$-edge coloring of $K_{n}$ there is neither a monochromatic copy of $F\subseteq K_{n}$ nor a rainbow copy of $H\subseteq K_{n}$.

The values for the following spectrums are shown. Let $m$ and $n$ be an integers. For $n>1$, $\mrs{K_3}{K_3}$=$\left\{ g\left(n\right),\dots,n-1\right\} $, in which $g\left(n\right)\in\left\{ \left\lceil 2\log_{5}n\right\rceil ,\left\lceil 2\log_{5}n\right\rceil +1\right\}$. For all $m$ and $n$, where $3\leq m\leq n$, $\left\{ n+2-m,\dots,n+1-m+\binom{m-1}{2}\right\} \subseteq \mrs{C_m}{C_m}$. For $n\geq4$, $\max\mrs{C_4}{C_4}=n$. Note: $\max\mrs{C_4}{C_4}=n$ was a result shown by Axenovich and Choi \cite{2010AvichChoifixedmonosubgraphs}, we provide an alternate proof.

We extended the definition of the mixed Ramsey spectrum from graphs to families of graphs. For families of graphs $\mathcal{F},\mathcal{H}$, $\mrs{ \mathcal{F} }{ \mathcal{H} }$ is the set of numbers $k$ such that for some $k$-edge coloring of $K_{n}$, there is no monochromatic copy of any $F\subseteq\mathcal{F}$ in $K_{n}$ nor any rainbow copy of any $H\subseteq\mathcal{H}$ in $K_{n}$. It is shown that for all $n\geq2$, \\$\mrs{\left\lbrace \text{odd cycles}\right\rbrace }{\left\lbrace \text{cycles}\right\rbrace }$$=\left\{ \left\lceil \log_{2}n\right\rceil ,\dots,n-1\right\}$.