Colourful and fractional (p,q)-theorems

Let \(p\geq q \geq d +1\) be positive integers. Let \(\mathcal{F}_1, \dots \mathcal{F}_p\) be finite families of convex sets in \(\mathbb{R}^d\) and \(\mathcal{F}\) their union painted with different colors. The family \(\mathcal{F}\) satisfies the heterochromatic \((p, q)\)-condition, to be denoted by \((p, q)_H\), if every heterochromatic \(p\)-tuple of \(\mathcal{F}\) contains an intersecting \(q\)-tuple. Following the Alon-Kleitman method [\textit{N. Alon} and \textit{D. J. Kleitman}, Adv. Math. 96, No. 1, 103--112 (1992; Zbl 0768.52001)], the authors prove that there exists a number \(M(p,q,d)\) such that the following statement holds: Given finite families \(\mathcal{F}_1, \dots \mathcal{F}_p\) of convex sets in \(\mathbb{R}^d\) satisfying the \((p, q)_H\)-property, there are \(q-d\) indices \(i \in [p]\) for which \(\tau (\mathcal{F}_i)\leq M(p,q,d)\) (here \(\tau (\mathcal{F})\) designates the piercing number of \(\mathcal{F}\)). Next, on the main case \(q = d+1\), the authors obtain the following fractional \((p,q)_H\)-theorem: If \(\alpha > 0\) and \(p \geq d + 1\), then there exists a real number \(\gamma (\alpha, p, d) > 0\) such that the following statement holds: Given finite families \(\mathcal{F}_1, \dots \mathcal{F}_p\) of convex sets in \(\mathbb{R}^d\) satisfying the \((p, d +1)_H\)-condition for all but an \(\alpha\) fraction of heterochromatic \(p\)-tuples of \(\mathcal{F} = \bigcup_{i=1}^n \mathcal{F}_i\), some family \(\mathcal{F}_i\) contains an intersecting subfamily of size \(\gamma |\mathcal{F}_i|\). In the second half of the paper the authors prove precise results on the piercing number when the convex sets are intervals in \(\mathbb{R}\).

Recommendations

Cites work

Cited in

(20)

This page was built for publication: Colourful and fractional \((p,q)\)-theorems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2249476)