首页 | 本学科首页   官方微博 | 高级检索  
     


Uniformly cross intersecting families
Authors:Noga Alon  Eyal Lubetzky
Affiliation:1.School of Mathematics,Institute for Advanced Study,Princeton,USA;2.Raymond and Beverly Sackler Faculty of Exact Sciences,Tel Aviv University,Tel Aviv,Israel;3.Theory Group of Microsoft Research,One Microsoft Way,Redmond,USA
Abstract:Let A and B denote two families of subsets of an n-element set. The pair (A,B) is said to be -cross-intersecting iff |AB|= for all AA and BB. Denote by P e (n) the maximum value of |A||B| over all such pairs. The best known upper bound on P e (n) is Θ(2 n ), by Frankl and R?dl. For a lower bound, Ahlswede, Cai and Zhang showed, for all n ≥ 2, a simple construction of an -cross-intersecting pair (A,B) with |A||B| = $ left( {{*{20}c} {2ell } ell } right) $ left( {begin{array}{*{20}c} {2ell } ell end{array} } right) 2 n−2 = Θ(2 n /$ sqrt ell $ sqrt ell ), and conjectured that this is best possible. Consequently, Sgall asked whether or not P e (n) decreases with .
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号