Upper bounds for linear graph codes

Abstract

A linear graph code is a family $\mathcal{C}$ of graphs on $n$ vertices with the property that the symmetric difference of the edge sets of any two graphs in $\mathcal{C}$ is also the edge set of a graph in $\mathcal{C}$. In this article, we investigate the maximal size of a linear graph code that does not contain a copy of a fixed graph $H$. In particular, we show that if $H$ has an even number of edges, the size of the code is $O(2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}/\log n)$, making progress on a question of Alon. Furthermore, we show that for almost all graphs $H$ with an even number of edges, there exists ${\epsilon }_H>0$ such that the size of a linear graph code without a copy of $H$ is at most $2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}/n^{{\epsilon }_H}$.

arXiv comment12 pages, fixed typos and changed formulations to match thesis