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


The (p,q) property in families of d-intervals and d-trees
Abstract:Given integers pq>1, a family of sets satisfies the (p,q) property if among any p members of it some q intersect. We prove that for any fixed integer constants pq>1, a family of d-intervals satisfying the (p,q) property can be pierced by O(dqq1) points, with constants depending only on p and q. This extends results of Tardos, Kaiser and Alon for the case q=2, and of Kaiser and Rabinovich for the case p=q=log2(d+2). We further show that similar bounds hold in families of subgraphs of a tree or a graph of bounded tree-width, each consisting of at most d connected components, extending results of Alon for the case q=2. Finally, we prove an upper bound of O(d1p1) on the fractional piercing number in families of d-intervals satisfying the (p,p) property, and show that this bound is asymptotically sharp.
Keywords:Piercing numbers  Fractional piercing numbers
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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