We say that a 2-coloring $col : V_G \rightarrow \{0, 1\}$ of a graph $G$ is $\epsilon$-approximate if $Pr_{(w, v) \in E_G}(col(w) \neq col(v)) \geq \epsilon$. For every $n$, what is the maximum $\epsilon_n$ for which the halved cube graph has an $\epsilon_n$-approximate coloring $col_n$? The halved cube graph is the graph you get by using the same construction as the Boolean cube but flipping 2 bits instead of 1 to get from vertex to vertex, and then throwing out one of the two identical connected components. What is the family of colorings which witnesses this? Is there a natural coloring which comes close to the optimum, ideally approaching it asymptotically?

  • $\begingroup$ Your approximate 2-coloring problem is just the Max-Cut problem, isn't it? $\endgroup$ Mar 6 '18 at 6:17
  • $\begingroup$ Right, a scaled version of it. $\endgroup$ Mar 6 '18 at 14:24
  • $\begingroup$ The scaling is pretty common (for Max-Cut and other Max-CSP problems). I think calling it Max-Cut would make the question easier to place in context. $\endgroup$ Mar 6 '18 at 14:40
  • $\begingroup$ Right, so the context of why I asked this is actually not in solving max-cut problems, but in understanding the maximum of this measure I’ve been calling the k-sensitivity for k=2. However, if you’d like to edit that in, please feel free. I’m glad you mentioned it, as I didn’t realize. $\endgroup$ Mar 6 '18 at 14:43

The answer is $\epsilon_n = \left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right) / {n \choose 2}$.

First, here's a formal definition of the halved cube graph $H_n$. The vertices are bitstrings of the form $a_1a_2\ldots a_n$ such that $a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0$. Two vertices $a_1a_2 \ldots a_n$ and $b_1b_2\ldots b_n$ are adjacent if and only if they differ in exactly two bits.

Define coloring $col_n$ of $H_n$ as follows: $$col_n(a_1a_2\ldots a_n) = a_1 \oplus a_2 \oplus \cdots \oplus a_{\lceil\frac{n}{2}\rceil}$$.

Consider the probability that a uniformly random edge has different colors on its two endpoints. It should be easy to see from the definition that an edge whose endpoints differ in bits $i$ and $j$ has different colors on both end points if and only if exactly one of these two indices is at most $\lceil\frac{n}{2}\rceil$. Furthermore, if we choose a uniformly random edge, then the pair of indices at which that edge's endpoints differ also ends up uniformly random (among all possible pairs of indices). Thus, the probability we are looking for is equal to the probability that a uniformly random pair of indices has the property that one index is at most $\lceil\frac{n}{2}\rceil$ while the other is not. There are $\left(\lceil\frac{n}{2}\rceil\times \left(n-\lceil\frac{n}{2}\rceil\right)\right) = \left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right)$ pairs with this property and $n \choose 2$ pairs in total. Thus, the probability we are looking for is $\left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right) / {n \choose 2} = \epsilon_n$. In other words, we have shown that coloring $col_n$ is an $\epsilon_n$-approximate coloring.

If $v = a_1a_2\ldots a_n$ is a vertex and $i$ is an index, then define $V(v, i) = \{v\} \cup \{b_1b_2\ldots b_n \in N(v)~|~a_i \ne b_i\}$ (where $N(v)$ is the set of neighbors of $v$). It is easy to show that all vertices in $V(v,i)$ are adjacent.

Consider the following procedure:

  • choose a vertex $v$ uniformly at random from $H_n$
  • choose an index $i$ uniformly at random from $\{1, 2, \ldots, n\}$
  • choose two vertices in $V(v, i)$ uniformly at random
  • output the edge between those vertices

This procedure samples an edge of $H_n$ with some probability distribution. It is possible to show that every edge is sampled with the same probability (this is somewhat annoying to prove, but you could argue this by symmetry). Therefore, this procedure can be thought of as a method of uniformly sampling an edge from $H_n$. We will prove below that for any fixed $v$ and $i$, the probability that a two random vertices from $V(v, i)$ have different colors is always at most $\epsilon_n$. Then if we sample an edge using the above procedure, the conditional probability that the two vertices at the third step have two different colors (given the outcomes of the first two steps) will be at most $\epsilon_n$. We conclude that the unconditional probability is also at most $\epsilon_n$. But then we have that the probability that an edge has two different colors at its endpoints when the edge is chosen uniformly at random is at most $\epsilon_n$. Thus, no coloring can be an $\epsilon$-approximation for any $\epsilon > \epsilon_n$.

All that's left is to show that two random vertices from $V(v, i)$ have different colors with probability at most $\epsilon_n$. There are $n$ vertices in $V(v, i)$. If $a$ vertices are colored in one color, then there are $a(n-a)$ pairs with different colors. Thus, the probability of choosing two vertices with different colors is $a(n-a) / {n \choose 2}$. But the closer $a$ gets to $\frac{n}{2}$, the larger $a(n-a)$ gets. In particular, for $n$ even, $a(n-a)$ achieves a maximum value of $n^2/4 = \left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right)$ at $a = \frac{n}{2}$ and for $n$ odd, $a(n-a)$ achieves a maximum value (for integer $a$) of $(n^2-1)/4 = \left(\frac{n-1}{2}\times\frac{n+1}{2}\right) = \left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right)$ at $a = \frac{n\pm 1}{2}$. In all cases, the maximum value of $a(n-a)$ is $\left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right)$, so we can conclude as desired that two random vertices from $V(v, i)$ have different colors with probability at most $\left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right) / {n \choose 2} = \epsilon_n$.

  • $\begingroup$ Thanks Mikhail! This is awesome, as it sort of confirms my intuition, that any function making this quantity large (above polylog n / n choose 2) must be quite hard to compute. The quantity you maximized is something I've been calling the "2-sensitivity" of a function. $\endgroup$ Mar 6 '18 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.