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}

Hints.

  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 http://www.math.ens.fr/metric2011/
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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s