Optimal Monotone Families for the Discrete Isoperimetric Inequality

2010-01-05T11:21:14Z

Background: the Discrete Isoperimetric Inequality

Start with a set X={1,2,...,n} of n elements and the family $2^X$ of all subsets of X.

For a real number p between zero and one, we consider a probability distribution $\mu_p$ on $2^X$ where the probability that $i \in S$ is p, independently for different i's. Thus for p=1/2 we get the uniform probability distribution.

Given a family F, for a subset S of X, we write h(X) as the number of subsets T in X such that

(1) T differs from S in exactly one element

(2) Exactly one set among S and T belongs to F.

The edge-boundary of F is the expectation of h(S) (according to $\mu_p$) over all subsets S of X. It is denoted by $I^p(F)$.

Now a famous isoperimetric relation asserts that

(IR) $I^p(F) \ge (1/p) \mu_(p)(F) \cdot \log \mu_p(F))$

This relation is true for every family F and every p. It is especially famous and simple when $p=1/2$ and $\mu_p(F)=1/2$. In this case, it says that given a set of half the vertices of the discrete cube $2^X$, the number of edges between F and its complement is at least $2^{n-1}$.

The Problem

A family F of subsets of $2^X$ is monotone increasing if when S belongs to F and T contains S then T also belongs to F. (Monotone increasing families also also called "filtes" and "up-families".) From now on we will restrict our attention to the case of monotone increasing families.

We say that a family is optimal for $\mu_p$ if the isoperimetric inequality (IR) is sharp up to a multiplicative constant $1000 log (1/p)$.

Problem: For every monotone increasing family F, given an interval [s.t] of real numbers so that $t/s > 1000 \log n$ we have some p in the interval [s,t] so that F is optimal with respect to $\mu_p$.

Motivation 1

There are two items on the motivation list. The first is why is the problem interesting.

Isoperimetric inequalities are quite central in combinatorics and in applications to probability. This specific problem is a sort of "missing lemma" in a work by Jeff Kahn and me about threshold behavior of monotone properties. The problem is related to an appealing conjecture about random graphs.

This missing lemma is needed for the following conjecture:

Conjecture: Consider a random graph G in G(n,p) and the graph property: G contains a copy of a specific graph H. (Note: H depends on n; a motivating example: H is a Hamiltonian cycle.) Let q be the minimal value for which the expected number of copies of H' in G is at least 1/2 for every subgraph H' of H. Let p be the value for which the probability that G contains a copy of H is 1/2. Conjecture: p/q = O(log n).

(Unfortunately it is not the only missing lemma needed to prove this conjecture.) The paper by Kahn and myself contains an easy proof of a much wealer version of the lemma, where $1000 \log n$ is replaced by $C_\epsilon n^\epsilon$ for every fixed $\epsilon$, where $C_\epsilon$ is a constant depending on $\epsilon$.

Motivation 2

The second item on the motivation list is is why the problem might be doable or even easy.

For a monotone increasing family F of subsets let $a_k(F)$ be the subsets of F of cardinality k. There is a theorem of Kruskal and Katona that gives a complete characterization of sequances that can appear as $(a_0(F),a_1(F),\dots,a_n(F))$. The Kruskal Katona theorem gives a numerical characterization.

It also asserts that every such sequence can be realized by very special families: the k-sets in the family are initial with respect to the reverse lexicographic ordering.

It is easy to see that the answer of our problem for a family F depends only on $(a_0(F), a_1(F), \dots, a_N(F))$. So, in principle, a positive or a negative answer to the problem should follow from the Kruskal-Katona theorem.

A related paper with several open problems by Michel Talagrand.

M. Talagrand, Are many sets explicitely small?

Optimal Monotone Families for the Discrete Isoperimetric Inequality - MathOverflow