NKNathan Keller

Nathan Keller

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Nathan Keller has a total of 6 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Stability for the complete intersection theorem, and the forbidden intersection problem of Erdős and Sós

    by David Ellis, Nathan Keller, Noam Lifshitz

    A family \mathcal{F} of sets is said to be t-intersecting if |A \cap B| \geq t for any A,B \in \mathcal{F} . The seminal Complete Intersection Theorem of Ahlswede and Khachatrian (1997) gives the maximal size f(n,k,t) of a t -intersecting family of k -element subsets of [n]=\{1,\ldots,n\} , together with a characterisation of the extremal families, solving a longstanding problem of Frankl. The forbidden intersection problem , posed by Erdős and Sós in 1971, asks for a determination of the maximal size g(n,k,t) of a family \mathcal{F} of k -element subsets of [n] such that |A \cap B| \neq t-1 for any A,B \in \mathcal{F} . In this paper, we show that for any fixed t \in \mathbb{N} , if o(n) \leq k \leq n/2-o(n) , then g(n,k,t)=f(n,k,t) . In combination with prior results, this solves the problem of Erdős and Sós for any constant t , except for the ranges n/2-o(n) < k < n/2+t/2 and k < 2t . One key ingredient of the proof is the following sharp ‘stability’ result for the Complete Intersection Theorem: if k/n is bounded away from 0 and 1/2 , and \mathcal{F} is a t -intersecting family of k -element subsets of [n] such that |\mathcal{F}| \geq f(n,k,t) - O(\binom{n-d}{k}) , then there exists a family \mathcal{G} such that \mathcal{G} is extremal for the Complete Intersection Theorem, and |\mathcal{F} \setminus \mathcal{G}| = O(\binom{n-d}{k-d}) . This proves a conjecture of Friedgut (2008). We prove the result by combining classical ‘shifting’ arguments with a ‘bootstrapping’ method based upon an isoperimetric inequality. Another key ingredient is a ‘weak regularity lemma’ for families of k -element subsets of [n] , where k/n is bounded away from 0 and 1. This states that any such family \mathcal{F} is approximately contained within a ‘junta’ such that the restriction of \mathcal{F} to each subcube determined by the junta is ‘pseudorandom’ in a certain sense.


  • Open Access

    A structure theorem for almost low-degree functions on the slice

    by Nathan Keller, Ohad Klein

    The Fourier-Walsh expansion of a Boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ is its unique representation as a multilinear polynomial. The Kindler-Safra theorem (2002) asserts that if in the expansion of $f$, the total weight on coefficients beyond degree $k$ is very small, then $f$ can be approximated by a Boolean-valued function depending on at most $O(2^k)$ variables. In this paper we prove a similar theorem for Boolean functions whose domain is the `slice' ${{[n]}\choose{pn}} = \{x \in \{0,1\}^n\colon \sum_i x_i = pn\}$, where $0 \ll p \ll 1$, with respect to their unique representation as harmonic multilinear polynomials. We show that if in the representation of $f\colon {{[n]}\choose{pn}} \rightarrow \{0,1\}$, the total weight beyond degree $k$ is at most $\epsilon$, where $\epsilon = \min(p, 1-p)^{O(k)}$, then $f$ can be $O(\epsilon)$-approximated by a degree-$k$ Boolean function on the slice, which in turn depends on $O(2^{k})$ coordinates. This proves a conjecture of Filmus, Kindler, Mossel, and Wimmer (2015). Our proof relies on hypercontractivity, along with a novel kind of a shifting procedure. In addition, we show that the approximation rate in the Kindler-Safra theorem can be improved from $\epsilon + \exp(O(k)) \epsilon^{1/4}$ to $\epsilon+\epsilon^2 (2\ln(1/\epsilon))^k/k!$, which is tight in terms of the dependence on $\epsilon$ and misses at most a factor of $2^{O(k)}$ in the lower-order term.

  • Open Access

    A Note on Large H-Intersecting Families

    by Nathan Keller, Noam Lifshitz

    A family $F$ of graphs on a fixed set of $n$ vertices is called triangle-intersecting if for any $G_1,G_2 \in F$, the intersection $G_1 \cap G_2$ contains a triangle. More generally, for a fixed graph $H$, a family $F$ is $H$-intersecting if the intersection of any two graphs in $F$ contains a sub-graph isomorphic to $H$. In [D. Ellis, Y. Filmus, and E. Friedgut, Triangle-intersecting families of graphs, J. Eur. Math. Soc. 14 (2012), pp. 841--885], Ellis, Filmus and Friedgut proved a 36-year old conjecture of Simonovits and S\'{o}s stating that the maximal size of a triangle-intersecting family is $(1/8)2^{n(n-1)/2}$. Furthermore, they proved a $p$-biased generalization, stating that for any $p \leq 1/2$, we have $\mu_{p}(F)\le p^{3}$, where $\mu_{p}(F)$ is the probability that the random graph $G(n,p)$ belongs to $F$. In the same paper, Ellis et al. conjectured that the assertion of their biased theorem holds also for $1/2 < p \le 3/4$, and more generally, that for any non-$t$-colorable graph $H$ and any $H$-intersecting family $F$, we have $\mu_{p}(F)\le p^{t(t+1)/2}$ for all $p \leq (2t-1)/(2t)$. In this note we construct, for any fixed $H$ and any $p>1/2$, an $H$-intersecting family $F$ of graphs such that $\mu_{p}(F)\ge 1-e^{-n^{2}/C}$, where $C$ depends only on $H$ and $p$, thus disproving both conjectures.

  • Open Access

    On a biased edge isoperimetric inequality for the discrete cube

    by David Ellis, Nathan Keller, Noam Lifshitz

    The `full' edge isoperimetric inequality for the discrete cube (due to Harper, Bernstein, Lindsay and Hart) specifies the minimum size of the edge boundary $\partial A$ of a set $A \subset \{0,1\}^n$, as a function of $|A|$. A weaker (but more widely-used) lower bound is $|\partial A| \geq |A| \log_2(2^n/|A|)$, where equality holds iff $A$ is a subcube. In 2011, the first author obtained a sharp `stability' version of the latter result, proving that if $|\partial A| \leq |A| (\log(2^n/|A|)+\epsilon)$, then there exists a subcube $C$ such that $|A \Delta C|/|A| = O(\epsilon /\log(1/\epsilon))$. The `weak' version of the edge isoperimetric inequality has the following well-known generalization for the `$p$-biased' measure $\mu_p$ on the discrete cube: if $p \leq 1/2$, or if $0 < p < 1$ and $A$ is monotone increasing, then $p\mu_p(\partial A) \geq \mu_p(A) \log_p(\mu_p(A))$. In this paper, we prove a sharp stability version of the latter result, which generalizes the aforementioned result of the first author. Namely, we prove that if $p\mu_p(\partial A) \leq \mu_p(A) (\log_p(\mu_p(A))+\epsilon)$, then there exists a subcube $C$ such that $\mu_p(A \Delta C)/\mu_p(A) = O(\epsilon' /\log(1/\epsilon'))$, where $\epsilon' =\epsilon \ln (1/p)$. This result is a central component in recent work of the authors proving sharp stability versions of a number of Erd\H{o}s-Ko-Rado type theorems in extremal combinatorics, including the seminal `complete intersection theorem' of Ahlswede and Khachatrian. In addition, we prove a biased-measure analogue of the `full' edge isoperimetric inequality, for monotone increasing sets, and we observe that such an analogue does not hold for arbitrary sets, hence answering a question of Kalai. We use this result to give a new proof of the `full' edge isoperimetric inequality, one relying on the Kruskal-Katona theorem.

  • Open Access

    Approximation of biased Boolean functions of small total influence by DNF's

    by Nathan Keller, Noam Lifshitz

    The influence of the $k$'th coordinate on a Boolean function $f:\{0,1\}^n \rightarrow \{0,1\}$ is the probability that flipping $x_k$ changes the value $f(x)$. The total influence $I(f)$ is the sum of influences of the coordinates. The well-known `Junta Theorem' of Friedgut (1998) asserts that if $I(f) \leq M$, then $f$ can be $\epsilon$-approximated by a function that depends on $O(2^{M/\epsilon})$ coordinates. Friedgut's theorem has a wide variety of applications in mathematics and theoretical computer science. For a biased function with $E[f]=\mu$, the edge isoperimetric inequality on the cube implies that $I(f) \geq 2\mu \log(1/\mu)$. Kahn and Kalai (2006) asked, in the spirit of the Junta theorem, whether any $f$ such that $I(f)$ is within a constant factor of the minimum, can be $\epsilon \mu$-approximated by a DNF of a `small' size (i.e., a union of a small number of sub-cubes). We answer the question by proving the following structure theorem: If $I(f) \leq 2\mu(\log(1/\mu)+M)$, then $f$ can be $\epsilon \mu$-approximated by a DNF of size $2^{2^{O(M/\epsilon)}}$. The dependence on $M$ is sharp up to the constant factor in the double exponent.

  • Open Access

    Stability versions of Erdős-Ko-Rado type theorems, via isoperimetry

    by David Ellis, Nathan Keller, Noam Lifshitz

    Erd\H{o}s-Ko-Rado (EKR) type theorems yield upper bounds on the sizes of families of sets, subject to various intersection requirements on the sets in the family. `Stability' versions of such theorems assert that if the size of a family is `close' to the maximum possible size, then the family itself must be `close' (in some appropriate sense) to a maximum-sized family. In this paper, we present an approach to obtaining stability versions of EKR-type theorems, via isoperimetric inequalities for subsets of the hypercube. Our approach is rather general, and allows the leveraging of a wide variety of `exact' EKR-type results into strong stability versions of these results, without going into the proofs of the original results. We use this approach to obtain tight stability versions of the EKR theorem itself and of the Ahlswede-Khachatrian theorem on $t$-intersecting families of $k$-element subsets of $\{1,2,\ldots.n\}$ (for $k < \frac{n}{t+1}$), and to show that, somewhat surprisingly, all these results hold when the `intersection' requirement is replaced by a much weaker requirement. Other examples include stability versions of Frankl's recent result on the Erd\H{o}s matching conjecture, the Ellis-Filmus-Friedgut proof of the Simonovits-S\'{o}s conjecture, and various EKR-type results on $r$-wise (cross)-$t$-intersecting families.