Revision #1 Authors: Noga Alon, Klim Efremenko, Benny Sudakov

Accepted on: 3rd June 2016 12:37

Downloads: 230

Keywords:

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 an 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.

TR16-086 Authors: Noga Alon, Klim Efremenko, Benny Sudakov

Publication: 29th May 2016 17:33

Downloads: 313

Keywords:

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 an 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.