Search

Proving the "expectation-threshold" conjecture of Kahn and Kalai [Combin. Probab. Comput. 16 (2007), pp. 495–502], we show that for any increasing property \mathcal {F} on a finite set X, \[ p_c(\mathcal {F})=O(q(\mathcal {F})\log \ell (\mathcal {F})), \] where p_c(\mathcal {F}) and q(\mathcal {F}) are the threshold and "expectation threshold" of \mathcal {F}, and \ell (\mathcal {F}) is the maximum of 2 and the maximum size of a minimal member of \mathcal {F}. [ABSTRACT FROM AUTHOR]

Our basic result, an isoperimetric inequality for Hamming cube Qn, can be written: ∫hAβdμ ≥ 2μ (A)(1−μ (A)). Here μ is uniform measure on V = {0,1\}n (= V(Qn)); β = log2(3/2); and, for S ⊆ V and x ∈ V, hS(x) = {dV\S(x) if x ∈ S, 0 if x ∉ S (where dT(x) is the number of neighbors of x in T). This implies inequalities involving mixtures of edge and vertex boundaries, with related stability results, and suggests some more general possibilities. One application, a stability result for the set of edges connecting two disjoint subsets of V of size roughly |V|/2, is a key step in showing that the number of maximal independent sets in Qn is (1+o(1))2n exp 2[2n-2]. This asymptotic statement, whose proof will appear separately, was the original motivation for the present work. [ABSTRACT FROM AUTHOR]

Resolving a conjecture of Kühn and Osthus from 2012, we show that p = 1/√n is the threshold for the random graph Gn,p to contain the square of a Hamilton cycle. [ABSTRACT FROM AUTHOR]