Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
2  
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

1 Answer 1

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|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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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