Nathan Keller
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Nathan Keller has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Noam Lifshitz
Hebrew University of Jerusalem, Israel
8 shared publications - David Ellis
School of Mathematics University of Bristol Bristol UK
4 shared publications - Ohad Klein
Hebrew University of Jerusalem
2 shared publications Ehud Friedgut
1 shared publicationGil Kalai
1 shared publicationJeff Kahn
1 shared publication
Latest Publications
- Open Access
- 21 February 2024
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
- Vol. 26 (5) , 1611-1654
Stability for the complete intersection theorem, and the forbidden intersection problem of Erdős and Sós
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.
- 21 February 2024
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
- Vol. 26 (5) , 1611-1654
Open AccessStability for the complete intersection theorem, and the forbidden intersection problem of Erdős and Sós
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.
- 23 September 2020
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 240 (1) , 179-221
A structure theorem for almost low-degree functions on the slice
- 23 September 2020
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 240 (1) , 179-221
A structure theorem for almost low-degree functions on the slice
- 1 April 2019
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 163, 118-162
On a biased edge isoperimetric inequality for the discrete cube
- 1 April 2019
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 163, 118-162
On a biased edge isoperimetric inequality for the discrete cube
- Open Access
A structure theorem for almost low-degree functions on the slice
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 AccessA structure theorem for almost low-degree functions on the slice
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
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 AccessA Note on Large H-Intersecting Families
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. - 24 May 2018
- Published by Wiley in Bulletin of the London Mathematical Society
- Vol. 50 (4) , 667-679
Approximation of biased Boolean functions of small total influence by DNFs
- 24 May 2018
- Published by Wiley in Bulletin of the London Mathematical Society
- Vol. 50 (4) , 667-679
Approximation of biased Boolean functions of small total influence by DNFs
- 1 May 2018
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 156, 22-43
Chvátal's conjecture and correlation inequalities
- 1 May 2018
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 156, 22-43
Chvátal's conjecture and correlation inequalities
- Open Access
On a biased edge isoperimetric inequality for the discrete cube
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 AccessOn a biased edge isoperimetric inequality for the discrete cube
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
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 AccessApproximation of biased Boolean functions of small total influence by DNF's
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
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.Open AccessStability versions of Erdős-Ko-Rado type theorems, via isoperimetry
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.