Proof of an Intersection Theorem via Graph Homomorphisms

  • Irit Dinur
  • Ehud Friedgut

Abstract

Let $0 \leq p \leq 1/2 $ and let $\{0,1\}^n$ be endowed with the product measure $\mu_p$ defined by $\mu_p(x)=p^{|x|}(1-p)^{n-|x|}$, where $|x|=\sum x_i$. Let $I \subseteq \{0,1\}^n$ be an intersecting family, i.e. for every $x, y \in I$ there exists a coordinate $1 \leq i \leq n$ such that $x_i=y_i=1$. Then $\mu_p(I) \leq p.$

Our proof uses measure preserving homomorphisms between graphs.

Published
2006-03-21
Article Number
N6