Posts Tagged ‘combinatorics’

New paper on arXiv: indistinguishable sceneries on the Boolean hypercube

January 28, 2017

I’m happy to say that fellow student Uri Grupel and I uploaded a paper to the arXiv recently under the title “Indistinguishable sceneries on the Boolean hypercube” ( We had great fun working on it, and most of the theorems are actually pretty simple and do not use heavy mathematical machinery, so I’d like to share the motivation and results with you below. I’ll try to write a fairly simple exposition, without most of the technical terms and details. If you find this too simple, just read the paper!

Our paper shows that the scenery reconstruction problem for the n-dimensional hypercube is impossible for n \geq 4. It does this using the combinatorial properties of what we call “locally biased” and “locally balanced” functions, some properties of which the paper investigates.

Don’t know what scenery reconstruction is? Want to learn about and play around with locally biased and locally balanced functions? Read on.

We’ll start with a simpler-to-state problem. Suppose you are given a cycle graph, that is, a collection of vertices arranged in a cycle. For example, here is a cycle with 13 vertices:


Each vertex is colored either black or white. There are many different such possible colorings: if there are n vertices, then there are 2^n different colorings. However, the cycle has some symmetries, and some of these colorings can be considered to be the same. For example, in the following figure, if we rotate the center cycle 5 places clockwise, we get the cycle on the left. Similarly, if we reflect the center cycle around a vertical line, we get the cycle on the right. Such colorings are called “isomorphic”, and we will treat them all as “the same” for all intents and purposes.

Suppose now we place a person at one of the vertices at random. The person then performs a random walk: at each step, she randomly goes to the vertex either to her left or to her right, with each possibility equally likely to occur. Then she tells us the color of the vertex she is currently at. The result is a sequence of colors, one for each time step, which constitute the trace of the random walk on the cycle. Here is a short example of such a trace:


The idea you should keep in your mind is this: the coloring of the cycle is a “scenery”, and the agent, walking randomly along the cycle, tells you what she sees but *not* where she is going. The scenery reconstruction on the n-cycle is then framed as follows: suppose that you are given the length of the cycle n and also an infinitely long trace of scenery observations by your agent. Can you reconstruct the scenery itself? That is, can you find the original color of each vertex of the cycle?

As an easy example, if the original cycle was colored all black, then no matter where the agent goes, she will always report “black” at every time step. So if she reports “BBBBBBB…”, we can be confident that the original scenery is the all black cycle. Similarly, if the agent reports “BWBWBWB…”, we can be confident that the original scenery is the alternating black-white cycle (we can assume that in the long run, the agent will never be stuck in a “back and forth between two vertices only path). But what about more complicated sceneries, like the one given below? Can we always reconstruct even very bizzare colorings?


The (perhaps surprising) answer is: yes! It was shown that if you are given a long enough series of observations, you can always reconstruct the original coloring! (up to isomorphism, meaning, you cannot differentiate between colorings which are shifts or reflections of one another, but we already mentioned above that weview these to be “the same”). So while this basic question is closed, there are other open questions still to be answered. For example, how many observations do we need so that we will be able to reconstruct the coloring with very high probability?

Variants of the n-cycle reconstruction problem abound. What if, in our random walk, we don’t go left or right with equal probability? What if we can jump other distances? What if we color and walk on another graph other than the cycle?

The latter question is what Uri’s and my paper addresses. Instead of the n-cycle, we investigate the scenery reconstruction problem on the Boolean hypercube in dimension n. In dimension 1, the cube is just a line. In dimension 2, a square. In dimension 3, an actual cube. In higher dimensions visualizations start to get messy. One way to think about it is as follows: the n+1-dimensional hypercube is composed of just two identical n-dimensional hypercubes, with edges connecting matching vertices in the two cubes.


So again, we place an agent at one of the vertices at random, and she starts a random walk. This time, there are n possible choices of where to go in each step. Again, she reports only the color of the vertex she is currently at. Now can we reconstruct the original coloring?

For n=1, the hypercube is just two points connected by an edge, and there aren’t that many colorings on it, so it’s no big deal. For n=2, the hypercube is a square, which is actually a cycle of length 4, and we already know how to deal with cycles, so that’s no big deal either. For n=3, it can be shown that the methods used to solve for the cycle, combined with some case-by-base analysis, again are able to reconstruct the scenery. What about other dimensions?

The (perhaps surprising) answer is: no! Starting from n=4, there exist two colorings which are non-isomorphic (that is, they are not obtained by rotations or reflections of the cube), but which nevertheless cannot be distinguished from one another based on the sequence of color observations of our agent alone! So if we are given such a sequence, we can never be sure whether it came from one coloring or the other.

Here is such a pair in dimension n=4:


To see that these are indeed two different colorings (meaning, that one is not just a rotation or reflection of the other), note that in the left image there are two small rings of black vertices, each of size 4, while in the right image there is only one large ring, of size 8. This difference cannot be due to rotations and reflections alone.

If you look carefuly, you will see an interesting property of these two colorings: every vertex, no matter what color it is, has exactly two neighbors which are black, and exactly two neighbors which are white. It is this property that prohibits us from distinguishing between the two colorings: no matter where our agent is, at the next step she will report “black” with probability 1/2, and “white” with probability 1/2, for both colorings. In technical terms, the sequence of observations distributes as a sequence of iid Bernoulli variables with success probability of 1/2.

We can take this property and generalize it: we call a coloring “locally p-biased” if every vertex, no matter what color it is, has a p-fraction of its neighbors colored black, and a 1-p-fraction of its neighbors colored white. If there are two non-isomorphic such colorings on the hypercube, for any p, then the scenery reconstruction problem is impossible to solve on that hypercube. In fact, this statement is true for any graph, not just the hypercube, so finding locally biased colorings on different graphs shows that the scenerey reconstruction problem is impossible for those graphs. But we think that such colorings stand alone by their own right, and deserve study regardless of their application to scenery reconstruction; they are simply interesting combinatorially!

Our first result was to classify for which values of p an n-dimensional hypercube even has a locally biased coloring. We saw a 1/2-biased coloring for n=4. Obviously, a 1/2-biased coloring requires the dimension to be even, since each vertex has n neighbors, and exactly n/2 of those need to be black, and n/2 white. So is there a locally 1/2-biased coloring on the 6-dimensional hypercube? What about a 1/3-biased coloring? You can try it out yourself for a bit and convince yourself that there is no 1/3-biased coloring on the 3-dimensional cube. After a bit of work, we came up with the following theorem:

Theorem 1: There exists a locally p-biased coloring on the n dimensional hypercube if and only if p is of the form p = b/2^k and 2^k divides n.

This shows, for example, that there are no locally biased colorings on odd-dimensional hypercubes. But for even-dimensional hypercubes, there do exist such colorings, and then it’s interesting to start counting them: as we said before, if there are more than two colorings for the same p value, then the scenery reconstruction problem is impossible.

Our proof uses elements from coding theory, and is not very complicated. I’ll tell it in short in the following paragraphs: feel free to skip it if you don’t want to go ito the details.

One side, the “only if”, tells you which colorings are impossible. In the n-dimensional hypercube, each vertex has n neighbors, and there are 2^n vertices overall. Suppose that in a specific locally p-biased coloring, a total of l vertices are colored black. Then when you pick a random vertex, it is black with probability l/2^n. On the other hand, when the agent takes a random step, it will be black with probability p = m/n for some m. These two probabilities are equal, so

b/n = l/2^n.

Decomposing n into its prime powers, n = c2^k where c is odd. Then

l = 2^{n-k} \cdot m / c

and since l must be a whole integer (and not a fraction), we get that m = bc for some b. This gives p = b/2^k after a short calculation.

The other direction, which says that for all p values of the proper form you can build a locally p-biased coloring, is a bit harder. We start by building locally 1/n-biased colorings for n that is a power of two, that is, n=2^k. Such colorings have the peculiar property that they induce tiles which tile the hypercube. What do I mean by this? In such a coloring, every vertex, no matter the color, has exactly 1 black neighbor. In particular, this is true for black vertices. So black vertices always come together in connected pairs, and all the neighbors of such pairs are white. Further, these white neighbors already have their “1-black-neighbor” condition satisfied, so all their other neighbors are also white. This is exemplified in the following shape, or “tile”:


If we can “tile the hypercube” with these shapes, that is, if we can cover the hypercube graph with these tiles without any pair of tiles overlapping, we will have a locally 1/n-biased coloring. Why? Well, these tiles exactly satisfy the properties stated in the above paragraph, and every vertex in such a tiling will have exactly one black neighbor.

The proof constructs such tilings by using perfect codes; without going into detail, these are well-known methods of tiling the hypercube with a half-tile: instead of two black vertices and two rings of white vertices, these methods tile the hypercube with just a single black vertex and a single ring of white vertices. These are actually known as “balls” on the hypercube:


By taking two copies of a perfect code and connecting the black vertices, we obtain the needed tiling! This gives us a locally 1/n-biased coloring, for n that is a power of two (the perfect codes we need only exist in dimension 2^k-1, so when we take two copies of the hypercube together we get a hypercube of dimension n = 2^k).

To obtain a locally m/n-biased coloring, we join together m different disjoint 1/n-biased colorings. By m disjoint colorings, we mean that if a vertex is colored black in one coloring, then it is necessarily colored white in all the others. Finally, using a bit of algebraic manipulation which I will not go into here, we can extend these colorings into hypercubes of dimension c \cdot 2^k for any c, which is exactly what our theorem stated we could do.

The theorem shows existence of some locally p-biased colorings, but tells us nothing of the number of such colorings. In order to show that the scenery reconstruction problem is impossible, we need to find at least two different such colorings. That’s where our next two theorems come into play:

Theorem 2.1: As a function of n, there is at least a super-exponential number of different locally 1/n-biased colorings on the n dimensional hypercube.

Theorem 2.2: As a function of n, there are at least C \cdot 2^{\sqrt{n}} / \sqrt{n} different locally 1/2-biased colorings on the n dimensional hypercube, where C is some constant.

Theorem 2.1 is proved by counting the number of perfect codes, which were used in proving the previous theorem; we won’t go into it here.

The proof of Theorem 2.2 is more interesting, and relies on an algebraic treatment of our colorings. It goes as follows.

Up until now, we have treated our colorings as assigning the color either black or white to each vertex. We could have equally well assigned the numbers “+1” or “-1“, and all the theorems and statements would have stayed the same: all we care is that there are two distinct “colors”. But this description has an immediate advantage: we can now easily perform arithmetic operations on the colorings. For example, if both f_1 and f_2 are colorings, then their product f = f_1 \cdot f_2 is also a coloring, where by multiplication we mean that if f_1 assigns the color f_1(v) to a vertex v, and f_2 assigns the color f_2(v), then f(v) = f_1(v)\cdot f_2(v). In words, what this multiplication means is that f is black precisely when f_1 and f_2 have the same color. This algebraic representation is often easier to work with than the verbal one.

Now, the n-dimensional hypercube can be described as follows: it is the set of points with n coordinates, where each coordinate can be either +1 or -1 (you can easily verify that this fits in with our notions of 2d and 3d cubes; it works just the same for higher dimensions). Thus a coloring is just a function

f(x_1, x_2, \ldots, x_n)

which returns either 1 or -1, and all the x_i‘s are also either 1 or -1.

This representation lets us combine two locally 1/2-biased colorings on small hypercubes together into one locally 1/2-biased coloring on a larger hypercubes: Suppose that f_1 is such a coloring on the n dimensional hypercube, and f_2 is such a coloring on the m dimensional hypercube. Then the new coloring

f(x_1, x_2, \ldots, x_{n+m}) = f_1(x_1,\ldots,x_n) f_2(x_{n+1}, \ldots, x_{n+m})

is a locally 1/2-biased coloring on the n+m dimensional hypercube! Our method for counting the number of locally 1/2-biased colorings then goes as follows: we construct many high dimensional colorings from different lower-dimensional ones. In fact, our “elementary building blocks”, from which we build all other colorings, are basically generalizations of the two colorings of the 4-dimensional hypercube which we encountered earlier in this post. It can be shown (via Fourier decomposition, a method which we won’t go into here) that taking combinations of different low-dimensional colorings always gives non-isomorphic high-dimensional colorings. In other words, if we use different building blocks, then the resultant colorings will be distinct.

We can then get a bound on the number locally 1/2-biased colorings by counting in how many distinct ways we can add up low-dimensional colorings into a high-dimensional one. After a bit of arithmetic, we find that there are at least as many colorings as there are solutions to this inequality:

4a_1 + 8a_2 + \ldots + 4k a_k \leq n,

where a_1,\ldots,a_k are non-negative integers. The number of solutions to this inequality is at least C \cdot 2^{\sqrt{n}} / \sqrt{n} , giving us Theorem 2.2.

This, I think, is quite neat: it’s enough to find just two different colorings in order to show that the scenery reconstruction problem is impossible, but in fact there are many, many more of them. And what we gave was only a lower bound: it’s entirely plausible that there is a more clever way of counting these colorings, which will give an even larger number.

So far, so good. We saw that the scenery reconstruction problem is impossible for even-dimensional hypercubes, and even saw that there are different indistinguishable colorings. What about odd-dimensional cubes?

The answer comes from what we call “locally p-balanced” colorings. In these colorings, every vertex, no matter what color it is, has a p-fraction of its neighbors colored in its own color, and a 1-p-fraction of its neighbors colored the opposite color. These colorings also yield identical scenery observations: when our agent tells us the colors she sees, the next color will always be the same as the current one with probability p. For example, the following figure shows a locally 2/3-stable and a locally 1/3-stable coloring on the 3-dimensional cube.


Locally balanced colorings are different than locally biased colorings, although the two are related. For example, we saw that there is a strong restriction on the possible p values for locally biased colorings, but it turns out that for every p, there is at least one locally balanced coloring. On the other hand, if p = 1/n or p = (n-1)/n, then there is exactly one locally balanced coloring, while, as we saw, there are many, many locally biased ones.

The main point, though, is that every locally 1/2-biased coloring f on the n-dimensional hypercube can easily give a locally balanced coloring g on the n+1 dimensional hypercube, by:

g(x_1, \ldots, x_{n+1}) = g(x_1, \ldots, x_n) \cdot x_{n+1}.

You should verify for yourself that this is indeed a locally balanced coloring, and calculate its p value. This construction gives different locally balanced functions for all odd-dimensional hypercubes of dimension n \geq 5, showing that the scenery reconstruction problem is impossible for all n \geq 4. And that’s what we promised to show in the beginning of this post.

You should play around with locally biased and locally balanced colorings yourself; they serve as good brain teasers, and indeed we’ll end with a small riddle: here are two locally balanced colorings on the infinite one-dimensional and two-dimensional integer lattices. Can you find one for the three dimensional lattice?



The Perfect Match

February 14, 2014

Valentine’s day is upon us, a cheerful reminder that the main purpose of every living creature is to copulate as much as possible and spray the world with its offspring; the more, the merrier.
This is certainly easy enough for all those twice blessed prokaryotes; twice blessed, first, for their asexual reproduction via mitosis, obliviating the need for a mate; second for their lack of consciousness, avoiding the misery induced by the absence of aforementioned mate.
However, for the rest of us, finding that special someone is tricky business; it’s a game of both chance and skill, bluffing and honesty, combinatorics and probability (well, if you’re into that kind of stuff). It’s no wonder that the world is filled with attempts to make the whole process easier: dating sites, religious / traditional matchmaking, random-blind-date-generators, etc. But in the end, it all comes down to basic mathematics.

Let’s look at some of the well known algorithms and theorems for matching couples under different conditions. In quite stereotypical behaviour, mathematicians always assume that it’s possible to rank others by order of preference in a unique and unambiguous way, or that you can reject a suitor at point blank range without remorse, stating that “Sorry Billy, Roger is 0.2 [pretties] more handsome than you”, only to dump Roger two days later because the next person in the list comes along.
Oh well. Mathematics, thou art a harsh mistress.

Hall’s Marriage Theorem:
Our first theorem discusses whether it’s possible to get everyone married in a group of n men and n women, assuming that not everyone is willing to marry everyone else (sounds reasonable). The procedure is this: for each man and woman, ask them if they see themselves as a married, middle-age couple. If so, then they are potential wedlock candidates; otherwise, you won’t pair them up. Equivalently, you could ask every man to make a list of the women he would be ok marrying with, then have the women look at the lists and cross themselves out if they don’t agree.
The result can be given as a bipartite graph:


Each of the upper nodes represents a woman, each of the bottom nodes represents a man. An edge means that both are ok with an eternal life together. It’s quite possible that a very attractive, high quality person will have many edges, meaning, a lot of people are interested in marrying him/her, while other people might have little or no edges at all. In the above example, Lisa is very popular – everyone wants to marry her, and she agrees to marry with everyone – while Fae only has one possible mate. Thus, some people have more options than others, and the question is, can we assign couples, meaning, pick edges, so that *everyone* gets married in the end?
A simple case where the answer is a straightforward yes is:


Each man is connected to one woman, and vice-versa – meaning that the couples are already picked here, and we have no real choice.
A case where the answer is no is:


You can try picking out couples and seeing that a solution indeed does not exist.
Hall’s marriage theorem states that a complete matching exists, meaning, everyone can be paired, if and only if the following condition applies: look at all the possible subsets of men (i.e first look at all the men individually, then at all the pairs of men, then at all the triplets, etc.). For each subset M, count the number of different women that they can marry, G(M). Then |M| <= G(M).

We can see that the condition applies in the first case – for each man in the set, there is an appropriate woman, and thus M = G(M), and we have a matching. In the second case, however, the condition does not hold: look at Joe, Frank, and Mark: the three of them only have two potential mates: Jill and Lisa. The theorem does not hold, and indeed, there is no matching.
A proof of this theorem (actually a slightly more generalized one) can be found in wikipedia. Notice that the theorem doesn’t tell you at all how to find the matching, only that it exists.

Happy Marriage: The Hungarian Method:
Suppose now that our n bachelors and bachelorettes have had enough of the single life, and they decide that everyone should get married, no matter what. So instead of asking every pair whether or not they agree to marry each other, we ask them to rank the match. The result is a number for each (man, woman) pair; the higher it is, the more miserable they will be with their marriage. We want to find a matching between all men and women, such that the overall happiness is highest, meaning that the sum over all rankings of the chosen pairs is the lowest it can be.
A way of looking at this is the following: create a n x n matrix, where the (i,j) entry contains the ranking of matching the i-th man with the j-th woman. An example might be as follows:


So a marriage between Frank and Anne would be a happy one, while a marriage between Joe and Jill would be rather miserable in its own way.
The question reduces to this: we need to choose n squares overall, each one in a different row and a different column, so that the sum of all the chosen squares is minimal.
The simplest way to solving this is the brute force approach: just go over all the possible matchings, and pick the best one. But when there are n men and n women, there are n! different possibilities. Try doing this for 30 men and women; tell me about it when the universe ends.
Something more clever is needed, and indeed, there exists an algorithm called the Hungarian Algorithm which can solve it in O(n3) moves. In general, it relies on the fact that you can add or subtract any number from an entire row or an entire column of the matrix, and this will not change the optimal matching. Think about it this way: if you add a number to an entire row, the total sum will change, but you are going to have to pick an entry in that row anyway, so whichever matching you choose, you will always get a larger sum.
The aim of the Hungarian algorithm is to add and subtract values from the different rows and columns in a clever way, so that the values in the matrix are always non-negative. Eventually, as if by magic mathematics, there appears an arrangement of zeros that can be picked as a matching. The algorithm is not simple, and will not be given here; conveniently, it can be found at this nice site (in the context of assigning jobs to workers, but hey, once you get to a matrix formulation, the mathematics is all the same).

Stable Marriages:
The previous algorithm gave us a global maximum for happy marriages – when we summed the total “miserableness” of the matching, it was the lowest possible between all possible matchings. However, it may be that one couple was a very bad match, and they live grumply and miserably, but in the overall matching, its still the minimum. We will now ask the question – can we make everyone happy locally?
Of course, we need to ask what that means. One interpretation is this: suppose that we match up all the couples. Some of them may be dissatisfied, and wish to break apart from the shackles of holy matrimony. If a woman desires another man more than she desires her own husband, and that man also desires that woman more than he desires his own wife, then they may each get a divorce from their current partners and marry each other instead. We say that the matching we initially had is “unstable”. If no such pairs exist, then the matching is stable.
The problem is then the following: suppose we ask each man to create a list, sorted by preference, of all the women, and we ask all the men to create a list, sorted by preference, of all the men. Can we create a stable matching, i.e, no two people will agree on replacing their partners?
It turns out that we always can, and rather efficiently, too. The basic algorithm for doing this is called the Gale-Shapley algorithm. It solves the problem in up to n2 iterations, as follows: in the first iteration, all the men approach the woman first on their list – the one they want the most. Some women may get a lot of suitors, while others may get none at all. This is ok. Each woman, from all the possible suitors, picks the man she likes best, and sends the rest away. So it goes. During every subsequent iteration, all the rejected men go to the next woman on their list, with the women picking between the new guys and the one they chose the previous iteration. The process continues until no one is rejected (this is bound to happen eventually; think why).
In the end, everyone gets matched up, and it can be proven that the matching contains no unstable couples. Of course, the scheme can also be reversed, with the women approaching the men (it turns out that this yields asymmetric results, with the active suitors getting matches that are better for them. Conclusion? It’s better to ask people out than to wait to be asked out).

Final remarks:
Feel free to assemble all your single friends and try these algorithms out. I’m sure it will create no social anxiety whatsoever, and in the end, everyone will be matched up! Hurray for mathematics.
Happy Valentine’s day.

* Note: in the problems introduced we always assumed the happy case, of an equal amount of men and women. Actually, all three problems can be extended to an unequal amount. For Hall’s theorem, instead of asking if everyone can be paired up, we can ask if all the men can find wives, or, conversely, if all the women can find husbands; the theorem stays the same. For the Hungarian algorithm, if there are, for example, more men than women, we can add fictitious “unmarriable-women” until there are an equal amount, and heavily penalize choosing them – no man would want to stay alone. The Gale-Shapely algorithm stays the same, knowing that not all participants will get a date at the end.
To sum it up and state the obvious: when there is a numerical bias towards one gender, someone always gets left out, resulting in mathematical misery. The Technion, having a whopping 35% female minority out of its 13,000 students, is a fine example of this (that’s actually a generous average term; in the physics and mathematics faculties, it’s about 20%…).