Discrepancy, The Beck-Fiala Theorem, and the Answer to "Test Your Intuition (14)"

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:

About these ads