Title: Odd-Ramsey numbers of complete bipartite graphs
| Speaker: | Thomas Lesgourgues |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: In his study of graph codes, Alon introduced the concept of the odd-Ramsey number of a family of graphs ℋ, defined as the minimum number of colours needed to colour the edges of the complete graph so that every copy of a graph H in ℋ intersects some colour class by an odd number of edges. In recent joint work with Simona Boyadzhiyska, Shagnik Das, and Kaline Petrova, we focus on the odd-Ramsey numbers of complete bipartite graphs. First, using polynomial methods, we completely resolve the problem when ℋ is the family of all spanning complete bipartite graphs on n vertices. We then focus on its subfamilies. In this case, we establish an equivalence between the odd-Ramsey problem and a well-known problem from coding theory, asking for the maximum dimension of a linear binary code avoiding codewords of given weights. We then use known results from coding theory to deduce asymptotically tight bounds in our setting. We conclude with bounds for the odd-Ramsey numbers of fixed (that is, non-spanning) complete bipartite subgraphs.