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 n-dimensional cube. At each time unit (or round) you can send the message to one vertex. When a vertex gets the message at round i all its neighbors will receive it at round i+1.

We will denote the vertices of the discrete n-cube by \pm 1 vectors of length n. The Hamming distance d(x,y) 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 \lceil n/2\rceil+1 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 H be a hypergraph, i.e., a collection of subsets of a ground set A. A is also called the set of vertices of the hypergraphs and the subsets in H are also called edges.

The discrepancy of H, denoted by disc(H)  is the minimum over all functions f:A \to \{-1,1\} of the maximum over all  S \in H of

\sum \{f(s):s\in S\}.  

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 A is included in at most t edges  of  H then disc(H)<2t.

Before proving this theorem we mention that it is a famous open conjecture to show that actually disc(H)=O(\sqrt t)

Proof: Consider the following process such that in every step every element i of A is assigned a real value in the interval [0,1]. At each step j of the process some elements in A are assigned -1 or +1 and such assignements will not change at later steps. We call such \pm 1 assinements determined values. A set A \in H is relevant at step j if it contains more than t 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 H 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 f by replacing every undetermined value by either +1 or -1 the  sum for every set A will be smaller than 2t.

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 t+1 undetermined values while every element in A is included in at most t edges of H

We return to the proof of the theorem. Suppose that at some step there are relevant sets S \in H.  We already have a vector of weights (z_1,z_2,\dots,z_n) 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 A 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 (y_1,y_2,\dots,y_n). Consider u=z+\delta y where \delta is a small positive value.  When we gradually increase \delta we reach a new solution with one additional determined value.

An even more general form of the discrepancy problem

Question: Let S_1,S_2,\dots,S_m be subsets of a ground set A={1,2,,,n} and let a_1,a_2,\dots,a_m be integers. Is there a function f:A\to \{-1,1\} such that for every i

|\sum \{f(s): s \in S_i\}|\le a_i?

In the ordinary combinatorial discrepancy problem we assume all these a_is 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 n by n matrix where each entry is either a 1 or a -1. Then there is a vector y of length n with latex \pm 1$ entries, such that for each i the scalar product od y with the ith row of A is, in absolute value strictly less than 2i.

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

6 thoughts on “Discrepancy, The Beck-Fiala Theorem, and the Answer to “Test Your Intuition (14)”

  1. daveagp

    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.

  2. Vance Faber

    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.

    1. Gil Kalai Post author

      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.

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

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s