## The Question

Suppose that you want to send a message so that it will reach all vertices of the discrete -dimensional cube. At each time unit (or round) you can send the message to one vertex. When a vertex gets the message at round all its neighbors will receive it at round .

We will denote the vertices of the discrete -cube by vectors of length . The Hamming distance between two such vertices is the number of coordinates they differ and two vertices are neighbors if their Hamming distance equals 1.

The question is

how many rounds it will take to transmit the message to all vertices?

Here is a very simple way to go about it: At round 1 you send the message to vertex (-1,-1,-1,…,-1). At round 2 you send the message to vertex (1,1,…,1). Then you sit and wait. With this strategy it will take rounds.

Test your intuition: Is there a better strategy?

## The Answer: NO

The answer to the question posed in test you intuition (14) is no. There is no better strategy. The question was originated in Intel. It was posed by Joe Brandenburg and David Scott, and popularized by Vance Faber. The answer was proved by Noga Alon in the paper Transmitting in the n-dimensional cube, Discrete Applied Math. 37/38 (1992), 9-11. The result is closely related to combinatorial discrepancy theory and the proof is related to the argument in the Beck-Fiala theorem and a related lemma by Beck and Spencer. This is a good opportunity to present the Beck-Fiala Theorem.

## The general form of a discrepancy problem

Let be a hypergraph, i.e., a collection of subsets of a ground set . is also called the set of vertices of the hypergraphs and the subsets in are also called edges.

The** discrepancy** of , denoted by is the minimum over all functions of the maximum over all of

.

The Erdős Discrepancy Problem (EDP) asks about the following particular hypergraph: The vertices are {1,2,…,n} and the edges are sets of vertices which form arithmetic progressions of the form (r,2r,3r,…kr}. EDP was extensively discussed and studied in polymath5. Here is the link of the first post. Here are links to all polymath5 posts. Here is the link to polymath5 wiki.

## The Beck-Fiala theorem

**Theorem (Beck-Fiala):** If every element in is included in at most edges of then .

Before proving this theorem we mention that it is a famous open conjecture to show that actually

**Proof: Continue reading **