2023/10/30 by Leo Versteegen, Versteegen, Leo · 2 citations
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Error Correcting Code Techniques #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2310.19891
openalex publication_date 2023/10/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A linear graph code is a family C of graphs on n vertices with the property 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 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^\binomn2/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 εH>0 such that the size of a linear graph code without a copy of H is at most 2^\binomn2/nεH.