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