pith. sign in

arxiv: 1703.02939 · v6 · pith:3J2FHIMInew · submitted 2017-03-08 · 🧮 math.CO

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

classification 🧮 math.CO
keywords propertycasefamiliesintervalsalonboundconstantsfamily
0
0 comments X
read the original abstract

Given integers $p\ge q>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 $p\ge q>1$, a family of $d$-intervals satisfying the $(p,q)$ property can be pierced by $O(d^{\frac{q}{q-1}})$ 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=\lceil log_2(d+2) \rceil$. 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(d^{\frac{1}{p-1}})$ on the fractional piercing number in families of $d$-intervals satisfying the $(p,p)$ property, and show that this bound is asymptotically sharp.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.