Colourful and Fractional (p,q)-theorems
详细信息 查看全文
- 作者：I. Bárány (1) (2)
F. Fodor (3) (4)
L. Montejano (5)
D. Oliveros (5)
A. Pór (6) - 关键词：Colourful and fractional theorems ; Gallai and Helly type results ; The (p ; q) ; problem
- 刊名：Discrete and Computational Geometry
- 出版年：2014
- 出版时间：April 2014
- 年：2014
- 卷：51
- 期：3
- 页码：628-642
- 全文大小：
- 参考文献：1. Alon, N., Kleitman, D.J.: Piercing convex sets and the Hadwiger–Debrunner ( / p, / q)-problem. Adv. Math. 96(1), 103-12 (1992) CrossRef
2. Bárány, I.: A generalization of Carathéodory’s theorem. Discrete Math. 40(2-), 141-52 (1982) CrossRef
3. Danzer, L., Grünbaum, B., Klee, V.: Helly’s theorem and its relatives. In: Klee, V. (ed.) Convexity, Proceedings of Symposia in Pure Mathematics, vol. 7, pp. 100-81. American Mathematical Society, Providence (1963)
4. Eckhoff, J.: Helly, Radon, and Carathéodory type theorems. In: Handbook of Convex Geometry, vol. A, B, pp. 389-48. North-Holland, Amsterdam (1993)
5. Eckhoff, J.: A survey of the Hadwiger–Debrunner (p,q)-problem. In: Discrete and Computational Geometry. Algorithms Combin., vol. 25, pp. 347-77. Springer, Berlin (2003) CrossRef
6. Gyárfás, A., Lehel, J.: A Helly-type problem in trees. In: Combinatorial Theory and Its Applications, II, Proc. Colloq., Balatonfüred, 1969, pp. 571-84. North-Holland, Amsterdam (1970)
7. Hadwiger, H., Debrunner, H.: über eine Variante zum Hellyschen Satz. Arch. Math. 8, 309-13 (1957) (in German) CrossRef
8. Katchalski, M., Liu, A.: A problem of geometry in / R / n . Proc. Am. Math. Soc. 75, 284-88 (1979)
9. Lovász, L.: Exercise 206. Mat. Lapok, 394-96 (1974) (in Hungarian)
10. Matou?ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002) CrossRef
11. Wegner, G.: / d-collapsing and nerves of families of convex sets. Arch. Math. 26, 317-21 (1975) CrossRef - 作者单位：I. Bárány (1) (2)
F. Fodor (3) (4)
L. Montejano (5)
D. Oliveros (5)
A. Pór (6)
1. Alfréd Rényi Institute of Mathematics, PO Box 127, 1364, Budapest, Hungary
2. Department of Mathematics, University College London, Gower Street, London, WC1E 6BT, UK
3. Department of Geometry, Bolyai Institute, University of Szeged, Aradi vértanúk tere 1, 6720, Szeged, Hungary
4. Department of Mathematics and Statistics, University of Calgary, 2500 University Dr. N.W., Calgary, Alberta, Canada, T2N 1N4
5. Instituto de Matemáticas, Universidad Nacional Autónoma de México, México City, México
6. Department of Mathematics, Western Kentucky University, Bowling Green, KY, 42101, USA - ISSN：1432-0444
文摘
Let p?em class="a-plus-plus">q?em class="a-plus-plus">d+1 be positive integers and let \({\mathcal{F}}\) be a finite family of convex sets in \({\mathbb{R}}^{d}\) . Assume that the elements of \({\mathcal{F}}\) are coloured with p colours. A p-element subset of \({\mathcal{F}}\) is heterochromatic if it contains exactly one element of each colour. The family \({\mathcal{F}}\) has the heterochromatic (p,q)-property if in every heterochromatic p-element subset there are at least q elements that have a point in common. We show that, under the heterochromatic (p,q)-condition, some colour class can be pierced by a finite set whose size we estimate from above in terms of d,p, and q. This is a colourful version of the famous (p,q)-theorem. (We prove a colourful variant of the fractional Helly theorem along the way.) A fractional version of the same problem is when the (p,q)-condition holds for all but an α fraction of the p-tuples in \({\mathcal{F}}\) . We show that, in the case that d=1, all but a β fraction of the elements of \({\mathcal{F}}\) can be pierced by p?em class="a-plus-plus">q+1 points. Here β depends on α and p,q, and β? as α goes to zero.