Combinatorics Seminar

When: Sunday, November 20, 10am
Where: Schreiber 309
Speaker: Klim Efremenko, Tel Aviv University
Title: Testing Equality in Communication Graphs


Let G=(V,E) be a connected undirected graph with k vertices. Suppose that on each vertex of the graph there is a player having an n-bit string. Each player is allowed to communicate with its neighbors according to a (static) agreed communication protocol and the players must decide, deterministically, if their inputs are all equal. What is the minimum possible total number of bits transmitted in a protocol solving this problem? We determine this minimum up to a lower order additive term in many cases (but not for all graphs). In particular, we show that it is kn/2+o(n) for any Hamiltonian k-vertex graph, and that for any 2-edge connected  graph with m edges containing no two adjacent vertices of degree exceeding 2 it is mn/2+o(n). The proofs combine graph theoretic ideas with tools from additive number theory.

Joint work with Noga Alon and Benny Sudakov.