Proof of an intersection theorem via graph homomorphisms

被引:0
作者
Dinur, I [1 ]
Friedgut, E
机构
[1] Hebrew Univ Jerusalem, Sch Comp Sci & Engn, Jerusalem, Israel
[2] Hebrew Univ Jerusalem, Inst Math, IL-91904 Jerusalem, Israel
关键词
intersecting families; product measure;
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let 0 <= p <= 1/2 and let {0,1}(n) be enclosed with the product measure mu(p) defined by mu(p)(x) = p(vertical bar x vertical bar) (1-p)(n-vertical bar x vertical bar), where vertical bar x vertical bar = Sigma x(i). Let I subset of {0,1}(n) be an intersecting family i.e. for every x,y epsilon I there exists a coordinate 1 <= i <= n such that x(i) = y(i) = 1. Then mu(p) (I) <= p. Our proof uses measure preserving homorphisms between graphs.
引用
收藏
页数:4
相关论文
共 5 条
[1]  
DINUR I, 2002, IN PRESS P 34 STOC
[2]   INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS [J].
ERDOS, P ;
RADO, R ;
KO, C .
QUARTERLY JOURNAL OF MATHEMATICS, 1961, 12 (48) :313-&
[3]   PROBABILITIES FOR INTERSECTING SYSTEMS AND RANDOM SUBSETS OF FINITE SETS [J].
FISHBURN, PC ;
FRANKL, P ;
FREED, D ;
LAGARIAS, JC ;
ODLYZKO, AM .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (01) :73-79
[4]   Weighted multiply intersecting families [J].
Frankl, P ;
Tokushige, N .
STUDIA SCIENTIARUM MATHEMATICARUM HUNGARICA, 2003, 40 (03) :287-291
[5]  
FRIEDGUT E, UNPUB MEASURE INTERS