Leo Versteegen

Linear graph codes

A linear graph code is a family C of graphs on n vertices such that the symmetric difference of the edge sets of any two graphs in C is also the edge set of a graph in C. In the talk, we will investigate the maximal size of a graph code that does not contain a copy of a fixed graph H. There are graphs H that are not contained in linear codes of size 2^{\binom{n}{2}}/exp(sqrt(log n)), but we will show that for almost all graphs H with an even number of edges, there exists epsilon_H>0 such that a linear graph code without copy of H can contain at most 2^{\binom{n}{2}}/n^{\epsilon_H} graphs.