Notes of Gil Kalai’s lecture nr 5

1. Exercises

Exercise 1

  1. Show that for the tribes function, {I_k (f)=c\frac{\log n}{n}}.
  2. Show that for monotone Boolean functions,

    \displaystyle  \begin{array}{rcl}  I(f)\leq I(Majority)=c\sqrt{n}. \end{array}

  3. If {f} is Boolean, there is a monotone Boolean function {g} such that

    \displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}(f)=\mathop{\mathbb E}(f) \quad\textrm{and}\quad\forall S\subset\{1,\ldots,n\},\, I_S^+ (g)\leq I_S^+ (f),\,I_S^- (g)\leq I_S^- (f). \end{array}

  4. Let {f:\Omega_n \rightarrow\{-1,1\}}. Recall that {h(x)} is the number of neighbours {y} of {x} where {f(y)\not=f(x)}. Show that

    \displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}(h^2)=\sum_{S}|S|^2 \hat{f}_S^2 . \end{array}

  5. Prove by induction the isoperimetric inequality

    \displaystyle  \begin{array}{rcl}  p I^p (f)\geq \mu^p (f)\log\frac{1}{\mu^p (f)}. \end{array}


  1. Recall that the size {s} of tribes is chosen so that {\mathop{\mathbb E}(f)=\frac{1}{2}}, which gives {s=\log n -\log\log n +c}. Here, {I_k (f)=2I_k^- (f)}. Let us estimate {\mathop{\mathbb P}(}changing {x_1} changes {f} from {1} to {0)}. For this, the first tribe must agree on 1 whereas none of the other tribes do. So the probability is {\frac{1}{2^s}(1-\frac{1}{2^s})^{t-1}\sim\frac{1}{2^{s+1}}=\frac{\log n}{n}}. Alternatively, by symmetry, {I_k (f)=\frac{1}{n}I(f)} and one can compute {\mathop{\mathbb E}(h)} directly.
  2. {I^p(f)} has a simple expression in terms of

    \displaystyle  \begin{array}{rcl}  a_k =|\{x\in\Omega_n \,;\,f(x)=1\textrm{ and }x\textrm{ has }k\,1's\}|. \end{array}

  3. Use “shifting”, a combinatorial analogue of symmetrization in geometry. Let {S_i (f)} be obtained from {f} by switching {f(x)} and {f\circ\sigma_i (x)} every time they are not is the desired order (increasing in {x_i}). Applying successively {S_1 ,\ldots,S_n} produces a monotone function {g}. Then {I_k (S_k (f))=I_k (f)} and, for {i\not=k}, {I_k (S_i (f))\leq I_k (f)}. Furthermore, {\mathop{\mathbb E}(S_i (f)=\mathop{\mathbb E}(f)}.
  4. Recall {f_k =f-f\circ\sigma_k} has {\widehat{f_k}_S=2\hat{f}_S} if {k\in S}, {\widehat{f_k}_S=0} otherwise. Also, {h(x)=|\{k\,;\,f_k (x)\not=0\}}.
  5. Let {F=\{f=1\}}, {A=F\cap\{x_1 =1\}}, {B=F\cap\{x_1 =0\}}. {\mu^p (F)=p{\mu'}^p(A)+(1-p){\mu'}^p(B)}, where {{\mu'}^p} is the measure on {\Omega_{n-1}}. With induction hypothesis,

    \displaystyle  \begin{array}{rcl}  pI^p (f)&=&p(1-p){I'}^p(A)+p^2 {I'}^p (B) +p{\mu'}^p(A\Delta B)\\ &\geq&(1-p){\mu'}^p(A)\log(\frac{1}{{\mu'}^p (A)})+p{\mu'}^p(B)\log(\frac{1}{{\mu'}^p (B)})+{\mu'}^p (A)-{\mu'}^p (B). \end{array}

    Conclude with convexity of log.

Linguistic statistics: French, English, Hungarian, Italian, Spanish say “more or less”,

Hebrew, Polish, Greek say “less or more”.

2. Necessary and sufficient conditions for a sequence of monotone function to have a sharp threshold

We use a notion from game theory and social choice, Shapley-Shubik power index. Given a monotone Boolean function {f} which represents a voting method. The index measures the power of the {k}-th voter. It is well suited to weighted majority functions, such as

\displaystyle  \begin{array}{rcl}  f(x)=\begin{cases} 1 & \text{ if } \sum_{i=1}^n w_i \geq W, \\ 0 & \text{otherwise}. \end{cases} \end{array}

The power is not simply the weight. The Banzhaf power index is merely {I_k (f)}.

Definition 1 (Shapley, Shubik) The Shapley-Shubik power indices of {f} are

\displaystyle  \begin{array}{rcl}  \psi_k (f)=\int_{0}^1 I_k^p (f)\,dp. \end{array}

Russo’s Lemma gives

\displaystyle  \begin{array}{rcl}  \sum_{k=1}^n \psi_k (f)=1. \end{array}

Theorem 2 Let {f_n} be a sequence of monotone Boolean functions. {|p_{1-\epsilon}(f_n)-p_\epsilon (f_n)|} tends to {0} for every fixed {\epsilon} {\Leftrightarrow} {\max_k \psi_k (f) } tends to {0}. Quantitatively,

\displaystyle  \begin{array}{rcl}  |p_{1-\epsilon}(f_n)-p_\epsilon (f_n)|\leq C(\epsilon)\frac{1}{\log\log(\frac{1}{\max_k \psi_k (f)})}. \end{array}

Maybe only one log suffices.

Remark 1 Motivation for the Shapley-Shubik power index.

The Shapley value applies to cooperative games. For every coalition (set of players), define the pay-off {v(S)}, maximum amount the coalition can win when playing together. The indices should satisfy a sequence of axioms of the form

  • Dummies (players {k} such that {v(S\cup\{i\})=v(S)} for all {S}) get nothing.
  • {\psi_k (v)=v(\{k\})}
  • {\sum\psi_k (v)=v(\{1,\ldots,n\})},

and so on… Shapley-Shubik’s theorem is that the axioms uniquely determine the {\psi_k}‘s and they are given by the formula above.

3. Functions with low influences

3.1. Naive estimate on transition probabilities

Let {H} be a fixed graph (which can depend on {n}, for instance, a Hamiltonian cycle). What is the transition probability for property {H\subset G} or {G\in G(n,p)} ?

The expected number of matchings is {p^{n/2}\frac{n!}{2^{n/2}}}. Is it true that the transition probability for existence of a perfect matching is {p} such that expectation aquals {1/2} ? Sounds naive.

Definition 3 The transition probability is

\displaystyle  \begin{array}{rcl}  p=\min\{p\,;\,\mathop{\mathbb P}_{G\in G(n,p)}(H\subset G)\geq\frac{1}{2}. \end{array}

The naive estimate is

\displaystyle  \begin{array}{rcl}  q=\min\{p\,;\,\mathop{\mathbb E}_{G\in G(n,p)}|\textrm{copies of }H\textrm{ in }G|\geq\frac{1}{2}. \end{array}

Of course, {q\leq p}.

Conjecture (Kahn, Kalai). For every {H}, {p\leq c(\log n) q}.

This is wild. We did not find any counterexample. This belongs to a network of interrelated conjectures. Talagrand added more conjectures of his own. Among these conjectures is the one in the following subsection.

3.2. Functions near isoperimetric equality

When {p} and {\mu^p (f)} are bounded away from {0} and {1}, {I^p (f)} is bounded from below. A bound from above then has strond consequences.

Theorem 4 (Friedgut) Assume {\frac{\log p}{\log n}} tends to {0}. If {I^p (f)} is bounded above, then {f} is closed to a junta, i.e. described up to small error by a bounded number of variables.

When we let {p} tend to zero (but {\mu^p (f)} stay aay from {0}), weaker results still hold.

Say a function {g} can be described by a family {\mathcal{G}} of sets if {g(x)=1 \Leftrightarrow \{i\,;\,x_i =1\}\in\mathcal{G}}.

Example. Containing a 5-clique is not a junta, but is described by a family of sets of size {5}.

Theorem 5 (Hatami) Let {f} be monotone. For every {\epsilon>0}, there is {C(\epsilon)}, there is a function {g} that can be described by a family of sets of bounded sizes, and {\mu^p (f-g)\leq \epsilon}.

Conjecture. If {f} is close to equality in the isoperimetric inequality,

\displaystyle  \begin{array}{rcl}  pI^p (f)\leq C\log\frac{1}{p}\mu^p (f)\log\mu^p (f), \end{array}

then {f} is close to a function describable by a family of sets of size {C\log\mu^p (f)}. Close means {\mu^p (f\Delta g)=o(\mu^p (f))}.

Example 1 Matchings in hypergraphs.

Can one cover a graph with disjoint triangles ? There, {p\sim n^{-2/3}(\log n)^3}, whereas {q\sim n^{-2/3}}. Johanssen-Kahn-Vu solved this special case.

Conjecture. If {\mathcal{F}} is a family of subsets of {\{1,\ldots,n\}} of size {k} and {\mathcal{F}} has no three pairwise disjoint members. Then

\displaystyle  \begin{array}{rcl}  |\mathcal{F}|\leq\max\{choose(n,k)-choose(n-2,k),choose(3k-1,k)\}. \end{array}

Fourier analysis applies to this problem (this was know long ago, Wilson, Hoffman, Delsarte,…). The idea is to replace the counting measure on the space of subsets of {\{1,\ldots,n\}} with {\mu^p}. When drawn according to {\mu^p}, a typical set has {k=pn} elements, so the {\mu^p}-variant is a good approximation of the original problem.

Sometimes, Fourier analysis manages to entirely solve the combinatorial problem. This happens with the following

Conjecture (Simionovitz, Sos). Given a family of graphs on {n} labelled vertices such that every two graphs in the family share a triangle, what is the maximum size of such a family ? Show that the optimal example is the famly of all the graphs containing a given triangle.

Settled by Ellis-Friedgut-Fillmus. They prove that for such a family {\mathcal{F}}, {\mu^p (\mathcal{F})\leq p^3} using Fourier analysis, and then go on to a full solution.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Course, Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s