Optimal Monotone Families for the Discrete Isoperimetric Inequality - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T19:58:08Z http://mathoverflow.net/feeds/question/10799 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/10799/optimal-monotone-families-for-the-discrete-isoperimetric-inequality Optimal Monotone Families for the Discrete Isoperimetric Inequality Gil Kalai 2010-01-05T11:21:14Z 2010-05-24T13:24:59Z <h2>Background: the Discrete Isoperimetric Inequality</h2> <p>Start with a set X={1,2,...,n} of n elements and the family $2^X$ of all subsets of X. </p> <p>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.</p> <p>Given a family F, for a subset S of X, we write h(X) as the number of subsets T in X such that</p> <p>(1) T differs from S in exactly one element</p> <p>(2) <strong>Exactly one</strong> set among S and T belongs to F. </p> <p>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)$.</p> <p>Now a famous isoperimetric relation asserts that </p> <blockquote> <p>(IR) $I^p(F) \ge (1/p) \mu_(p)(F) \cdot \log \mu_p(F))$</p> </blockquote> <p>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}$. </p> <h2>The Problem</h2> <p>A family F of subsets of $2^X$ is <em>monotone increasing</em> 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. </p> <p>We say that a family is <strong>optimal</strong> for $\mu_p$ if the isoperimetric inequality (IR) is sharp up to a multiplicative constant $1000 log (1/p)$.</p> <blockquote> <p><strong>Problem:</strong> 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$. </p> </blockquote> <h2>Motivation 1</h2> <p>There are two items on the motivation list. The first is why is the problem interesting. </p> <p>Isoperimetric inequalities are quite central in combinatorics and in applications to probability. This specific problem is a sort of "missing lemma" in <a href="http://front.math.ucdavis.edu/0603.5218" rel="nofollow">a work by Jeff Kahn and me</a> about threshold behavior of monotone properties. The problem is related to an appealing conjecture about random graphs.</p> <h2>This missing lemma is needed for the following conjecture:</h2> <blockquote> <p><strong><a href="http://front.math.ucdavis.edu/0603.5218" rel="nofollow">Conjecture</a>:</strong> 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). </p> </blockquote> <p>(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$.</p> <h2>Motivation 2</h2> <p>The second item on the motivation list is is why the problem might be doable or even easy.</p> <p>For a monotone increasing family F of subsets let $a_k(F)$ be the subsets of F of cardinality k. There is a <a href="http://en.wikipedia.org/wiki/Kruskal-Katona_theorem" rel="nofollow">theorem of Kruskal and Katona</a> that gives a <strong>complete characterization</strong> of sequances that can appear as $(a_0(F),a_1(F),\dots,a_n(F))$. The Kruskal Katona theorem gives a numerical characterization. </p> <p>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. </p> <p>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. </p> <h2>A related paper with several open problems by Michel Talagrand.</h2> <p>M. Talagrand, <a href="http://people.math.jussieu.fr/~talagran/preprints/small.pdf" rel="nofollow">Are many sets explicitely small?</a></p>