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.
We extend the definitions of complexity measures of functions to domains such as the symmetric group. The complexity measures we consider include degree, approximate degree, decision tree complexity, sensitivity, block sensitivity, and a few others.
We show that these complexity measures are polynomially related for the symmetric group and for many other domains. To show that all measures but sensitivity are polynomially related, we generalize classical arguments of Nisan and others. To add sensitivity to the mix, we reduce to Huangs sensitivity theorem using pseudo-characters, which witness the degree of a function. Using similar ideas, we extend the characterization of Boolean degree 1 functions on the symmetric group due to Ellis, Friedgut and Pilpel to the perfect matching scheme. As another application of our ideas, we simplify the characterization of maximum-size $t$-intersecting families in the symmetric group and the perfect matching scheme.
The hypercontractive inequality is a fundamental result in analysis, with many applications throughout discrete mathematics, theoretical computer science, combinatorics and more. So far, variants of this inequality have been proved mainly for product
spaces, which raises the question of whether analogous results hold over non-product domains. We consider the symmetric group, $S_n$, one of the most basic non-product domains, and establish hypercontractive inequalities on it. Our inequalities are most effective for the class of emph{global functions} on $S_n$, which are functions whose $2$-norm remains small when restricting $O(1)$ coordinates of the input, and assert that low-degree, global functions have small $q$-norms, for $q>2$. As applications, we show: 1. An analog of the level-$d$ inequality on the hypercube, asserting that the mass of a global function on low-degrees is very small. We also show how to use this inequality to bound the size of global, product-free sets in the alternating group $A_n$. 2. Isoperimetric inequalities on the transposition Cayley graph of $S_n$ for global functions, that are analogous to the KKL theorem and to the small-set expansion property in the Boolean hypercube. 3. Hypercontractive inequalities on the multi-slice, and stabili
A family of permutations $mathcal{F} subset S_{n}$ is said to be $t$-intersecting if any two permutations in $mathcal{F}$ agree on at least $t$ points. It is said to be $(t-1)$-intersection-free if no two permutations in $mathcal{F}$ agree on exactly
$t-1$ points. If $S,T subset {1,2,ldots,n}$ with $|S|=|T|$, and $pi: S to T$ is a bijection, the $pi$-star in $S_n$ is the family of all permutations in $S_n$ that agree with $pi$ on all of $S$. An $s$-star is a $pi$-star such that $pi$ is a bijection between sets of size $s$. Friedgut and Pilpel, and independently the first author, showed that if $mathcal{F} subset S_n$ is $t$-intersecting, and $n$ is sufficiently large depending on $t$, then $|mathcal{F}| leq (n-t)!$; this proved a conjecture of Deza and Frankl from 1977. Equality holds only if $mathcal{F}$ is a $t$-star. In this paper, we give a more `robust proof of a strengthening of the Deza-Frankl conjecture, namely that if $n$ is sufficiently large depending on $t$, and $mathcal{F} subset S_n$ is $(t-1)$-intersection-free, then $|mathcal{F} leq (n-t)!$, with equality only if $mathcal{F}$ is a $t$-star. The main ingredient of our proof is a `junta approximation result, namely, that any $(t-1)$-intersection-free family of permutations is essentially contained in a $t$-intersecting {em junta} (a `junta being a union of a bounded number of $O(1)$-stars). The proof of our junta approximation result relies, in turn, on a weak regularity lemma for families of permutations, a combinatorial argument that `bootstraps a weak notion of pseudorandomness into a stronger one, and finally a spectral argument for pairs of highly-pseudorandom fractional families. Our proof employs four different notions of pseudorandomness, three being combinatorial in nature, and one being algebraic.
The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta t
heorem give a strong characterization of such functions whenever the bound on the total influence is $o(log n)$. However, both results become useless when the total influence of the function is $omega(log n)$. The only case in which this logarithmic barrier has been broken for an interesting class of functions was proved by Bourgain and Kalai, who focused on functions that are symmetric under large enough subgroups of $S_n$. In this paper, we build and improve on the techniques of the Bourgain-Kalai paper and establish new concentration results on the Fourier spectrum of Boolean functions with small total influence. Our results include: 1. A quantitative improvement of the Bourgain--Kalai result regarding the total influence of functions that are transitively symmetric. 2. A slightly weaker version of the Fourier--Entropy Conjecture of Friedgut and Kalai. This weaker version implies in particular that the Fourier spectrum of a constant variance, Boolean function $f$ is concentrated on $2^{O(I[f]log I[f])}$ characters, improving an earlier result of Friedgut. Removing the $log I[f]$ factor would essentially resolve the Fourier--Entropy Conjecture, as well as settle a conjecture of Mansour regarding the Fourier spectrum of polynomial size DNF formulas. Our concentration result has new implications in learning theory: it implies that the class of functions whose total influence is at most $K$ is agnostically learnable in time $2^{O(Klog K)}$, using membership queries.
One powerful method for upper-bounding the largest independent set in a graph is the Hoffman bound, which gives an upper bound on the largest independent set of a graph in terms of its eigenvalues. It is easily seen that the Hoffman bound is sharp on
the tensor power of a graph whenever it is sharp for the original graph. In this paper, we introduce the related problem of upper-bounding independent sets in tensor powers of hypergraphs. We show that many of the prominent open problems in extremal combinatorics, such as the Turan problem for (hyper-)graphs, can be encoded as special cases of this problem. We also give a new generalization of the Hoffman bound for hypergraphs which is sharp for the tensor power of a hypergraph whenever it is sharp for the original hypergraph. As an application of our Hoffman bound, we make progress on the problem of Frankl on families of sets without extended triangles from 1990. We show that if $frac{1}{2}nle2klefrac{2}{3}n,$ then the extremal family is the star, i.e. the family of all sets that contains a given element. This covers the entire range in which the star is extremal. As another application, we provide spectral proofs for Mantels theorem on triangle-free graphs and for Frankl-Tokushige theorem on $k$-wise intersecting families.
A function $fcolon{0,1}^nto {0,1}$ is called an approximate AND-homomorphism if choosing ${bf x},{bf y}in{0,1}^n$ randomly, we have that $f({bf x}land {bf y}) = f({bf x})land f({bf y})$ with probability at least $1-epsilon$, where $xland y = (x_1land
y_1,ldots,x_nland y_n)$. We prove that if $fcolon {0,1}^n to {0,1}$ is an approximate AND-homomorphism, then $f$ is $delta$-close to either a constant function or an AND function, where $delta(epsilon) to 0$ as $epsilonto0$. This improves on a result of Nehama, who proved a similar statement in which $delta$ depends on $n$. Our theorem implies a strong result on judgement aggregation in computational social choice. In the language of social choice, our result shows that if $f$ is $epsilon$-close to satisfying judgement aggregation, then it is $delta(epsilon)$-close to an oligarchy (the name for the AND function in social choice theory). This improves on Nehamas result, in which $delta$ decays polynomially with $n$. Our result follows from a more general one, in which we characterize approximate solutions to the eigenvalue equation $mathrm T f = lambda g$, where $mathrm T$ is the downwards noise operator $mathrm T f(x) = mathbb{E}_{{bf y}}[f(x land {bf y})]$, $f$ is $[0,1]$-valued, and $g$ is ${0,1}$-valued. We identify all exact solutions to this equation, and show that any approximate solution in which $mathrm T f$ and $lambda g$ are close is close to an exact solution.
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.
A family ${A_{0},ldots,A_{d}}$ of $k$-element subsets of $[n]={1,2,ldots,n}$ is called a simplex-cluster if $A_{0}capcdotscap A_{d}=varnothing$, $|A_{0}cupcdotscup A_{d}|le2k$, and the intersection of any $d$ of the sets in ${A_{0},ldots,A_{d}}$ is n
onempty. In 2006, Keevash and Mubayi conjectured that for any $d+1le klefrac{d}{d+1}n$, the largest family of $k$-element subsets of $[n]$ that does not contain a simplex-cluster is the family of all $k$-subsets that contain a given element. We prove the conjecture for all $kgezeta n$ for an arbitrarily small $zeta>0$, provided that $nge n_{0}(zeta,d)$. We call a family ${A_{0},ldots,A_{d}}$ of $k$-element subsets of $[n]$ a $(d,k,s)$-cluster if $A_{0}capcdotscap A_{d}=varnothing$ and $|A_{0}cupcdotscup A_{d}|le s$. We also show that for any $zeta nle klefrac{d}{d+1}n$ the largest family of $k$-element subsets of $[n]$ that does not contain a $(d,k,(frac{d+1}{d}+zeta)k)$-cluster is again the family of all $k$-subsets that contain a given element, provided that $nge n_{0}(zeta,d)$. Our proof is based on the junta method for extremal combinatorics initiated by Dinur and Friedgut and further developed by Ellis, Keller, and the author.
