The (p,q) property in families of d-intervals and d-trees

摘要

Given two integers $pge q>1$, a family of sets satisfies the $(p,q)$property if among any $p$ members of it some $q$ intersect. We prove that afamily of $d$-intervals satisfying the $(p,q)$ property can be pierced by atmost $c(p,q)d^{rac{q}{q-1}} + o(d^{rac{q}{q-1}})$ points, where $c(p,p) =p^{rac{1}{p-1}}$ and $c(p,q)=2^{rac{1}{q-1}}(ep)^rac{q}{q-1}q^{-1}.$ Thisextends results of Tardos, Kaiser and Alon for the case $q=2$, and of Kaiserand Rabinovich for the case $p=q=lceil log_2(d+2) ceil$. We further showthat our bounds hold also in families of subgraphs of a tree (or a graph ofbounded tree-width), each consisting of at most $d$ connected components,extending results of Alon for the case $q=2$. We also prove an upper bound of$O(d^{rac{1}{p-1}})$ on the fractional covering number in families of$d$-intervals that satisfy the $(p,p)$ property, and show that this bound istight.