

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

It is well known that isoperimetric inequalities on a hypercube are closely related to influences, but all the theorems I'm aware of deal with monotone sets. Now suppose we have an arbitrary set $X \subset \{0, 1\}^n$, and let us color all vertices of a hypercube that lie in $X$ in black, others in white. The boundary edges (which have their endpoints colored in different colors), are of two types: going in positive direction we either go from white to black (positive influence) or from black to white (negative influence). Let us denote these edge sets by $D^+$ and $D^-$.

Now, the question follows:

Suppose that every node in $X$ is connected to $(1,1,...,1)$ (which belongs to $X$ as well) by a path that consists of only increasing edges (that is, following such path we always switch some coordinate from $0$ to $1$ and not otherwise). Suppose also that $P(X) = 1/2$, assuming the uniform measure on a hypercube. Moreover, let $X$ be symmetric. Is it true that $|D^+|-|D^-| > 0$? If not, what additional conditions should be posed on $X$ to make it true?

More generally, can one bound $|D^+|-|D^-|$ to get an analog of sharp threshold results for symmetric but not necessary increasing events?

share|cite|improve this question
What do you mean by the condition that $X$ is symmetric? – Douglas Zare Aug 23 '12 at 21:41
Sorry for being sloppy with this. I mean that there is a transitive permutation group $\Gamma$ on $\\{1,...,n\\}$ such that $X$ is invariant under $\Gamma$. I was keeping in mind the monotone case, considered e.g. in E. Freidgut, G. Kalai "EVERY MONOTONE GRAPH PROPERTY HAS A SHARP THRESHOLD". One could say much more for symmetric events in this case. – DmitryZ Aug 24 '12 at 14:07
up vote 1 down vote accepted

$|D^+| - |D^-|$ can be expressed in terms of the level counts.

Let $S_k$ be the set of vertices of the cube with $k$ coordinates equal to $1$. Let $c_k = |X \cap S_k|$.

Let $d_k$ be the contribution to $|D^+| - |D^-|$ from the edges between $S_k$ and $S_{k+1}$. Weight each edge $+1$ if it is white-black, $0$ if it is between vertices of the same color, and $-1$ if it is black-white. The total weight is $d_k$. We can also compute $d_k$ by weighting each half-edge leaving $S_k$ by $0$ if it leaves a white vertex and $-1$ if it leaves a black vertex, and weight each half-edge to $S_{k+1}$ by $+1$ if it the vertex is black and $0$ if the vertex is white, so the weight of each edge is the sum of the weights of its halves. So, $d_k = (k+1)c_{k+1}- (n-k)c_k. $

$$\begin{eqnarray}|D^+| - |D^-| & = & \sum_{k=0}^{n-1} (k+1)c_{k+1} - (n-k)c_k \\\ & = & \sum_{k=0}^n (2k-n)c_k. \end{eqnarray}$$

This is negative if the sum of the coordinates of the center of mass of $X$ is less than $n/2.$

I'm not sure what you mean by the assumption that $X$ is symmetric. Since you assume $|X| = 2^{n-1},$ a reasonable possibility is that you want $X$ to be self-complementary, that $(x_1,...,x_n) \in x \iff (1-x_1,...,1-x_n) \notin X.$ If so, then it is true that $|D^+| - |D^-| \gt 0$ for $n \le 3$ by inspection, it is possible for $|D^+| - |D^-| = 0$ when $n = 4$, and $|D^+| - |D^-| \lt 0$ is possible for $n \ge 5$.

$S_4 = \lbrace (1,1,1,1) \rbrace$

$S_3 = \lbrace (1,1,1,0) \rbrace$

$S_2 = \lbrace (1,1,0,0),(1,0,1,0),(0,1,1,0) \rbrace$

$S_1 = \lbrace (1,0,0,0),(0,1,0,0),(0,0,1,0) \rbrace$

$|D^+| - |D^-| = 4(1) + 2(1) + 0(3) - 2(3) = 0.$

The analogous construction for $n \ge 5$ is $X = \lbrace (1,1,...,1) \rbrace \cup \lbrace (x_1,...,x_n,0) \rbrace \backslash \lbrace (0, ..., 0) \rbrace.$ By the above summation,

$|D^+| - |D^-| = 2n -(2^{n-1}).$

Here is a construction of a counterexample for the revised symmetry condition, that $X$ is invariant under some transitive group of symmetries acting on the coordinates. Let $n=7$ and let the symmetries by cyclic rotation.

$|S_7| = 1, S_7 = \lbrace (1,...,1) \rbrace$

$|S_6| = 7, S_6 = \langle (1,...,1,0) \rangle$

$|S_5| = 7, S_5 = \langle (1,...,1,0,0) \rangle$

$|S_4| = 7, S_4 = \langle (1,1,1,1,0,0,0) \rangle$

$|S_3| =14, S_3 = \langle (1,0,1,1,0,0,0),(1,1,0,1,0,0,0) \rangle$

$|S_2| = 21, S_2 = \langle (1,0,0,1,0,0,0),(1,0,1,0,0,0,0),(1,1,0,0,0,0,0) \rangle$

$|S_1| = 7, S_1 = \langle (1,0,0,0,0,0,0) \rangle$

By the level count formula, $|D^+|-|D^-| = 7(1)+5(7)+3(7)+1(7)-1(14)-3(21)-5(7) = -42 \lt 0.$

share|cite|improve this answer
Thank you for the insightful answer! It's interesting if one can make your counterexample symmetric (in a sense I describe above). – DmitryZ Aug 24 '12 at 14:12

Your Answer


