Determining the maximum size of a $t$-intersecting code in $[m]^n$ was a longstanding open problem of Frankl and Furedi, solved independently by Ahlswede and Khachatrian and by Frankl and Tokushige. We extend their result to the setting of forbidden
intersections, by showing that for any $m>2$ and $n$ large compared with $t$ (but not necessarily $m$) that the same bound holds for codes with the weaker property of being $(t-1)$-avoiding, i.e. having no two vectors that agree on exactly $t-1$ coordinates. Our proof proceeds via a junta approximation result of independent interest, which we prove via a development of our recent theory of global hypercontractivity: we show that any $(t-1)$-avoiding code is approximately contained in a $t$-intersecting junta (a code where membership is determined by a constant number of co-ordinates). In particular, when $t=1$ this gives an alternative proof of a recent result of Eberhard, Kahn, Narayanan and Spirkl that symmetric intersecting codes in $[m]^n$ have size $o(m^n)$.
The hypercontractive inequality on the discrete cube plays a crucial role in many fundamental results in the Analysis of Boolean functions, such as the KKL theorem, Friedguts junta theorem and the invariance principle. In these results the cube is eq
uipped with the uniform measure, but it is desirable, particularly for applications to the theory of sharp thresholds, to also obtain such results for general $p$-biased measures. However, simple examples show that when $p = o(1)$, there is no hypercontractive inequality that is strong enough. In this paper, we establish an effective hypercontractive inequality for general $p$ that applies to `global functions, i.e. functions that are not significantly affected by a restriction of a small set of coordinates. This class of functions appears naturally, e.g. in Bourgains sharp threshold theorem, which states that such functions exhibit a sharp threshold. We demonstrate the power of our tool by strengthening Bourgains theorem, thereby making progress on a conjecture of Kahn and Kalai and by establishing a $p$-biased analog of the invariance principle. Our results have significant applications in Extremal Combinatorics. Here we obtain new results on the Turan number of any bounded degree uniform hypergraph obtained as the expansion of a hypergraph of bounded uniformity. These are asymptotically sharp over an essentially optimal regime for both the uniformity and the number of edges and solve a number of open problems in the area. In particular, we give general conditions under which the crosscut parameter asymptotically determines the Turan number, answering a question of Mubayi and Verstraete. We also apply the Junta Method to refine our asymptotic results and obtain several exact results, including proofs of the Huang--Loh--Sudakov conjecture on cross matchings and the Furedi--Jiang--Seiver conjecture on path expansions.
In this note we investigate correlation inequalities for `up-sets of permutations, in the spirit of the Harris--Kleitman inequality. We focus on two well-studied partial orders on $S_n$, giving rise to differing notions of up-sets. Our first result s
hows that, under the strong Bruhat order on $S_n$, up-sets are positively correlated (in the Harris--Kleitman sense). Thus, for example, for a (uniformly) random permutation $pi$, the event that no point is displaced by more than a fixed distance $d$ and the event that $pi$ is the product of at most $k$ adjacent transpositions are positively correlated. In contrast, under the weak Bruhat order we show that this completely fails: surprisingly, there are two up-sets each of measure $1/2$ whose intersection has arbitrarily small measure. We also prove analogous correlation results for a class of non-uniform measures, which includes the Mallows measures. Some applications and open problems are discussed.
The classical hypercontractive inequality for the noise operator on the discrete cube plays a crucial role in many of the fundamental results in the Analysis of Boolean functions, such as the KKL (Kahn-Kalai-Linial) theorem, Friedguts junta theorem a
nd the invariance principle of Mossel, ODonnell and Oleszkiewicz. In these results the cube is equipped with the uniform ($1/2$-biased) measure, but it is desirable, particularly for applications to the theory of sharp thresholds, to also obtain such results for general $p$-biased measures. However, simple examples show that when $p$ is small there is no hypercontractive inequality that is strong enough for such applications. In this paper, we establish an effective hypercontractivity inequality for general $p$ that applies to `global functions, i.e. functions that are not significantly affected by a restriction of a small set of coordinates. This class of functions appears naturally, e.g. in Bourgains sharp threshold theorem, which states that such functions exhibit a sharp threshold. We demonstrate the power of our tool by strengthening Bourgains theorem, thereby making progress on a conjecture of Kahn and Kalai. An additional application of our hypercontractivity theorem, is a $p$-biased analog of the seminal invariance principle of Mossel, ODonnell, and Oleszkiewicz. In a companion paper, we give applications to the solution of two open problems in Extremal Combinatorics.
