- Show that for the tribes function, .
- Show that for monotone Boolean functions,
- If is Boolean, there is a monotone Boolean function such that
- Let . Recall that is the number of neighbours of where . Show that
- Prove by induction the isoperimetric inequality
- Recall that the size of tribes is chosen so that , which gives . Here, . Let us estimate changing changes from to . For this, the first tribe must agree on 1 whereas none of the other tribes do. So the probability is . Alternatively, by symmetry, and one can compute directly.
- has a simple expression in terms of
- Use “shifting”, a combinatorial analogue of symmetrization in geometry. Let be obtained from by switching and every time they are not is the desired order (increasing in ). Applying successively produces a monotone function . Then and, for , . Furthermore, .
- Recall has if , otherwise. Also, .
- Let , , . , where is the measure on . With induction hypothesis,
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 which represents a voting method. The index measures the power of the -th voter. It is well suited to weighted majority functions, such as
The power is not simply the weight. The Banzhaf power index is merely .
Definition 1 (Shapley, Shubik) The Shapley-Shubik power indices of are
Russo’s Lemma gives
Theorem 2 Let be a sequence of monotone Boolean functions. tends to for every fixed tends to . Quantitatively,
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 , maximum amount the coalition can win when playing together. The indices should satisfy a sequence of axioms of the form
- Dummies (players such that for all ) get nothing.
and so on… Shapley-Shubik’s theorem is that the axioms uniquely determine the ‘s and they are given by the formula above.
3. Functions with low influences
3.1. Naive estimate on transition probabilities
Let be a fixed graph (which can depend on , for instance, a Hamiltonian cycle). What is the transition probability for property or ?
The expected number of matchings is . Is it true that the transition probability for existence of a perfect matching is such that expectation aquals ? Sounds naive.
Definition 3 The transition probability is
The naive estimate is
Of course, .
Conjecture (Kahn, Kalai). For every , .
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 and are bounded away from and , is bounded from below. A bound from above then has strond consequences.
Theorem 4 (Friedgut) Assume tends to . If is bounded above, then is closed to a junta, i.e. described up to small error by a bounded number of variables.
When we let tend to zero (but stay aay from ), weaker results still hold.
Say a function can be described by a family of sets if .
Example. Containing a 5-clique is not a junta, but is described by a family of sets of size .
Theorem 5 (Hatami) Let be monotone. For every , there is , there is a function that can be described by a family of sets of bounded sizes, and .
Conjecture. If is close to equality in the isoperimetric inequality,
then is close to a function describable by a family of sets of size . Close means .
Example 1 Matchings in hypergraphs.
Can one cover a graph with disjoint triangles ? There, , whereas . Johanssen-Kahn-Vu solved this special case.
Conjecture. If is a family of subsets of of size and has no three pairwise disjoint members. Then
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 with . When drawn according to , a typical set has elements, so the -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 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 , using Fourier analysis, and then go on to a full solution.