Journal article
Proof of an Intersection Theorem via Graph Homomorphisms
The Electronic journal of combinatorics, Vol.13(1), pp.1-4
21/Mar/2006
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.
Details
- Title
- Proof of an Intersection Theorem via Graph Homomorphisms
- Creators
- Irit Dinur - Hebrew University of JerusalemEhud Friedgut - Hebrew University of Jerusalem
- Resource Type
- Journal article
- Publication Details
- The Electronic journal of combinatorics, Vol.13(1), pp.1-4; 21/Mar/2006
- Number of pages
- 4
- Language
- English
- DOI
- https://doi.org/10.37236/1144
- Grant note
- Research supported in part by the Israel Science Foundation, grant no. 0329745.
- Record Identifier
- 993347067003596
Metrics
2 Record Views