## 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: **Consider the following process such that in every step every element of is assigned a real value in the interval [0,1]. At each step of the process some elements in are assigned -1 or +1 and such assignements will not change at later steps. We call such assinements **determined values**. A set is** relevant** at step if it contains more than undetermined values. The crucial property (P) we want to mentain along the process is that at every step the sum of values for every relevant set in is precisely 0.

At the first step we give all elements the value 0.

When we reach a step where all sets S in A become irrelevant we stop. Now if we will define by replacing every undetermined value by either +1 or -1 the sum for every set will be smaller than .

**Lemma**: At each step the number of undetermined values is larger than the number of relevant sets.

**Proof of the lemma: **This follows immediately from the fact that every relevant set contains at least undetermined values while every element in is included in at most edges of .

We return to the proof of the theorem. Suppose that at some step there are relevant sets . We already have a vector of weights such that all weights are in the interval [-1,1] and the sum of weights over every relevant set is 0.

Now, ignore the determined values, assign a variables to every undetermined value and consider the system of equations in which for every relevant set the sum of variables in the set is 0. By the lemma we have more equations than variables. Since the all 0 vector solves our system of equations there is also another nontrivial solution . Consider where is a small positive value. When we gradually increase we reach a new solution with one additional determined value.

## An even more general form of the discrepancy problem

**Question:** Let be subsets of a ground set A={1,2,,,n} and let be integers. Is there a function such that for every

?

In the ordinary combinatorial discrepancy problem we assume all these s are the same.

The following result of Beck and Spencer which addresses a special case of the more general discrepancy problem admits a simple linear algebra proof similar to the proof of the Beck Fiala theorem described above:

**Lemma (Beck-Spencer)**: Let $A=(a_{i,j})$ be an by matrix where each entry is either a 1 or a -1. Then there is a vector of length n with latex \pm 1$ entries, such that for each the scalar product od with the th row of is, in absolute value strictly less than .

Let me simply bring the argument for this lemma and the derivation of the negative answer to the cube transmission problem from Alon’s paper.

**Proof of Beck-Spencer’s lemma**

The negative answer to the cube transmission problem follows from Beck-Spencer lemma as follows:

Fantastic, thanks for sharing! I had previously conjectured that all of your “test your intuition” posts were actually secretly open problems. So much for that conjecture.

The problem came from a real application. An early hypercube multiprocessor machine had to load a given problem and its initial data from a single front end machine that was able to communicate to one single processor at any given time. This makes me wonder about general Cayley graphs. Is there a corresponding theorem for them?

I am not able to reach the link to Alon’s paper.

Thanks Vance! Am I correct to assume that you are the same Faber from the famous Erdos-Faber-Lovasz Conjecture? I will check the link it is from Alon’s homepage.

Pingback: Alantha Newman and Alexandar Nikolov Disprove Beck’s 3-Permutations Conjecture | Combinatorics and more

Pingback: EDP22 — first guest post from Gil Kalai « Gowers's Weblog

Pingback: Looking Again at Erdős’ Discrepancy Problem | Combinatorics and more