Graph-codes: questions, results and methods

Noga Alon

Abstract: This paper is a presentation of the content of the Takagi Lectures delivered by the author in Tokyo in 2025. The topic discussed is Graph-Codes, a subject motivated by questions in Extremal Combinatorics, Additive Number Theory and Coding Theory. The initial guiding fact is that viewing binary vectors as characteristic vectors of edge-sets of graphs transforms the basic combinatorial questions of Coding Theory into intriguing extremal problems about families of graphs. We discuss some of these questions and describe several results and open problems. The relevant methods combine Combinatorial and Probabilistic tools with techniques from Information Theory, Number Theory and the theory of Combinatorial Designs.