Notes of Michel Talagrand’s talk


Are many small sets explicitly small ?

Philosophy: In a high dimensional space, given a large subset, most points of the space are close to the subset. The point is to get dimension independant bounds. I will give evidence that positive results may exist.


1. {p}-small sets


Vocabulary: Our ambient space will be the hypercube {\{ 0,1  \}^S}, {|S|=n}. Each point in {\{ 0,1 \}^S} is a subset of {S}. To avoid confusion, subsets of {\{ 0,1  \}^S} are called classes. We shall always use the measure {\mu_p} which is the {n}th power of the Bernoulli distribution {\mathcal{B}_p} on {\{ 0,1 \}}.

An up-class is a class such that {I\in A}, {I\subset J \Rightarrow J\in A}.


Definition 1 For {I\in S}, let \displaystyle  \begin{array}{rcl}  H_I =\{J\in S\,;\, I\subset J\}. \end{array}

Given a class {A}, let \displaystyle  \begin{array}{rcl}  A^{(q)} =\{J\subset S\,;\, J \textrm{  cannot be covered by }k\textrm{ elements of }A\} \end{array}

{A^{(q)}} is an up-class. We view points of {A^{(q)}} as very far

Main conjecture: When {A} and {q} are large, {A^{(q)}} is very small.

This does not mean that {A^{(q)}} has small measure.


Definition 2 A class {C} is {p}-small if there exists a family {I} of subsets of {S} such that\displaystyle  \begin{array}{rcl}  C\subset \bigcup H_I \end{array}

and the sum of {\mu_p} measures of {H_I} is {\leq \frac{1}{2}}.

So smallness of {C} is attested by a small number of witnesses.


Example 1 \displaystyle  \begin{array}{rcl}  B=\{I\subset S\,;\,|I|\leq k\}. \end{array}



Proposition 3 If {\mu_p (B)\geq  9/10} and {q=100}, then {B^{(q)}} is {p}-small.


Proof: {B^{(q)}} is the set of {J} of size {\geq s=qk+1}. It is covered by {H_I} with {|I|=s}. \Box

Main conjecture: When {A} is a down class, {\mu_p (A)\geq 1-\frac{1}{q}} and {q=10^{10^{10}}}, {A^{(q)}} is {p}-small.


2. Connections to geometry and probability



2.1. Connection to convexity


Carathéodory: For a convex set in {{\mathbb R}^n}, every point is the barycenter So {n} additions are needed to construct the convex hull of a balanced set {A}. (We consider multiplication by a real number as costless, since ).

How many operations are needed to construct an approximation of the convex hull ? In terms of Gaussian measure {G}.

Convexity conjecture: The exists {q} such that for every banaced {D}, there exists a convex set {C} which is contained in the sum of {q} copies of {D}.

The Main conjecture is a kind of discretized version of the Convexity conjecture (down-class refelcts convexity).


2.2. Stochastic processes


Given stochastic process {X_t}, {t\in  T}, estimate {\sup_{t\in T}X_t}.


Example 2 {X_t  (\omega)=t\cdot\omega} for {\omega} in Gaussian {{\mathbb R}^n}, {t} in a subset {T} of {{\mathbb R}^n}.



Theorem 4 {\mathop{\mathbb  E}(\sup_{t\in T}X_t)\sim\gamma_2 (T)}, a purely metric quantity, which is hard to evaluate.



Corollary 5 The set where the Gaussian process is large is covered by a collection of half-spaces, the sum of the measures of which is {\leq\frac{1}{2}}.



Corollary 6 Given a convex balanced set {C}, is covered by a collection of half-spaces, the sum of the measures of which is {\leq\frac{1}{2}}.


Reformulated convexity conjecture: Replace {C} has large Gaussian measure with its complement is covered by half spaces, the sum of the measures of which is {\leq\frac{1}{2}}.

I view {A^{(q)}} as a discrete analogue of the complement of {A+A+\cdots +A}.


2.3. Selector processes on sets


Independantly select at {\mathcal{B}_p} random points of {S}, producing random subsets {Y}. Given a class {F}, estimate the quantity

\displaystyle   \begin{array}{rcl}  \mathop{\mathbb E}_p (F):=\mathop{\mathbb E}_{Y}  (\sup_{I\in F}|I\cap Y) \end{array}

Trivial bound: {\mathop{\mathbb E}_p (F)\leq\max\{|I|\,;\,I\in F\}}


Remark 1 Suppose there exists {M\geq 1} such that\displaystyle  \begin{array}{rcl}  \sum_{J\in F}(\frac{p|J|}{M})^M \leq 1. \end{array}

Then {\mathop{\mathbb E}_p (F)\leq LN}.

Proof: Union bound.

Let us merge these two remarks.


Definition 7 Given classes, {F}, {G},\displaystyle  \begin{array}{rcl}  F+G=\{I\cup J\,;\, I\in F\, J\in G\}. \end{array}

Say that {G} dominates {F} if each set {I\in F} is contained in a set {I\in G}.


\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}_p (F)\leq \mathop{\mathbb E}_p (G). \end{array}

This gives a method to estimate {\mathop{\mathbb E}_p}.

Question: Are the above two remarks the only way to estimate {\mathop{\mathbb E}_p} ? I.e., is every class {F} a small perturbation of a class {G} for which the union bound is sharp ?


2.4. General selector processes


Let {Y} be a random set. Given a vector {t\in{\mathbb R}^S}, let {X_t =\sum_{i\in  Y}t_i}. Estimate

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}_p (\sup_{t\in T}X_t) \end{array}

as a function of the geometry of {T}. Seems related to

Bernoulli problem: estimate {\mathop{\mathbb E}_p  (\sup_{t\in T}\sum_{i}\epsilon_i t_i)}, {\epsilon_i \in\pm 1} random. Specifically, show that there are no better ways to estimate it than the obvious ones (by the absolute values).

Less ambitious

Problem: Show that the set (of {Y}‘s) where the selector process is large (compared to its expectation) is {p}-small.

This would follow from the Main conjecture. Indeed,

\displaystyle  \begin{array}{rcl}  \{Y\subset S\,;\, \sup_{t\in T}X_t \geq LM\} \end{array}

is a down class.


3. Approaches to the Main conjecture



3.1. Relaxing smallness: measures


{p}-small sets are hard to manipulate, so I introduce easier notions.


Definition 8 Say a probability measure {\nu} on {B^S} is {\delta}-spread if for all {I\in  S}, {\nu(H_I)\subset \delta^{|I|}}.

For instance, {\mu_p} is {p}-spread.


Example 3 The measure which is uniform on sets of cardinality {1} is {\frac{1}{n}}-spread.



Definition 9 A class is weakly {\delta}-small if it does not carry a {\delta}-spread probability measure.



Proposition 10 {p}-small implies weakly {p}-small.


Question: Is the converse true, up to a multiplicative constant ?

Weak form of Main conjecture: When {A} is a down class, {\mu_p (A)\geq 1-\frac{1}{q}} and {q=10^{10^{10}}}, {A^{(q)}} is weakly {p}-small.

Measures give the impression to be easier to manipulate than classes. It might be easier to find a counter example in that manner. Naively,


3.2. Relaxing {A^{(q)}} :



Definition 11 If {A} is a down class, and {I\subset S}, let\displaystyle  \begin{array}{rcl}  A_I =\{J\subset I\,;\,J\in A\}. \end{array}


Given {\alpha\in (0,1)} view {\mu_{\alpha}(A_I)} as a kind of distance of {I} to {A}.

Conjecture: There exists {\alpha>0} such that if {A} is a down class,

\displaystyle  \begin{array}{rcl}  \mu_p (A)\leq \prod \mu_p (A_I)^{\nu(\{I\})}. \end{array}

Which down classes satisfy the conjecture for all {p}-spread measures {\nu} ? For this, one must control the measure of {A} for each product measure. Product measures are indexed by vectors {t\in  {\mathbb R}_+^S} ({\lambda_t  =\bigotimes_{i}\mathcal{B}_{e^{-t_i}}}). One is interested in {-\log\lambda_t (A)} as a function of {t}. For instance, if {A=\{\emptyset\}}, {-\log\lambda_t (A)=\sum_i  t_i}. In general, it is complicated. So we compare it with multilinear polynomials.


Definition 12 Say a set {A} satisfies {C_{\gamma}} if {t\mapsto -\log\lambda_t (A)} compares, up to a {\gamma} factor, with a multilinear polynomial.

Hopefully, every set satisfies {C_{\gamma}}. This would be our boldest conjecture.


Theorem 13 If {A} is a down class and satisfies {C_{\gamma}}, conjecture 3 holds for {\alpha\leq 1-(1-p)^{\gamma/\delta}}.


Property {C_{\gamma}} survives various operations, which makes production of a counter example a hard task.


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

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