Celebrations in Sweden and Norway

Celebrations for Endre, Jean and Terry

Anders Bjorner presents the 2012 Crafoord Prize in Mathematics 

I am in Sweden for two weeks to work with colleagues and to take part in two celebrations. Jean Bourgain and Terence Tao are the 2012 laureates of the Crafoord Prize in mathematics which was awarded  last Tuesday at Lund. Along with them the 2012 Crafoord Prize in Astronomy was awarded to Reinhand Genzel and Andrea Ghez.  I took part in the symposium entitled “From chaos to harmony” to celebrate the event.

Next Friday the Swedish Royal academy will celebrate with a mini-symposium in honor of the 2012 Abel prize winner Endre Szeméredi. (Here are the slides of my future talk looking at and around the Szeméredi-Trotter theorem. Please alert me of mistakes if you see them.) The Abel prize symposium and ceremony in Oslo are  Tuesday (Today! see the picture above) and Wednesday of this week.

(Copyright: Crafoord foundation.)

Congratulations again to Jean, Terry and Endre for richly deserved awards.

Crafoord days at Lund

Owing to the passing of Count Carl Johan Bernadotte af Wisborg, H.M. King Carl XVI Gustaf was unable to attend the Crafoord Days 2012. The prizes were presented by Margareta Nilsson, daughter of the Donors, Holge and Anna-Greta Crafoord. Ms Nilsson’s kind hospitality, deep devotion to science, culture and other noble social causes, and moving childhood memories shared at the dinner,  have led Reinhard Genzel in his moving speech on behalf of the winners in Astronomy to refer to Margareta Nilsson by the words: “You were our King these past two days!”.

The one day symposium itself was very interesting, and so were the four prize lectures on Tuesday morning. In a few days The videos of the two days’ lectures will be are posted here. Here are the slides of my talk on analysis of Boolean functions, featuring, among other things a far-reaching conjectural extension of a recent theorem by Hamed Hatami.

Gothenburg and Stockholm

From Lund I continued to a short visit of Gothenburg hosted by Jeff Steif with whom I share much interest in noise sensitivity and many other things. I then continued to Stockholm where I visit Anders Björner who is a long-time collaborator and friend since the mid eighties. For me this is perhaps the twelfth visit to Stockholm and it is always great to be here.

We will celebrate on this blog these exciting events with a rerun of the classic, much-acclaimed piece by Christine Björner on the Golden room and the golden mountain.

Speakers at Crafoord symposium, (from right to left) Carlos Kenig, Ben Green, Jean Bourgain, Terry Tao, me and Michael Christ. Copyright: Crafoord foundation.


Update(Oct 2014): Here is a picture of me and  Jean at IHES 1988


Galvin’s Proof of Dinitz’s Conjecture

Dinitz’ conjecture

The following theorem was conjectured by Jeff Dinitz in 1979 and proved by Fred Galvin in 1994:

Theorem: Consider an n by n square table such that in each cell (i,j) you have a set A_{i,j} with n or more elements. Then it is possible to choose elements a_{ij} from A_{ij} such that the chosen elements in every row and in every colummn are distinct.

Special case: if all A_{ij} are the same set, say {1,2,…,n} then this is possible. Such a choice is called a Latin square for example a_{ij}=i+j({\rm mod} n).

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

Here are a few remarks before we go ahead with Galvin’s proof:

1) The Theorem is about graph-coloring from  lists of colors, or briefly list-coloring. Given a graph G with n vertices and a list of colors A_i for vertex i we ask for a proper coloring of the graph such that vertex i is colored by an element of A_i. (A proper coloring is a coloring such that two djacent vertices have different colors.)

The list chromatic number of a graph G is the smallest number k such that G can be colored from any lists of colors, where every A_i has k elements.

2) We consider the graph G whose vertices are the pairs (i,j) and two vertices are adgacent if one of their coordinates agree. This graph is the line graph of the complete bipartite graph K_{n,n}. The line graph L(H) of a graph H is the graph whose vertices correspond to the edges of H and two vertices are adjacent if the corresponding edges share a vertex.

3) Vizing proved that the chromatic number of the line graph L(H) is at most one more than the maximum degree of H. He conjectured that this is also true for list coloring. A bolder version asserts that for every line-graph G the list chromatic number equals the chromatic number. Dinits’s conjecture is the special case (of the bolder version) where G is the line graph of the complete bipartite graph K_{n,n}. The proof demonstrates Vizing’s conjecture for the line graph of every bipartite graph.

4) Shortly before Galvin, Jeannette Janssen gave an amazing proof for a slightly weaker statement where in each square you allow n+1 colors.  (She proved the Dinitz conjecture for rectangular arrays.) Janssen applied  a theorem of Alon and Tarsi, who used the “polynomial method” to obtain a powerful necessary condition for list coloring.

5) Here are now (or when I will be able to find them later) links to Galvin’s paper, to Janssen’s paper, to Alon-Tarsi’s paper,  to expositions by Barry Cipra and by Doron Zeilberger and to a short self-contained version of the proof by Tomaž Slivnik.

Galvin’s proof

Galvin’s ingenious proof of Dinitz’ the conjecture combines two known theorems which are quite easy themselves.

For a directed graph G an induced subgraph is a subgraph spanned by a subset of the set of vertices of G. A kernel in a directed graph is an independent and absorbant set of vertices. I.e., it is a set of vertices W such that there is no edge between any two vertices in W, and from every vertex not in W there is an edge directed from it to a vertex in W.

Lemma 1 (Bondy, Boppana, Siegal): (mentioned e.g. in the paper by Alon and Tarsi)

Continue reading

Fractional Sylvester-Gallai

Avi Wigderson was in town and gave a beautiful talk about an extension of Sylvester-Gallai theorem. Here is a link to the paper: Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes by Boaz Barak, Zeev Dvir, Avi Wigderson, and Amir Yehudayoff.


The Sylvester-Gallai Theorem:  Let X be a finite set of n points in an eulidean space such that for every two distinct points x,y \in X the line through x and y contains a third point z \in X. Then all points in X are contained in a line. 

I heard about this result when I took Benjy Weiss’s mathematics course for high-school students in 1970/1. a  The Sylvester-Gallai theorem was the last question marked with (*) in the first week’s homework. In one of the next meetings Benjy listened carefully to our ideas on how to prove it and then explained to us why our attempts of proving it are doomed to fail: What we tried to do only relied on the very basic incidence axioms of Euclidean geometry but the Sylvester-Gallai theorem does not hold for finite projective planes. (Sylvester conjectured the result in 1893. The first proof was given by Mechior in 1940 and Gallai proved it in 1945.)

My MO question

Befor describing the new results let me mention my third ever MathOverflow question that was about potential extensions of the G-S theorem. The question was roughly this:

Suppose that V is an r dimensional variety embedded into n space so that if the intersection of every j-dimensional subspace with V is full dimensional then this intersection  is “complicated”. Then n cannot be too large.

I will not reproduce the full question here but only a memorable remark made by Greg Kuperberg:

If you claimed that Gil is short for Gilvester (which is a real first name although rare), then you could say that any of your results is the “Gilvester Kalai theorem”. – Greg Kuperberg Nov 24 2009 at 5:13

The result by Barak, Dvir, Wigderson and Yehudayoff

Theorem:  Let X be a finite set of n points in an Euclidean space such that for every point x \in X the number of y, y\in X,y \ne x such that the line through x and y contains another point of X is at least \delta (n-1). Then

\dim (Aff(X))\le 13/\delta^2

Some remarks:

1) The proof: The first ingredient of the proof is a translation of the theorem into a question about ranks of matrices with a certain combinatorial structure. The next thing is to observe is that when the non zero entries of the matrix are 1’s the claim is simple. The second surprising ingredient of the proof is to use scaling in order to “tame” the entries of the matrix.

2)  The context – locally correctable codes:  A q-query locally correctable (q,\delta)-code over a field F is a subspace of F^n so that, given any element \tilde y that disagrees with some y \in C in at most \delta n positions and an index i, 1 \le i \le n we can recover y_i with probability 3/4 by reading at most q coordinates of \tilde y.  The theorem stated above imply that, for two queries,  over the real numbers (and also over the complex numbers), such codes do not exist when n is large. Another context where the result is of interest is the hot area of sum product theorems and related questions in the geometry of incidences.

3) Some open problems: Is there a more detailed structure theorem for configurations of points satisfying the condition of the theorem? Can the result be improved to \dim (Aff(X))=O(1/\delta )? Can a similar result be proved on locally correctable codes with more than two queries? This also translates into an interesting Sylvester-Gallai type question but it will require, Avi said, new ideas.

Ryan O’Donnell: Analysis of Boolean Function

Ryan O’Donnell has begun writing a book about Fourier analysis of Boolean functions and  he serializes it on a blog entiled Analysis of Boolean Function.  New sections appear on Mondays, Wednesdays, and Fridays.

Besides covering the basic theory, Ryan intends to describe applications in theoretical computer science and other areas of mathematics, including combinatorics, probability, social choice, and geometry.

Beside being a great place to learn this interesting material, actively participating in Ryan’s blog can make you a hero! Don’t miss this opportunity.

Each chapter of Ryan’s book ends with a “highlight” illustrating the use of Boolean analysis in problems where you might not necessarily expect it. In a post over Computational Complexity Ryan described some of these highlights in order to give a flavor of the contents:

  • Testing linearity (the Blum-Luby-Rubinfeld Theorem)
  • Arrow’s Theorem from Social Choice (and Kalai’s “approximate” version)
  • The Goldreich-Levin Algorithm from cryptography
  • Constant-depth circuits (Linial-Mansour-Nisan’s work)
  • Noise sensitivity of threshold functions (Peres’s Theorem)
  • Pseudorandomness for F_2-polynomials (Viola’s Theorem)
  • NP-hardness of approximately solving linear systems (Hastad’s Theorem)
  • Randomized query complexity of monotone graph properties
  • The (almost-)Polynomial Freiman-Ruzsa Theorem (i.e., Sanders’s Theorem)
  • The Kahn-Kalai-Linial Theorem on influences
  • The Gaussian Isoperimetric Inequality (Bobkov’s proof)
  • Sharp threshold phenomena (Friedgut and Bourgain’s theorems)
  • Majority Is Stablest Theorem
  • Unique Games-hardness from SDP gaps (work of Raghavendra and others)

Cup Sets, Sunflowers, and Matrix Multiplication

This post follows a recent paper On sunflowers  and matrix multiplication by Noga Alon, Amir Spilka, and Christopher Umens (ASU11) which rely on an earlier paper Group-theoretic algorithms for matrix multiplication, by Henry Cohn, Robert Kleinberg, Balasz Szegedy, and Christopher Umans (CKSU05), and refers also to a paper by Don Coppersmith and Shmuel Winograd (CW90).

Three famous problems

The Erdos-Rado sunflower conjecture

The Erdos-Rado sunflower (Delta system) theorem and conjecture was already menioned in this post on extremal set theory.

A sunflower (a.k.a. Delta-system) of size r is a family of sets A_1, A_2, \dots, A_r such that every element that belongs to more than oneofthe sets belongs to all of them. A basic and simple result of Erdos and Rado asserts that

Erdos-Rado sunflower theorem: There is a function f(k,r) so that every family \cal F of k-sets with more than f(k,r) members contains a sunflower of size r.

One of the most famous open problems in extremal combinatorics is:

The Erdos-Rado conjecture: Prove that f(k,r) \le c_r^k.

Here, c_r is a constant depending on r. This is most interesting already for r=3.

Three term arithmetic progressions

The cup set problem (three terms arithmetic progressions in (Z/3Z)^n):

The cup set problem was also discussed here quite extensively. (See, e.g. this post.)

Let \Gamma=\{0,1,2\}^n. The cap set problem  asks for the maximum number of elements in a subset of \Gamma which contains no arithmetic progression of size three or, alternatively, no three vectors that sum up to 0(modulo 3). (Such a set is called a cup set.) If A is a cap set of maximum size we can ask how the function h(n)=3^n/|A| behaves. Roy Meshulam proved, using Roth’s argument, that h(n) \ge n. Edell found an example of a cap set of size 2.2^n. So h(n) \le (3/2.2)^n.  The gap is exponential.

The strong cap set conjecture: h(n) \ge (1+\epsilon)^n for some \epsilon >0.

Of course, the cap set problem is closely related to

Erdos-Turan problem (for r=3): What is the larget size r_3(n) of a subest of {1,2,…,n} without 3-term arithmetic progression?

Matrix multiplications

Let ω be the smallest real number so that there is an algorithm for multiplying  two n \times n matrices which requires O(n^\omega ) arithmetic operations.

The ω=2 conjecture: ω=2.

A very recent breakthrough by Virginia Vassilevska Williams (independently) following an earlier breakthrough by Andrew Stothers improved the Coppersmith-Winograd algorithm which gave ω =2.376, to 2.374 and 2.373 respectively. (See the discussions over Lipton’s blog (1,2), Shtetl optimized, and Computational Complexity.)

It turns out that these three conjectures are related. (The connection of matrix multiplication and the Erdos-Turan problem is fairly old, but I am not sure what an even drastic improvment of Behrends’s lower bound would say about \omega.)

Three combinatorial conjectures that imply ω=2.

Remarkably, an affarmative answer for the ω=2 conjecture would folow from each one of three combinatorial conjectures. One conjecture goes back to CW90 and two were described in CKSU05. I will not present the precise formulations in order to encourage the readers to look at the original papers. (Maybe I will add the formulations later.)

The no disjoint equivoluminous subsets conjecture (CW90).

The Strong UPS conjecture (CKSU05).

Theorem: Conjecture CW90 implies the strong UPS conjecture.

CKSU’s two-family conjecture (CKSU05).

Relations between these problems

Here are some results taken from ASU11 about the relations between these combinatorial questions. The first result goes back to Erdos and Szemeredi.

The weak sunflower conjecture: A family \cal F of subsets of {1,2,…,n}  with no sunflower of size 3 can have at most (2-\epsilon)^n sets.

The following results are not difficult.

Theorem: The strong sunflower conjecture implies the weak sunflower conjecture.

Theorem: The strong cup set conjecture also implies the weak sunflower conjecture.

Theorem: The weak sunflower conjecture implies that the CW90 conjecture is false.

It follows that CW90 conjecture is in conflict both with the Erdos Rado sunflower conjecture and with the strong cup set conjecture.

Theorem: The strong cup set conjecture implies that the strong UPS conjecture is false.

While two family theorems are quite popular in extremal combinatorics (see this post and this one), CKSU’s two family conjecture is still rather isolated from other combinatorics.

What to believe?

This is a nice topic for discussion.

High Dimensional Expanders: Introduction I

Alex Lubotzky and I  are running together a year long course at HU on High Dimensional Expanders. High dimensional expanders are simplical (and more general) cell complexes which generalize expander graphs. The course is taking place in Room 110 of the mathematics building on Tuesdays 10-12. The first four hours were devoted to an introduction to the course that came with a disclaimer that some of the material is new to us as well, with a promise that the course will occasionally turn into a seminar featuring interesting speakers, and with a hope that perhaps we will be able to discover while running the course interesting questions to answer or ask. It will be too difficult for me  to follow the entire course over the blog but I would like to devote two posts to the Introduction with some remarks and backgrounds.

A brief introduction.

The introduction included the following four  parts.

Introduction to Expanders: Alex briefly described the definition of expanders, their spectral properties, the relation with random walks, the construction of expanders, the construction of Ramanujan graphs, one brief application.

Introduction to high dimensional complexes: I briefly described higher dimensional topological objects and mainly simplicial complexes, and the notions of homology and cohomology.

Introduction to high dimensional expanders: I briefly went over several possible (not equivalent) definitions: Cohomological definition; geometric and topological definitions; spectral definition;

Ramanujan graphs and complexes: Alex briefly described what they are.

In this post we will go over the first three items.  The next post will discuss the fourth item, provide credits, references and links,  and also discuss examples, connections, potential applications, and questions.


1. Expander graphs

1.1 The definition

Let G be a graph on the vertex set V. G is an \epsilonexpander if for every set U of vertices, |U| \le |V|/2, the number of edges of G containing one vertex from U and one vertex from V \backslash U is at least \epsilon|U|.

The set of edges E_G(U,\bar U) in G from U to its complement are sometimes called the edge-boundary of U. The expansion h(G) of G is defined by

h(G)= \min\{E_G(U,\bar U): U \subset V, U \ne \emptyset, |U| \le |V|/2\}.

1.2 Spectral relation

We will mainly be interested in the case where G is a k-regular graph with n vertices and k is a fixed integer. Let A be the adjecency matrix of G. The largest  eigenvalue of A is k and let \lambda=\lambda_2 be the second largest eigenvalue. 

Theorem (Alon-Boppana): \lambda\ge 2\sqrt {k-1}-o_n(1)

Theorem (Tanner, Alon-Milman): h(G)\ge (k-\lambda)/2

Theorem (Alon): h(G) \le \sqrt {2k(k-\lambda)}

1.3 Random walks

For regular graphs, the expansion property (through the spectral interpretation) implies that (unless the graph is bipartite) the simple random walk on the graph G converges quickly to the uniform distribution on the vertices.

We will come back to examples of expander graph and to a certain application after defining high dimensional expansion.

2. High dimensional complexes and homology

We defined abstract simplicial complexes and geometric simplicial complexes K. Then we defined the chain groups C_i(K): i\ge -1 with coefficients in Z/2Z and the cochain groups C^i(K) and we identified between them. Thus an element x in the ith chain or cochain groups can be regarded as a linear combination of i-dimensional faces of K. The support of x, supp(x) is the set of i-faces of K with nonzero coefficient in x.

We described the boundary and coboundary operations.  Briefly, if x is the i chain that correspond to an i-face S, then \partial (x), the boundary operation,  is the sum of all (i-1) faces of S. This definition is extended by linearity to every i-chain. When we think about x above as an element in the ith cochain group then \delta(x) is the sum (modulo 2) of all (i+1)-faces of K containing S.  

Then we defined the vector spaces – Z^i(K) of i-cocycles, B^i(K) of i-coboundaries and the ith cohomology H^i(K)=Z^i(K)/B^i(K). We also defined boundaries, cycles and homology.  

Everything we said apply to homology with other fields of coefficients except that it was easier to define the boundary/coboundary operations over Z/2Z (for other fields of coefficients we need to worry about signs). We always consider reduced homology/cohomology without saying it.

3. High dimensional expanders

We mention several different (nonequivalent) notions of high dimensional expansions. 

3.1 (co)Homological definition:

Let K be a simplicial complex, define

h_i(K)=\min_y \max _x~\{~{\frac{|supp(y)|}{|supp(x)|}}: y \in B^{i+1}(K),~x\in (C^i(K)\backslash B^i(K)), \delta (x)=y\}

Another way to write the same thing is this:

For x\in C^i(K)\backslash B^i(K) write

h(x)=\min\{|supp(\delta x)|/(|supp(x+\delta z)|: z \in C^{i-1}(K)\}.

Then h_i(K)=\min\{~h(x): x\in C^i(K)\backslash B^i(K)\}.

If K is a d-dimensional complex we will denote h(K)=h_{d-1}(K).

Some remarks:

1) For graphs: When K is a 1-dimensional complex, the cohomological definition of h_0(K) coincides with the combinatorial definition. Every x \in C^{0}(K) is the sum of vertices in a set U \subset V of vertices. \delta (x) is the sum of edges in E(U,\bar U). The formula reduces to h(G)=\min |E(U,\bar U)/(\min |U|, |V|-|U|) over all nonempty proper subsets U of V.

2) h_i(K)=0 if and only if H_i(K)\ne 0.

3.2 Spectral definition

In this little sections we move to chain and cochain groups with real coefficients. Define the Laplacian L_i(K): C^i(K)\to C^i(K) by

L_i = \delta \partial +\partial\delta.

Let \lambda^i(K) to be the minimal eigenvalue of L_i(K).

We will say that a d-dimensional space is an i-expander in the spectral sense, if \lambda^{i}(K) is large. As before we are mainly interested in the case where i=\dim (K)-1

3.3 Geometric and topological definitions.

Let K be a d-dimensional simplicial complex. Let \phi be an embedding of the vertices of K to R^d. Given a d-dimensional face F of K we denote by \phi(F) the convex hull of the images under \phi of the vertices of $F$.  (Alternatively we can think about K as a geometric simplicial complex and about \phi as a mao to R^d which is an affine map on the faces of K.)

The overlap number w.r.t. \phi and a point x \in R^d, denoted by overlap(K,\phi,x) is the number of d dimensional faces in K whose image under \phi contains x. The overlap number of K is defined as

overlap(K) = \min_{\phi} \max_{x \in R^d} overlap (K,\phi,x).

The topological overlap number of K is defined the same except that you allow \phi to be a continuous function from K (regarded as a geometric simplicial complex) into R^d.

Note that for graphs, large expansion implies large overlap number.

Next post: Examples, relations between the various definitions, basic research questions. Ramanujan graphs and complexes. Applications: error correcting codes, qantum codes.  More remarks, credits and and links to relevant papers.

Alantha Newman and Alexandar Nikolov Disprove Beck’s 3-Permutations Conjecture

Alantha Newman and Alexandar Nikolov disproved a few months ago one of the most famous and frustrating open problem in discrepancy theory: Beck’s 3-permutations conjecture. Their paper  A counterexample to Beck’s conjecture on the discrepancy of three permutations is already on the arxive since April. (I was slow to get the news. Yuval Peres who heard it from Prasad Tetali told me about it today. You can read about it already on Joel Spencer’s homepage. Joel had offered 100$ prize for solving the conjecture that Alantha and Alexandar collected.)

The paper’s abstract tells the story.

Our previos post gives the basic definition of discrepancy of a hypergraph (=set-system), and describes a theorem by Beck and Fiala.

Abstract: Given three permutations on the integers 1 through n, consider the set system consisting of each interval in each of the three permutations. Jozsef Beck conjectured (c. 1987) that the discrepancy of this set system is O(1). We give a counterexample to this conjecture: for any positive integer n = 3^k, we exhibit three permutations whose corresponding set system has discrepancy \Omega (\log (n)). Our counterexample is based on a simple recursive construction, and our proof of the discrepancy lower bound is by induction. This example also disproves a generalization of Beck’s conjecture due to Spencer, Srinivasan and Tetali, who conjectured that a set system corresponding to l permutations has discrepancy O(\sqrt l).

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:  Continue reading

Test Your Intuition (14): A Discrete Transmission Problem

Recall that the n-dimensional discrete cube is the set of all binary vectors (0-1 vectors) of length n. We say that two binary vectors are adjacent if they differ in precisely one coordinate. (In other words, their Hamming distance is 1.) This gives the n-dimensional discrete cube a structure of a graph, so from now on , we will refer to binary vectors as vertices.

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.

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 (0,0,0,…,0). At round 2 you send the message to vertex (1,1,…,1). Then you wait and sit. With this strategy it will take \lceil n/2\rceil+1 rounds.

Test your intuition: Is there a better strategy?

Here is a link to previous posts in the “Test-your-intuition” series.