Jeff Kahn
Research Subjects
Research Interests
Jeff Kahn has a total of 61 co-authors. Here are the top co-authors by number of shared publications:
- Bobby DeMarco
Department of Mathematics, Rutgers University, Piscataway, New Jersey 08854
7 shared publications - Bhargav Narayanan
Department of Mathematics, Rutgers University, Piscataway, USA
6 shared publications - Jinyoung Park
Department of Mathematics Courant Institute of Mathematical Sciences, New York University New York NY UK
5 shared publications - Gil Kalai
Einstein Institute of Mathematics Hebrew University 91904 Jerusalem Israel
4 shared publications - Nicholas Wormald
School of Mathematics Department of Combinatorics and Optimization School of Mathematics Monash University University of Waterloo Monash University
4 shared publications Pat Devlin
Rutgers University
4 shared publications
Latest Publications
- Open Access
On the "second" Kahn--Kalai Conjecture
We make progress on a conjecture of Kahn and Kalai, the original (stronger but less general) version of what became known as the ``Kahn-Kalai Conjecture" (KKC; now a theorem of Park and Pham). This ``second" KKC concerns the threshold, $p_c(H)$, for $G_{n,p}$ to contain a copy of a given graph $H$, predicting $p_c(H) = O(p_{\mathbb E}(H)\log n)$, where $p_{\mathbb E}$ is an easy lower bound on $p_c$. What we actually show is $p_{\mathbb E}^*(H)=O(p_{\mathbb E}(H)\log ^2n)$, where $p_{\mathbb E}^*$, the fractional expectation threshold, is a larger lower bound suggested by Talagrand. When combined with Talagrand's fractional relaxation of the KKC (now a theorem of Frankston, Kahn, Narayanan and Park), this gives $p_c(H)=O(p_{\mathbb E}(H)\log^3 n)$. (The second KKC would follow similarly if one could remove the log factors from the above bound on $p_{\mathbb E}^*$.)Open AccessOn the "second" Kahn--Kalai Conjecture
We make progress on a conjecture of Kahn and Kalai, the original (stronger but less general) version of what became known as the ``Kahn-Kalai Conjecture" (KKC; now a theorem of Park and Pham). This ``second" KKC concerns the threshold, $p_c(H)$, for $G_{n,p}$ to contain a copy of a given graph $H$, predicting $p_c(H) = O(p_{\mathbb E}(H)\log n)$, where $p_{\mathbb E}$ is an easy lower bound on $p_c$. What we actually show is $p_{\mathbb E}^*(H)=O(p_{\mathbb E}(H)\log ^2n)$, where $p_{\mathbb E}^*$, the fractional expectation threshold, is a larger lower bound suggested by Talagrand. When combined with Talagrand's fractional relaxation of the KKC (now a theorem of Frankston, Kahn, Narayanan and Park), this gives $p_c(H)=O(p_{\mathbb E}(H)\log^3 n)$. (The second KKC would follow similarly if one could remove the log factors from the above bound on $p_{\mathbb E}^*$.) - Open Access
Note on a conjecture of Talagrand: expectation thresholds vs. fractional expectation thresholds
We show that a restricted version of a conjecture of M. Talagrand on the relation between "expectation thresholds" and "fractional expectation thresholds" follows easily from a strong version of a second conjecture of Talagrand, on "selector processes." The selector process conjecture was proved by Park and Pham, and the quantitative strengthening used here is due to Bednorz, Martynek, and Meller.
Open AccessNote on a conjecture of Talagrand: expectation thresholds vs. fractional expectation thresholds
We show that a restricted version of a conjecture of M. Talagrand on the relation between "expectation thresholds" and "fractional expectation thresholds" follows easily from a strong version of a second conjecture of Talagrand, on "selector processes." The selector process conjecture was proved by Park and Pham, and the quantitative strengthening used here is due to Bednorz, Martynek, and Meller.
- Open Access
On the $H$-space of a random graph
The edge space $\mathcal{E}(G)$ of a graph $G$ is the vector space $\mathbb{F}_2^{E(G)}$ with members naturally identified with subgraphs of $G$, and the $H$-space is the subspace $\mathcal{C}_H(G)$ of $ \mathcal{E}(G)$ spanned by copies of the graph $H$. We are interested in when the random graph $G = G_{n,p}$ is likely to satisfy \[\mathcal{C}_H(G) = \mathcal{W}_H(G),\] where $\mathcal{W}_H(G)$ takes one of four natural values, depending on the value of $\mathcal{C}_H(K_n)$. We show that for strictly $2$-balanced $H$, w.h.p. the above equality holds whenever every edge of $G$ is in a copy of $H$.Open AccessOn the $H$-space of a random graph
The edge space $\mathcal{E}(G)$ of a graph $G$ is the vector space $\mathbb{F}_2^{E(G)}$ with members naturally identified with subgraphs of $G$, and the $H$-space is the subspace $\mathcal{C}_H(G)$ of $ \mathcal{E}(G)$ spanned by copies of the graph $H$. We are interested in when the random graph $G = G_{n,p}$ is likely to satisfy \[\mathcal{C}_H(G) = \mathcal{W}_H(G),\] where $\mathcal{W}_H(G)$ takes one of four natural values, depending on the value of $\mathcal{C}_H(K_n)$. We show that for strictly $2$-balanced $H$, w.h.p. the above equality holds whenever every edge of $G$ is in a copy of $H$. - Open Access
Asymptotics for Palette Sparsification
It is shown that the following holds for each $\varepsilon>0$. For $G$ an $n$-vertex graph of maximum degree $D$ and "lists" $L_v$ ($v \in V(G)$) chosen independently and uniformly from the ($(1+\varepsilon)\ln n$)-subsets of $\{1, ..., D+1\}$, \[ G \text{ admits a proper coloring } σ\text{ with } σ_v \in L_v \forall v \] with probability tending to 1 as $D \to \infty$. This is an asymptotically optimal version of a recent "palette sparsification" theorem of Assadi, Chen, and Khanna.Open AccessAsymptotics for Palette Sparsification
It is shown that the following holds for each $\varepsilon>0$. For $G$ an $n$-vertex graph of maximum degree $D$ and "lists" $L_v$ ($v \in V(G)$) chosen independently and uniformly from the ($(1+\varepsilon)\ln n$)-subsets of $\{1, ..., D+1\}$, \[ G \text{ admits a proper coloring } σ\text{ with } σ_v \in L_v \forall v \] with probability tending to 1 as $D \to \infty$. This is an asymptotically optimal version of a recent "palette sparsification" theorem of Assadi, Chen, and Khanna. - 14 March 2022
- Published by Springer Nature in Combinatorica
- Vol. 42 (6) , 853-880
The Number of Maximal Independent Sets in the Hamming Cube
- 14 March 2022
- Published by Springer Nature in Combinatorica
- Vol. 42 (6) , 853-880
The Number of Maximal Independent Sets in the Hamming Cube
- 5 November 2021
- Published by American Mathematical Society (AMS) in Transactions of the American Mathematical Society
- Vol. 375 (01) , 627-668
Hitting times for Shamir’s problem
For fixed $r\geq 3$ and $n$ divisible by $r$, let $\boldsymbol {\mathcal {H}}=\boldsymbol {\mathcal {H}}^r_{n,M}$ be the random $M$-edge $r$-graph on $V=\{1,\ldots ,n\}$; that is, $\boldsymbol {\mathcal {H}}$ is chosen uniformly from the $M$-subsets of $\mathcal {K}≔{{V}\choose {r}}$ ($≔\{\text {$r$-subsets of$V$}\}$). Shamir’s Problem (circa 1980) asks, roughly, \[ \text {\emph {for what $\boldsymbol {M=M(n)}$ is }} \boldsymbol {\mathcal {H}} \text {\emph { likely to contain a perfect matching}} \] (that is, $n/r$ disjoint $r$-sets)? In 2008 Johansson, Vu and the author showed that this is true for $M>C_rn\log n$. More recently the author proved the asymptotically correct version of that result: for fixed $C> 1/r$ and $M> Cn\log n$, \[ \mathbb {P}(\boldsymbol {\mathcal {H}} ~\text {\emph {contains a perfect matching}})\rightarrow 1 \,\,\, \text {\emph {as} $n\rightarrow \infty $}. \] The present work completes a proof, begun in that recent paper, of the definitive “hitting time” statement: Theorem. If $A_1, \ldots ~$ is a uniform permutation of $\mathcal {K}$, $\boldsymbol {\mathcal {H}}_t=\{A_1,\ldots ,A_t\}$, and \[ T=\min \{t:A_1\cup \cdots \cup A_t=V\}, \] then $\mathbb {P}(\boldsymbol {\mathcal {H}}_T ~\text {contains a perfect matching})\rightarrow 1 \,\,\, \text {\emph {as}$n→∞$}$.- 5 November 2021
- Published by American Mathematical Society (AMS) in Transactions of the American Mathematical Society
- Vol. 375 (01) , 627-668
Hitting times for Shamir’s problem
For fixed $r\geq 3$ and $n$ divisible by $r$, let $\boldsymbol {\mathcal {H}}=\boldsymbol {\mathcal {H}}^r_{n,M}$ be the random $M$-edge $r$-graph on $V=\{1,\ldots ,n\}$; that is, $\boldsymbol {\mathcal {H}}$ is chosen uniformly from the $M$-subsets of $\mathcal {K}≔{{V}\choose {r}}$ ($≔\{\text {$r$-subsets of$V$}\}$). Shamir’s Problem (circa 1980) asks, roughly, \[ \text {\emph {for what $\boldsymbol {M=M(n)}$ is }} \boldsymbol {\mathcal {H}} \text {\emph { likely to contain a perfect matching}} \] (that is, $n/r$ disjoint $r$-sets)? In 2008 Johansson, Vu and the author showed that this is true for $M>C_rn\log n$. More recently the author proved the asymptotically correct version of that result: for fixed $C> 1/r$ and $M> Cn\log n$, \[ \mathbb {P}(\boldsymbol {\mathcal {H}} ~\text {\emph {contains a perfect matching}})\rightarrow 1 \,\,\, \text {\emph {as} $n\rightarrow \infty $}. \] The present work completes a proof, begun in that recent paper, of the definitive “hitting time” statement: Theorem. If $A_1, \ldots ~$ is a uniform permutation of $\mathcal {K}$, $\boldsymbol {\mathcal {H}}_t=\{A_1,\ldots ,A_t\}$, and \[ T=\min \{t:A_1\cup \cdots \cup A_t=V\}, \] then $\mathbb {P}(\boldsymbol {\mathcal {H}}_T ~\text {contains a perfect matching})\rightarrow 1 \,\,\, \text {\emph {as}$n→∞$}$.- 7 May 2021
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 149 (8) , 3201-3208
The threshold for the square of a Hamilton cycle
Resolving a conjecture of Kühn and Osthus from 2012, we show that p = 1 / n p= 1/\sqrt {n} is the threshold for the random graph G n , p G_{n,p} to contain the square of a Hamilton cycle.
- 7 May 2021
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 149 (8) , 3201-3208
The threshold for the square of a Hamilton cycle
Resolving a conjecture of Kühn and Osthus from 2012, we show that p = 1 / n p= 1/\sqrt {n} is the threshold for the random graph G n , p G_{n,p} to contain the square of a Hamilton cycle.
- 18 March 2021
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 30 (6) , 899-904
On symmetric intersecting families of vectors
A family of vectors in [k]n is said to be intersecting if any two of its elements agree on at least one coordinate. We prove, for fixed k ≥ 3, that the size of any intersecting subfamily of [k]n invariant under a transitive group of symmetries is o(kn), which is in stark contrast to the case of the Boolean hypercube (where k = 2). Our main contribution addresses limitations of existing technology: while there are now methods, first appearing in work of Ellis and the third author, for using spectral machinery to tackle problems in extremal set theory involving symmetry, this machinery relies crucially on the interplay between up-sets, biased product measures, and threshold behaviour in the Boolean hypercube, features that are notably absent in the problem considered here. To circumvent these barriers, introducing ideas that seem of independent interest, we develop a variant of the sharp threshold machinery that applies at the level of products of posets.
- 18 March 2021
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 30 (6) , 899-904
On symmetric intersecting families of vectors
A family of vectors in [k]n is said to be intersecting if any two of its elements agree on at least one coordinate. We prove, for fixed k ≥ 3, that the size of any intersecting subfamily of [k]n invariant under a transitive group of symmetries is o(kn), which is in stark contrast to the case of the Boolean hypercube (where k = 2). Our main contribution addresses limitations of existing technology: while there are now methods, first appearing in work of Ellis and the third author, for using spectral machinery to tackle problems in extremal set theory involving symmetry, this machinery relies crucially on the interplay between up-sets, biased product measures, and threshold behaviour in the Boolean hypercube, features that are notably absent in the problem considered here. To circumvent these barriers, introducing ideas that seem of independent interest, we develop a variant of the sharp threshold machinery that applies at the level of products of posets.
- Open Access
The threshold for the square of a Hamilton cycle
Resolving a conjecture of K\"uhn and Osthus from 2012, we show that $p= 1/\sqrt{n}$ is the threshold for the random graph $G_{n,p}$ to contain the square of a Hamilton cycle.Open AccessThe threshold for the square of a Hamilton cycle
Resolving a conjecture of K\"uhn and Osthus from 2012, we show that $p= 1/\sqrt{n}$ is the threshold for the random graph $G_{n,p}$ to contain the square of a Hamilton cycle. - Open Access
On symmetric intersecting families of vectors
A family of vectors $A \subset [k]^n$ is said to be intersecting if any two elements of $A$ agree on at least one coordinate. We prove, for fixed $k \ge 3$, that the size of a symmetric intersecting subfamily of $[k]^n$ is $o(k^n)$, which is in stark contrast to the case of the Boolean hypercube (where $k =2$). Our main contribution addresses limitations of existing technology: while there is now some spectral machinery, developed by Ellis and the third author, to tackle extremal problems in set theory involving symmetry, this machinery relies crucially on the interplay between up-sets and biased product measures on the Boolean hypercube, features that are notably absent in the problem at hand; here, we describe a method for circumventing these barriers.Open AccessOn symmetric intersecting families of vectors
A family of vectors $A \subset [k]^n$ is said to be intersecting if any two elements of $A$ agree on at least one coordinate. We prove, for fixed $k \ge 3$, that the size of a symmetric intersecting subfamily of $[k]^n$ is $o(k^n)$, which is in stark contrast to the case of the Boolean hypercube (where $k =2$). Our main contribution addresses limitations of existing technology: while there is now some spectral machinery, developed by Ellis and the third author, to tackle extremal problems in set theory involving symmetry, this machinery relies crucially on the interplay between up-sets and biased product measures on the Boolean hypercube, features that are notably absent in the problem at hand; here, we describe a method for circumventing these barriers.