Some Avenues in Graph Codes

Abstract

For a family of graphs $\mathcal{H}$, the maximum size of a collection of graphs $\mathcal{F}$ for which the symmetric difference $\oplus$ of two distinct graphs $G_1, G_2$ has the property $G_1 \oplus G_2 \not\in \mathcal{H}$ (or $\in \mathcal{H}$) is denoted by $D_{\mathcal{H}}(n)$ (or $M_{\mathcal{H}}(n)$ respectively).
We also denote the independence ratio by $d_{\mathcal{H}}(n) = D_{\mathcal{H}}(n) / 2^{\binom{n}{2}}$.

This thesis gives a new approach to get an upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain cycles of length $2k$, i.e. $\mathcal{H} = \{H : C_{2k} \subseteq H\}.$
The proof of which is based on a different proof by Noga Alon concerning the upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain stars with $2k$ edges, i.e. $\mathcal{H} = \{H : K_{1,2k} \subseteq H\}.$
A bound on the number of $C_{2k}$-free graphs proven by Morris and Saxton indirectly already solved this problem, but Alon's approach could be expanded upon for different types of graph families for which the upper bound is not yet known.
In this thesis we also perform a spectral analysis of the Cayley graph corresponding to the families $\mathcal{H} = \{H : L \subseteq H\}$ and $\mathcal{H} = \{H : L \cong H\}$, in order to give upper bounds on $D_{\mathcal{H}}(n)$.
These upper bounds are compared to known lower bounds.