Source author record

Jeff Kahn

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.PR Discrete Mathematics math-ph math.MP

Catalog footprint

Research overview

27works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Hitting times for Shamir's Problem

For fixed $r\geq 3$ and $n$ divisible by $r$ , let ${\mathcal H}={\mathcal H}^r_{n,M}$ be the random $M$ -edge $r$ -graph on $V=\{1,\ldots ,n\}$ ; that is, ${\mathcal H}$ is chosen uniformly from the $M$ -subsets of ${\mathcal K}:={V \choose r}$ ($:= \{\mbox{$r $-subsets of$ V$}\}$). Shamir's Problem (circa 1980) asks, roughly, for what $M=M(n)$ is ${\mathcal H}$ 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$ , $P({\mathcal H} ~\mbox{contains a perfect matching})\rightarrow 1 \,\,\, \mbox{as $n\rightarrow\infty$}.$ The present work completes a proof, begun in that recent paper, of the definitive "hitting time" statement: $\mbox{Theorem.}$ If $A_1, \ldots ~$ is a uniform permutation of ${\mathcal K}$ , ${\mathcal H}_t=\{A_1\dots A_t\}$ , and $T=\min\{t:A_1\cup \cdots\cup A_t=V\},$ then $P({\mathcal H}_T ~\mbox{contains a perfect matching})\rightarrow 1 \,\,\, \mbox{as $n\rightarrow\infty$}$.

preprint2020arXiv

Tuza's Conjecture for random graphs

A celebrated conjecture of Zs. Tuza says that in any (finite) graph, the minimum size of a cover of triangles by edges is at most twice the maximum size of a set of edge-disjoint triangles. Resolving a recent question of Bennett, Dudek, and Zerbib, we show that this is true for random graphs; more precisely: \[ \mbox{for any $p=p(n)$, $\mathbb P(\mbox{$G_{n,p}$ satisfies Tuza's Conjecture})\rightarrow 1 $ (as $n\rightarrow\infty$).} \]

preprint2016arXiv

Chvátal's Conjecture and Correlation Inequalities

Chvátal's conjecture in extremal combinatorics asserts that for any decreasing family $\mathcal{F}$ of subsets of a finite set $S$ , there is a largest intersecting subfamily of $\mathcal{F}$ consisting of all members of $\mathcal{F}$ that include a particular $x \in S$ . In this paper we reformulate the conjecture in terms of influences of variables on Boolean functions and correlation inequalities, and study special cases and variants using tools from discrete Fourier analysis.

preprint2016arXiv

On Erdős-Ko-Rado for random hypergraphs II

Denote by $\mathcal{H}_k (n,p)$ the random $k$ -graph in which each $k$ -subset of $\{1... n\}$ is present with probability $p$ , independent of other choices. More or less answering a question of Balogh, Bohman and Mubayi, we show: there is a fixed $\varepsilon >0$ such that if $n=2k+1$ and $p> 1-\varepsilon$ , then w.h.p. (that is, with probability tending to 1 as $k\rightarrow \infty$ ), $\mathcal{H}_k (n,p)$ has the "Erdős-Ko-Rado property." We also mention a similar random version of Sperner's Theorem.

preprint2015arXiv

Modular statistics for subgraph counts in sparse random graphs

Answering a question of Kolaitis and Kopparty, we show that, for given integer $q>1$ and pairwise nonisomorphic connected graphs $G_1...G_k$ , if $p=p(n)$ is such that $\Pr(G_{n,p}\supseteq G_i)\to 1$ $\forall i$ , then, with $ξ_i$ the number of copies of $G_i$ in $G_{n,p}$ , $(ξ_1...ξ_k)$ is asymptotically uniformly distributed on ${\bf Z}_q^k$ .

preprint2015arXiv

On "stability" in the Erdős-Ko-Rado theorem

Denote by $K_p(n,k)$ the random subgraph of the usual Kneser graph $K(n,k)$ in which edges appear independently, each with probability $p$ . Answering a question of Bollobás, Narayanan, and Raigorodskii,we show that there is a fixed $p<1$ such that a.s. (i.e., with probability tending to 1 as $k \to \infty$ ) the maximum independent sets of $K_p(2k+1, k)$ are precisely the sets $\{A\in V(K(2k+1,k)): x\in A\}$ ( $x\in [2k+1]$ ). We also complete the determination of the order of magnitude of the "threshold" for the above property for general $k$ and $n\geq 2k+2$ . This is new for $k\sim n/2$ , while for smaller $k$ it is a recent result of Das and Tran.

preprint2015arXiv

Turán's Theorem for random graphs

For a graph $G$ , denote by $t_r(G)$ (resp. $b_r(G)$ ) the maximum size of a $K_r$ -free (resp. $(r-1)$ -partite) subgraph of $G$ . Of course $t_r(G) \geq b_r(G)$ for any $G$ , and Turán's Theorem says that equality holds for complete graphs. With $G_{n,p}$ the usual ("binomial" or "Erdős-Rényi") random graph, we show: For each fixed r there is a C such that if $p=p(n) > Cn^{-\tfrac{2}{r+1}}\log^{\tfrac{2}{(r+1)(r-2)}}n,$ then $\Pr(t_r(G_{n,p})=b_r(G_{n,p}))\rightarrow 1$ as $n\rightarrow\infty$ . This is best possible (apart from the value of $C$ ) and settles a question first considered by Babai, Simonovits and Spencer about 25 years ago.

preprint2014arXiv

Cycle factors and renewal theory

For which values of $k$ does a uniformly chosen $3$ -regular graph $G$ on $n$ vertices typically contain $n/k$ vertex-disjoint $k$ -cycles (a $k$ -cycle factor)? To date, this has been answered for $k=n$ and for $k \ll \log n$ ; the former, the Hamiltonicity problem, was finally answered in the affirmative by Robinson and Wormald in 1992, while the answer in the latter case is negative since with high probability most vertices do not lie on $k$ -cycles. Here we settle the problem completely: the threshold for a $k$ -cycle factor in $G$ as above is $κ_0 \log_2 n$ with $κ_0=[1-\frac12\log_2 3]^{-1}\approx 4.82$ . Precisely, we prove a 2-point concentration result: if $k \geq κ_0 \log_2(2n/e)$ divides $n$ then $G$ contains a $k$ -cycle factor w.h.p., whereas if $k<κ_0\log_2(2n/e)-\frac{\log^2 n}n$ then w.h.p. it does not. As a byproduct, we confirm the "Comb Conjecture," an old problem concerning the embedding of certain spanning trees in the random graph $G(n,p)$ . The proof follows the small subgraph conditioning framework, but the associated second moment analysis here is far more delicate than in any earlier use of this method and involves several novel features, among them a sharp estimate for tail probabilities in renewal processes without replacement which may be of independent interest.

preprint2014arXiv

Influential coalitions for Boolean Functions

We improve results of Kahn, Kalai, and Linial from the late 80s on the existence of influential large coalitions for Boolean functions, and we give counterexamples to conjectures (of Benny Chor and others) also from the late 80s, by exhibiting functions for which the influences of large coalitions are unexpectedly small relative to the expectations of the functions. The large gaps between the new upper and lower bounds leave a lot of room for further study.

preprint2014arXiv

On Erdős-Ko-Rado for random hypergraphs I

A family of sets is intersecting if no two of its members are disjoint, and has the Erdős-Ko-Rado property (or is EKR) if each of its largest intersecting subfamilies has nonempty intersection. Denote by $\mathcal{H}_k(n,p)$ the random family in which each $k$ -subset of $\{1\dots n\}$ is present with probability $p$ , independent of other choices. A question first studied by Balogh, Bohman and Mubayi asks: \[ \mbox{for what $p=p(n,k)$ is $\mathcal{H}_k(n,p)$ likely to be EKR?} \] Here, for fixed $c<1/4$ , and $k< \sqrt{cn\log n}$ we give a precise answer to this question, characterizing those sequences $p=p(n,k)$ for which $\Pr(\mathcal{H}_k(n,p) \textrm{ is EKR}) \rightarrow 1 \textrm{ as } n\rightarrow \infty.$

preprint2014arXiv

The threshold for combs in random graphs

For $k\mid n$ let $Comb_{n,k}$ denote the tree consisting of an $(n/k)$ -vertex path with disjoint $k$ -vertex paths beginning at each of its vertices. An old conjecture says that for any $k=k(n)$ the threshold for the random graph $G(n,p)$ to contain $Comb_{n,k}$ is at $p\asymp \frac{\log n}n$ . Here we verify this for $k \leq C\log n$ with any fixed $C>0$ . In a companion paper, using very different methods, we treat the complementary range, proving the conjecture for $k\geq κ_0 \log n$ (with $κ_0\approx 4.82$ ).

preprint2014arXiv

Thresholds and expectation-thresholds of monotone properties with small minterms

Let $N$ be a finite set, let $p \in (0,1)$ , and let $N_p$ denote a random binomial subset of $N$ where every element of $N$ is taken to belong to the subset independently with probability $p$ . This defines a product measure $μ_p$ on the power set of $N$ , where for $\mathcal{A} \subseteq 2^N$ $μ_p(\mathcal{A}) := Pr[N_p \in \mathcal{A}]$ . In this paper we study upward-closed families $\mathcal{A}$ for which all minimal sets in $\mathcal{A}$ have size at most $k$ , for some positive integer $k$ . We prove that for such a family $μ_p(\mathcal{A}) / p^k$ is a decreasing function, which implies a uniform bound on the coarseness of the thresholds of such families. We also prove a structure theorem which enables to identify in $\mathcal{A}$ either a substantial subfamily $\mathcal{A}_0$ for which the first moment method gives a good approximation of its measure, or a subfamily which can be well approximated by a family with all minimal sets of size strictly smaller than $k$ . Finally, we relate the (fractional) expectation threshold and the probability threshold of such a family, using duality of linear programming. This is related to the threshold conjecture of Kahn and Kalai.

preprint2013arXiv

A bipartite graph with non-unimodal independent set sequence

We show that the independent set sequence of a bipartite graph need not be unimodal.

preprint2013arXiv

Functions without influential coalitions

We give counterexamples to a conjecture of Benny Chor and another of the second author, both from the late 80s, by exhibiting functions for which the influences of large coalitions are unexpectedly small relative to the expectations of the functions.

preprint2012arXiv

Asymptotics of the Upper Matching Conjecture

We give upper bounds for the number $Φ_\ell(G)$ of matchings of size $\ell$ in (i) bipartite graphs $G=(X\cup Y, E)$ with specified degrees $d_x$ ( $x\in X$ ), and (ii) general graphs $G=(V,E)$ with all degrees specified. In particular, for $d$ -regular, $N$ -vertex graphs, our bound is best possible up to an error factor of the form $\exp[o_d(1)N]$ , where $o_d(1) \rightarrow 0$ as $d \rightarrow \infty$ . This represents the best progress to date on the "Upper Matching Conjecture" of Friedland, Krop, Lundow and Markström. Some further possibilities are also suggested.

preprint2012arXiv

Counting maximal antichains and independent sets

Answering several questions of Duffus, Frankl and Rödl, we give asymptotics for the logarithms of (i) the number of maximal antichains in the n-dimensional Boolean algebra and (ii) the numbers of maximal independent sets in the covering graph of the n-dimensional hypercube and certain natural subgraphs thereof. The results in (ii) are implied by more general upper bounds on the numbers of maximal independent sets in regular and biregular graphs. We also mention some stronger possibilities involving actual rather than logarithmic asymptotics.

preprint2012arXiv

Mantel's Theorem for random graphs

For a graph $G$ , denote by $t(G)$ (resp. $b(G)$ ) the maximum size of a triangle-free (resp. bipartite) subgraph of $G$ . Of course $t(G) \geq b(G)$ for any $G$ , and a classic result of Mantel from 1907 (the first case of Turán's Theorem) says that equality holds for complete graphs. A natural question, first considered by Babai, Simonovits and Spencer about 20 years ago is, when (i.e. for what $p=p(n)$ ) is the "Erdős-Rényi" random graph $G=G(n,p)$ likely to satisfy $t(G) = b(G)$ ? We show that this is true if $p>C n^{-1/2} \log^{1/2}n$ for a suitable constant $C$ , which is best possible up to the value of $C$ .

preprint2012arXiv

On phase transition in the hard-core model on ${\bf Z}^d$

It is shown that the hard-core model on ${\bf Z}^d$ exhibits a phase transition at activities above some function $λ(d)$ which tends to zero as $d\rightarrow \infty$

preprint2012arXiv

On the triangle space of a random graph

Settling a first case of a conjecture of M. Kahle on the homology of the clique complex of the random graph $G=G_{n,p}$ , we show, roughly speaking, that (with high probability) the triangles of $G$ span its cycle space whenever each of its edges lies in a triangle (which happens (w.h.p.) when $p$ is at least about $\sqrt{(3/2)\ln n/n}$ , and not below this unless $p$ is very small.) We give two related proofs of this statement, together with a relatively simple proof of a fundamental "stability" theorem for triangle-free subgraphs of $G_{n,p}$ , originally due to Kohayakawa, Łuczak and Rödl, that underlies the first of our proofs.

preprint2012arXiv

Phase coexistence and torpid mixing in the 3-coloring model on Z^d

We show that for all sufficiently large d, the uniform proper 3-coloring model (in physics called the 3-state antiferromagnetic Potts model at zero temperature) on Z^d admits multiple maximal-entropy Gibbs measures. This is a consequence of the following combinatorial result: if a proper 3-coloring is chosen uniformly from a box in Z^d, conditioned on color 0 being given to all the vertices on the boundary of the box which are at an odd distance from a fixed vertex v in the box, then the probability that v gets color 0 is exponentially small in d. The proof proceeds through an analysis of a certain type of cutset separating v from the boundary of the box, and builds on techniques developed by Galvin and Kahn in their proof of phase transition in the hard-core model on Z^d. Building further on these techniques, we study local Markov chains for sampling proper 3-colorings of the discrete torus Z^d_n. We show that there is a constant ρ\approx 0.22 such that for all even n \geq 4 and d sufficiently large, if M is a Markov chain on the set of proper 3-colorings of Z^d_n that updates the color of at most ρn^d vertices at each step and whose stationary distribution is uniform, then the mixing time of M (the time taken for M to reach a distribution that is close to uniform, starting from an arbitrary coloring) is essentially exponential in n^{d-1}.

preprint2012arXiv

Upper Tails for Cliques

With $ξ_{k}=ξ_{k}^{n,p}$ the number of copies of $K_k$ in the usual (Erdős-Rényi) random graph $G(n,p)$ , $p\geq n^{-2/(k-1)}$ and $η>0$ , we show when $k>1$ $$\Pr(ξ_k> (1+η)\E ξ_k) < \exp [-\gO_{η,k} \min\{n^2p^{k-1}\log(1/p), n^kp^{\binom{k}{2}}\}].$$ This is tight up to the value of the constant in the exponent.

preprint2011arXiv

Upper tails for triangles

With $ξ$ the number of triangles in the usual (Erdős-Rényi) random graph $G(m,p)$ , $p>1/m$ and $η>0$ , we show (for some $C_η>0$ ) $$\Pr(ξ> (1+η)\E ξ) < \exp[-C_η\min{m^2p^2\log(1/p),m^3p^3}].$$ This is tight up to the value of $C_η$ .

preprint2010arXiv

Conditional negative association for competing urns

Competing urns refers to the random experiment where m balls are dropped, randomly and independently, into urns 1,...,n. Formally, we have a random map $σ$ from {1,...,m} to {1,...,n} with the $σ(i)$ 's i.i.d. With $x_j$ the indicator of the event that at least $t_j$ balls land in urn j (for some threshold $t_j$ ), we prove conditional negative association for the random variables $x_1,...,x_n$ . We mostly deal with the more general situation in which the $σ(i)$ 's need not be identically distributed, proving results which imply conditional negative association in the i.i.d. case. Some of the results--particularly Lemma 8 on graph orientations--are thought to be of independent interest. We also give a counterexample to a negative correlation conjecture of D. Welsh, a strong version of a (still open) conjecture of G. Farr.

preprint2010arXiv

Left and right convergence of graphs with bounded degree

The theory of convergent graph sequences has been worked out in two extreme cases, dense graphs and bounded degree graphs. One can define convergence in terms of counting homomorphisms from fixed graphs into members of the sequence (left-convergence), or counting homomorphisms into fixed graphs (right-convergence). Under appropriate conditions, these two ways of defining convergence was proved to be equivalent in the dense case by Borgs, Chayes, Lovász, Sós and Vesztergombi. In this paper a similar equivalence is established in the bounded degree case. In terms of statistical physics, the implication that left convergence implies right convergence means that for a left-convergent sequence, partition functions of a large class of statistical physics models converge. The proof relies on techniques from statistical physics, like cluster expansion and Dobrushin Uniqueness.

preprint2010arXiv

On the Number of 2-SAT Functions

We give an alternative proof of a conjecture of Bollobás, Brightwell and Leader, first proved by Peter Allen, stating that the number of boolean functions definable by 2-SAT formulae is $(1+o(1))2^{\binom{n+1}{2}}$ . One step in the proof determines the asymptotics of the number of "odd-blue-triangle-free" graphs on $n$ vertices.

preprint2010arXiv

The number of 3-SAT functions

With $G_k(n)$ the number of functions of $n$ boolean variables definable by $k$ -SAT formulae, we prove that $G_3(n)$ is asymptotic to $2^{n+\binom{n}{3}}$ . This is a strong form of the case $k=3$ of a conjecture of Bollobás, Brightwell and Leader stating that for fixed $k$ , $\log_2 G_k(n)\sim \binom{n}{k}$ .

preprint2007arXiv

Positive association in the fractional fuzzy Potts model

A fractional fuzzy Potts measure is a probability distribution on spin configurations of a finite graph $G$ obtained in two steps: first a subgraph of $G$ is chosen according to a random cluster measure $ϕ_{p,q}$ , and then a spin ( $\pm1$ ) is chosen independently for each component of the subgraph and assigned to all vertices of that component. We show that whenever $q\geq1$ , such a measure is positively associated, meaning that any two increasing events are positively correlated. This generalizes earlier results of Häggström [Ann. Appl. Probab. 9 (1999) 1149--1159] and Häggström and Schramm [Stochastic Process. Appl. 96 (2001) 213--242].

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jeff Kahn

Research overview

Is this your work?

27 publications

Hitting times for Shamir's Problem

Tuza's Conjecture for random graphs

Chvátal's Conjecture and Correlation Inequalities

On Erdős-Ko-Rado for random hypergraphs II

Modular statistics for subgraph counts in sparse random graphs

On "stability" in the Erdős-Ko-Rado theorem

Turán's Theorem for random graphs

Cycle factors and renewal theory

Influential coalitions for Boolean Functions

On Erdős-Ko-Rado for random hypergraphs I

The threshold for combs in random graphs

Thresholds and expectation-thresholds of monotone properties with small minterms

A bipartite graph with non-unimodal independent set sequence

Functions without influential coalitions

Asymptotics of the Upper Matching Conjecture

Counting maximal antichains and independent sets

Mantel's Theorem for random graphs

On phase transition in the hard-core model on ${\bf Z}^d$

On the triangle space of a random graph

Phase coexistence and torpid mixing in the 3-coloring model on Z^d

Upper Tails for Cliques

Upper tails for triangles

Conditional negative association for competing urns

Left and right convergence of graphs with bounded degree

On the Number of 2-SAT Functions

The number of 3-SAT functions

Positive association in the fractional fuzzy Potts model

See the researcher in context

Building this map preview

Jeff Kahn

Research overview

Is this your work?

27 publications

Hitting times for Shamir's Problem

Tuza's Conjecture for random graphs

Chvátal's Conjecture and Correlation Inequalities

On Erdős-Ko-Rado for random hypergraphs II

Modular statistics for subgraph counts in sparse random graphs

On "stability" in the Erdős-Ko-Rado theorem

Turán's Theorem for random graphs

Cycle factors and renewal theory

Influential coalitions for Boolean Functions

On Erdős-Ko-Rado for random hypergraphs I

The threshold for combs in random graphs

Thresholds and expectation-thresholds of monotone properties with small minterms

A bipartite graph with non-unimodal independent set sequence

Functions without influential coalitions

Asymptotics of the Upper Matching Conjecture

Counting maximal antichains and independent sets

Mantel's Theorem for random graphs

On phase transition in the hard-core model on Zd{\bf Z}^dZd

On the triangle space of a random graph

Phase coexistence and torpid mixing in the 3-coloring model on Z^d

Upper Tails for Cliques

Upper tails for triangles

Conditional negative association for competing urns

Left and right convergence of graphs with bounded degree

On the Number of 2-SAT Functions

The number of 3-SAT functions

Positive association in the fractional fuzzy Potts model

See the researcher in context

Building this map preview

On phase transition in the hard-core model on ${\bf Z}^d$