### Linear graph codes

Combinatorics Seminar

7th November 2023, 11:00 am – 12:00 pm

Fry Building, 2.04

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.

## Comments are closed.