A strong log-concavity property for measures on Boolean algebras (2009)
We introduce the antipodal pairs property for probability measures on finite Boolean algebras and prove that conditional versions imply strong forms of log-concavity. We give several applications of...
For a simple d-regular graph G, let M be chosen uniformly at random from the set of all matchings of G, and for x ∈ V (G) let p(x) be the probability that M does not cover x. We show that for large...
Abbreviated title: Entropy bounds (2008)
For a graph G = (V, E) and x: E → ℜ + satisfying � e∋v xe = 1 for each v ∈ V, set h(x) = � e xe log(1/xe) (with log = log 2). We show that for any n-vertex G, random (not necessarily...
Negative correlation and log-concavity (2007)
We give counterexamples and a few positive results related to several conjectures of R. Pemantle and D. Wagner concerning negative correlation and log-concavity properties for probability measures...
The Influence of Variables on Boolean Functions (Extended Abstract) (2007)
Jeff Kahn, Gil Kalai, Nathan Linial
This paper applies methods from harmonic analysis to prove some general theorems on boolean functions. The result that is easiest to describe says that "Boolean functions always have small...
Positive association in the fractional fuzzy Potts model (2007)
Kahn, Jeff, Weininger, Nicholas
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...
Thresholds and expectation thresholds (2006)
Consider a random graph G in G(n,p) and the graph property: G contains a copy of a specific graph H. (Note: H depends on n; a motivating example: H is a Hamiltonian cycle.) Let q be the minimal value...
Some Conditional Correlation Inequalities for Percolation and Related Processes (2004)
Berg, Jacob Van Den, Haggstrom, Olle, Kahn, Jeff
Consider ordinary bond percolation on a finite or countably infinite graph. Let s, t, a and b be vertices. An earlier paper proved the (nonintuitive) result that, conditioned on the event that there...
Inequality of Two Critical Probabilities for Percolation (2003)
Kahn, Jeff; Rutgers University, USA; Jkahn@math.rutgers.edu
We disprove a conjecture of Russ Lyons---that for every locally finite, connected graph G, the critical probability for (Bernoulli bond) percolation on G is equal to the "first moment method" lower...
independent sets and antichains: A new approach to Dedekind’s problem (2002)
Abstract. For n-regular, N-vertex bipartite graphs with bipartition A ∪ B, a precise bound is given for the sum over independent sets I of the quantity µ |I∩A | λ |I∩B |. (In other language,...
Computing Graph Properties By Randomized Subcube Partitions (2002)
Ehud Friedgut, Jeff Kahn, Avi Wigderson
We prove a new lower bound on the randomized decision tree complexity of monotone graph properties. For a monotone property A of graphs on n vertices, let p = p(A) denote the threshold probability of...
Computing Graph Properties by Randomized Subcube Partitions (2002)
Ehud Friedgut, Jeff Kahn, Avi Wigderson
We prove a new lower bound on the randomized decision tree complexity of monotone graph properties. For a monotone property A of graphs on n vertices, let p = p(A) denote the threshold probability of...
A dual version of Reimer’s inequality and a proof of Rudich’s conjecture (2000)
Jeff Kahn, Cliff Smyth, Michael Saks
We prove a dual version of the celebrated inequality of D. Reimer (a.k.a. the van den Berg-Kesten conjecture). We use the dual inequality to prove a combinatorialconjecture of S. Rudich motivated by...
A federal façade :--problems in the development of Russian federalism /--Jeff Kahn. (1999)
Thesis (D.Phil.)--University of Oxford, 1999.
A federal façade [microform] : problems in the development of Russian federalism / (1999)
BLDSC reference no.: D205831.
A counterexample to Borsuk's conjecture (1993)
Let $f(d)$ be the smallest number so that every set in $R^d$ of diameter 1 can be partitioned into $f(d)$ sets of diameter smaller than 1. Borsuk's conjecture was that $f(d)\! =\!d\!+\!1$. We prove...
The influence of variables on Boolean functions (1988)
Jeff Kahn, Gil Kalai, Nathan Linial
This paper applies methods from harmonic analysis to prove some general theorems on boolean functions. The result that is easiest to describe says that "Boolean functions always have small...
On the uniqueness of matroid representations over GF(4) (1988)
We determine when a matroid is uniquely representable over GF(4). In particular all 3-connected (GF(4)-representable) matroids have this property.