Combinatorial Convexity

Bárány, Imre

doi:10.1090/ulect/077

My Holdings

Activate Remote Access

Combinatorial Convexity

About this Title

Imre Bárány, Rényi Institute of Mathematics, Budapest, Hungary

Publication: University Lecture Series
Publication Year: 2021; Volume 77
ISBNs: 978-1-4704-6709-8 (print); 978-1-4704-6768-5 (online)
DOI: https://doi.org/10.1090/ulect/077

PDF View full volume as PDF

Read more about this volume

PDF Download chapters as PDF

Front/Back Matter

View this volume's front and back matter

Chapters

References

Karim A. Adiprasito, Philip Brinkmann, Arnau Padrol, Pavel Paták, Zuzana Patáková, and Raman Sanyal, Colorful simplicial depth, Minkowski sums, and generalized Gale transforms, Int. Math. Res. Not. IMRN 6 (2019), 1894–1919. MR 3932598, DOI 10.1093/imrn/rnx184
N. Alon, Piercing $d$-intervals, Discrete Comput. Geom. 19 (1998), no. 3, Special Issue, 333–334. Dedicated to the memory of Paul Erdős. MR 1608873, DOI 10.1007/PL00009349
Noga Alon, Imre Bárány, Zoltán Füredi, and Daniel J. Kleitman, Point selections and weak $\epsilon$-nets for convex hulls, Combin. Probab. Comput. 1 (1992), no. 3, 189–200. MR 1208800, DOI 10.1017/S0963548300000225
Noga Alon, Gil Kalai, Jiří Matoušek, and Roy Meshulam, Transversal numbers for hypergraphs arising in geometry, Adv. in Appl. Math. 29 (2002), no. 1, 79–101. MR 1921545, DOI 10.1016/S0196-8858(02)00003-9
Noga Alon and Daniel J. Kleitman, Piercing convex sets and the Hadwiger-Debrunner $(p,q)$-problem, Adv. Math. 96 (1992), no. 1, 103–112. MR 1185788, DOI 10.1016/0001-8708(92)90052-M
N. Alon and D. J. Kleitman, A purely combinatorial proof of the Hadwiger Debrunner $(p,q)$ conjecture, Electron. J. Combin. 4 (1997), no. 2, Research Paper 1, approx. 8. The Wilf Festschrift (Philadelphia, PA, 1996). MR 1444148
Jorge L. Arocha, Imre Bárány, Javier Bracho, Ruy Fabila, and Luis Montejano, Very colorful theorems, Discrete Comput. Geom. 42 (2009), no. 2, 142–154. MR 2519872, DOI 10.1007/s00454-009-9180-4
E. G. Bajmóczy and I. Bárány, On a common generalization of Borsuk’s and Radon’s theorem, Acta Math. Acad. Sci. Hungar. 34 (1979), no. 3-4, 347–350 (1980). MR 565677, DOI 10.1007/BF01896131
Imre Bárány, A generalization of Carathéodory’s theorem, Discrete Math. 40 (1982), no. 2-3, 141–152. MR 676720, DOI 10.1016/0012-365X(82)90115-7
I. Bárány, Z. Füredi, and L. Lovász, On the number of halving planes, Combinatorica 10 (1990), no. 2, 175–183. MR 1082647, DOI 10.1007/BF02123008
I. Bárány and D. G. Larman, A colored version of Tverberg’s theorem, J. London Math. Soc. (2) 45 (1992), no. 2, 314–320. MR 1171558, DOI 10.1112/jlms/s2-45.2.314
Imre Bárány and Jiří Matoušek, A fractional Helly theorem for convex lattice sets, Adv. Math. 174 (2003), no. 2, 227–235. MR 1963693, DOI 10.1016/S0001-8708(02)00037-3
Imre Bárány and Shmuel Onn, Colourful linear programming, Integer programming and combinatorial optimization (Vancouver, BC, 1996) Lecture Notes in Comput. Sci., vol. 1084, Springer, Berlin, 1996, pp. 1–15. MR 1441787, DOI 10.1007/3-540-61310-2_{1}
I. Bárány, S. B. Shlosman, and A. Szűcs, On a topological generalization of a theorem of Tverberg, J. London Math. Soc. (2) 23 (1981), no. 1, 158–164. MR 602247, DOI 10.1112/jlms/s2-23.1.158
Károly Bezdek and Aart Blokhuis, The Radon number of the three-dimensional integer lattice, Discrete Comput. Geom. 30 (2003), no. 2, 181–184. U.S.-Hungarian Workshops on Discrete Geometry and Convexity (Budapest, 1999/Auburn, AL, 2000). MR 2007959, DOI 10.1007/s00454-003-0003-8
A. Björner, L. Lovász, S. T. Vrećica, and R. T. Živaljević, Chessboard complexes and matching complexes, J. London Math. Soc. (2) 49 (1994), no. 1, 25–39. MR 1253009, DOI 10.1112/jlms/49.1.25
Pavle V. M. Blagojević, Florian Frick, and Günter M. Ziegler, Barycenters of polytope skeleta and counterexamples to the topological Tverberg conjecture, via constraints, J. Eur. Math. Soc. (JEMS) 21 (2019), no. 7, 2107–2116. MR 3959859, DOI 10.4171/JEMS/881
Pavle V. M. Blagojević, Benjamin Matschke, and Günter M. Ziegler, Optimal bounds for the colored Tverberg problem, J. Eur. Math. Soc. (JEMS) 17 (2015), no. 4, 739–754. MR 3336834, DOI 10.4171/JEMS/516
E. Boros and Z. Füredi, The number of triangles covering the center of an $n$-set, Geom. Dedicata 17 (1984), no. 1, 69–77. MR 771183, DOI 10.1007/BF00181519
R. C. Buck and Ellen F. Buck, Equipartition of convex sets, Math. Mag. 22 (1949), 195–198. MR 29521, DOI 10.2307/3029182
Boris Bukh, A point in many triangles, Electron. J. Combin. 13 (2006), no. 1, Note 10, 3. MR 2240753
Boris Bukh, Jiří Matoušek, and Gabriel Nivasch, Lower bounds for weak epsilon-nets and stair-convexity, Israel J. Math. 182 (2011), 199–208. MR 2783971, DOI 10.1007/s11856-011-0029-1
C. Carathéodory, Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen, Math. Ann. 64 (1907), no. 1, 95–115 (German). MR 1511425, DOI 10.1007/BF01449883
Jack G. Ceder, On a problem of Grünbaum, Proc. Amer. Math. Soc. 16 (1965), 188–189. MR 173200, DOI 10.1090/S0002-9939-1965-0173200-5
B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, M. Sharir, and E. Welzl, Improved bounds on weak $\epsilon$-nets for convex sets, Discrete Comput. Geom. 13 (1995), no. 1, 1–15. MR 1300506, DOI 10.1007/BF02574025
T. K. Dey, Improved bounds for planar $k$-sets and related problems, Discrete Comput. Geom. 19 (1998), no. 3, Special Issue, 373–382. Dedicated to the memory of Paul Erdős. MR 1608878, DOI 10.1007/PL00009354
Antoine Deza, Sui Huang, Tamon Stephen, and Tamás Terlaky, Colourful simplicial depth, Discrete Comput. Geom. 35 (2006), no. 4, 597–615. MR 2225675, DOI 10.1007/s00454-006-1233-3
R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51 (1950), 161–166. MR 32578, DOI 10.2307/1969503
Jean-Paul Doignon, Convexity in cristallographical lattices, J. Geom. 3 (1973), 71–85. MR 387090, DOI 10.1007/BF01949705
Jürgen Eckhoff, An upper-bound theorem for families of convex sets, Geom. Dedicata 19 (1985), no. 2, 217–227. MR 809468, DOI 10.1007/BF00181472
Herbert Edelsbrunner, Algorithms in combinatorial geometry, EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, Berlin, 1987. MR 904271, DOI 10.1007/978-3-642-61568-9
Paul Erdős and Miklós Simonovits, Supersaturated graphs and hypergraphs, Combinatorica 3 (1983), no. 2, 181–192. MR 726456, DOI 10.1007/BF02579292
P. Erdős, L. Lovász, A. Simmons, and E. G. Straus, Dissection graphs of planar point sets, A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) North-Holland, Amsterdam, 1973, pp. 139–149. MR 0363986
Julius Farkas, Theorie der einfachen Ungleichungen, J. Reine Angew. Math. 124 (1902), 1–27 (German). MR 1580578, DOI 10.1515/crll.1902.124.1
Werner Fenchel, Über Krümmung und Windung geschlossener Raumkurven, Math. Ann. 101 (1929), no. 1, 238–252 (German). MR 1512528, DOI 10.1007/BF01454836
A. Flores. Über $n$-dimensionale Complex, die im $\R _{2n+1}$ absolute selbstverschlungen sind. Ergäb. Math. Kolloq., 6:4–7, 1932.
F. Frick. Counterexamples to the topological Tverberg conjecture. Oberwolfach Reports, 12:318–321, 2015.
D. R. Fulkerson and O. A. Gross, Incidence matrices with the consecutive $1$’s property, Bull. Amer. Math. Soc. 70 (1964), 681–684. MR 190028, DOI 10.1090/S0002-9904-1964-11160-5
Jacob E. Goodman and Richard Pollack, Allowable sequences and order types in discrete and computational geometry, New trends in discrete and computational geometry, Algorithms Combin., vol. 10, Springer, Berlin, 1993, pp. 103–134. MR 1228041, DOI 10.1007/978-3-642-58043-7_{6}
A. Gyárfás and J. Lehel, A Helly-type problem in trees, Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969) North-Holland, Amsterdam, 1970, pp. 571–584. MR 0298550
H. Hadwiger and H. Debrunner, Über eine Variante zum Hellyschen Satz, Arch. Math. (Basel) 8 (1957), 309–313 (German). MR 92987, DOI 10.1007/BF01898794
Allen Hatcher, Algebraic topology, Cambridge University Press, Cambridge, 2002. MR 1867354
T. Hausel, On a Gallai-type problem for lattices, Acta Math. Hungar. 66 (1995), no. 1-2, 127–145. MR 1313780, DOI 10.1007/BF01874358
David Haussler and Emo Welzl, $\epsilon$-nets and simplex range queries, Discrete Comput. Geom. 2 (1987), no. 2, 127–151. MR 884223, DOI 10.1007/BF02187876
E. Helly. Über Mengen konvexer Körper mit gemeinschaftlichen Punkten. Jahresberichte der Deutschen Math.-Verein., 32:175–176, 1923.
Andreas F. Holmsen, Hossein Nassajian Mojarrad, János Pach, and Gábor Tardos, Two extensions of the Erdős-Szekeres problem, J. Eur. Math. Soc. (JEMS) 22 (2020), no. 12, 3981–3995. MR 4176784, DOI 10.4171/jems/1000
Andreas F. Holmsen, János Pach, and Helge Tverberg, Points surrounding the origin, Combinatorica 28 (2008), no. 6, 633–644. MR 2488743, DOI 10.1007/s00493-008-2427-5
T. Kaiser, Transversals of $d$-intervals, Discrete Comput. Geom. 18 (1997), no. 2, 195–203. MR 1455514, DOI 10.1007/PL00009315
Gil Kalai, Intersection patterns of convex sets, Israel J. Math. 48 (1984), no. 2-3, 161–174. MR 770699, DOI 10.1007/BF02761162
E. R. van Kampen, Komplexe in euklidischen Räumen, Abh. Math. Sem. Univ. Hamburg 9 (1933), no. 1, 72–78 (German). MR 3069580, DOI 10.1007/BF02940628
M. Katchalski and A. Liu, A problem of geometry in $\textbf {R}^{n}$, Proc. Amer. Math. Soc. 75 (1979), no. 2, 284–288. MR 532152, DOI 10.1090/S0002-9939-1979-0532152-6
Paul Kirchberger, Über Tchebychefsche Annäherungsmethoden, Math. Ann. 57 (1903), no. 4, 509–540 (German). MR 1511222, DOI 10.1007/BF01445182
Daniel J. Kleitman, András Gyárfás, and Géza Tóth, Convex sets in the plane with three of every four meeting, Combinatorica 21 (2001), no. 2, 221–232. Paul Erdős and his mathematics (Budapest, 1999). MR 1832447, DOI 10.1007/s004930100020
J. Komlós and M. Simonovits, Szemerédi’s regularity lemma and its applications in graph theory, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993) Bolyai Soc. Math. Stud., vol. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 295–352. MR 1395865
R. N. Krasnoselski. On a criteria for starshapedness. Mat. Sb., 19:309–310, 1946.
K. Kuratowski. Sur le problème des courbes gauches en topologie. Fund. Math., 15:271–283, 1930.
C. G. Lekkerkerker and J. Ch. Boland, Representation of a finite graph by a set of intervals on the real line, Fund. Math. 51 (1962/63), 45–64. MR 139159, DOI 10.4064/fm-51-1-45-64
Bernt Lindström, A theorem on families of sets, J. Combinatorial Theory Ser. A 13 (1972), 274–277. MR 304183, DOI 10.1016/0097-3165(72)90030-1
L. Lovász, On the number of halving lines, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 14 (1971), 107–108 (1972). MR 340111
László Lovász, Combinatorial problems and exercises, 2nd ed., North-Holland Publishing Co., Amsterdam, 1993. MR 1265492
Isaac Mabillard and Uli Wagner, Eliminating Tverberg points, I. An analogue of the Whitney trick, Computational geometry (SoCG’14), ACM, New York, 2014, pp. 171–180. MR 3382296
Jiří Matoušek, Note on the colored Tverberg theorem, J. Combin. Theory Ser. B 66 (1996), no. 1, 146–151. MR 1368521, DOI 10.1006/jctb.1996.0011
J. Matoušek, Lower bounds on the transversal numbers of $d$-intervals, Discrete Comput. Geom. 26 (2001), no. 3, 283–287. MR 1854102, DOI 10.1007/s00454-001-0037-8
Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299, DOI 10.1007/978-1-4613-0039-7
J. Matoušek. Using the Borsuk–Ulam theorem: Lectures on topological methods in combinatorics and geometry. Springer, 2003.
Jiří Matoušek and Uli Wagner, New constructions of weak $\epsilon$-nets, Discrete Comput. Geom. 32 (2004), no. 2, 195–206. MR 2074337, DOI 10.1007/s00454-004-1116-4
D. McGinnis. A family of convex sets in the plane satisfying the (4,3)-property be pierced by nine points. page 16, 2020. arXiv 2010.13195.
P. McMullen, The maximum numbers of faces of a convex polytope, Mathematika 17 (1970), 179–184. MR 283691, DOI 10.1112/S0025579300002850
Shmuel Onn, On the geometry and computational complexity of Radon partitions in the integer lattice, SIAM J. Discrete Math. 4 (1991), no. 3, 436–446. MR 1105949, DOI 10.1137/0404039
M. Özaydin. Equivariant maps for the symmetric group. unpublished preprint, University of Winsconsin-Madison, 17 pages, 1987.
János Pach, A Tverberg-type result on multicolored simplices, Comput. Geom. 10 (1998), no. 2, 71–76. MR 1614605, DOI 10.1016/S0925-7721(97)00022-9
A. Pór. Colourful theorems in convexity. PhD thesis, Eötvös University, Budapest, 1997. diploma thesis.
Attila Pór and Pavel Valtr, The partitioned version of the Erdős-Szekeres theorem, Discrete Comput. Geom. 28 (2002), no. 4, 625–637. Discrete and computational geometry and graph drawing (Columbia, SC, 2001). MR 1949905, DOI 10.1007/s00454-002-2894-1
R. Rado, A theorem on general measure, J. London Math. Soc. 21 (1946), 291–300 (1947). MR 21962, DOI 10.1112/jlms/s1-21.4.291
Johann Radon, Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten, Math. Ann. 83 (1921), no. 1-2, 113–115 (German). MR 1512002, DOI 10.1007/BF01464231
Jean-Pierre Roudneff, Partitions of points into simplices with $k$-dimensional intersection. I. The conic Tverberg’s theorem, European J. Combin. 22 (2001), no. 5, 733–743. Combinatorial geometries (Luminy, 1999). MR 1845497, DOI 10.1006/eujc.2000.0493
Natan Rubin, An improved bound for weak epsilon-nets in the plane, 59th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2018, IEEE Computer Soc., Los Alamitos, CA, 2018, pp. 224–235. MR 3899592, DOI 10.1109/FOCS.2018.00030
N. Rubin. Stronger bounds for weak $\varepsilon$-nets in higher dimensions. In Proceedings of the Annual Symposium on Foundations of Computer Science (STOC 2021), page 62, 2021. arxiv 2104.12654.
K. S. Sarkaria, Tverberg’s theorem via number fields, Israel J. Math. 79 (1992), no. 2-3, 317–320. MR 1248921, DOI 10.1007/BF02808223
Pauline Sarrabezolles, The colourful simplicial depth conjecture, J. Combin. Theory Ser. A 130 (2015), 119–128. MR 3280686, DOI 10.1016/j.jcta.2014.11.002
Sophus Lie, Gesammelte Abhandlungen. Band 1, Johnson Reprint Corp., New York-London, 1973 (German). Herausgegeben von Friedrich Engel und Poul Heegaard; Geometrische Abhandlungen. Abteilung 1; Reprint of the 1934 edition. MR 0392459
G. Sierksma, Relationships between Carathéodory, Helly, Radon and exchange numbers of convexity spaces, Nieuw Arch. Wisk. (3) 25 (1977), no. 2, 115–132. MR 514026
Pablo Soberón, Equal coefficients and tolerance in coloured Tverberg partitions, Combinatorica 35 (2015), no. 2, 235–252. MR 3347469, DOI 10.1007/s00493-014-2969-7
Ernst Steinitz, Bedingt konvergente Reihen und konvexe Systeme, J. Reine Angew. Math. 143 (1913), 128–176 (German). MR 1580879, DOI 10.1515/crll.1913.143.128
Andrew Suk, On the Erdős-Szekeres convex polygon problem, J. Amer. Math. Soc. 30 (2017), no. 4, 1047–1053. MR 3671936, DOI 10.1090/jams/869
George Szekeres and Lindsay Peters, Computer solution to the 17-point Erdős-Szekeres problem, ANZIAM J. 48 (2006), no. 2, 151–164. MR 2291511, DOI 10.1017/S144618110000300X
Endre Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 399–401 (English, with French summary). MR 540024
Gábor Tardos, Transversals of $2$-intervals, a topological approach, Combinatorica 15 (1995), no. 1, 123–134. MR 1325276, DOI 10.1007/BF01294464
G. Tóth, Point sets with many $k$-sets, Discrete Comput. Geom. 26 (2001), no. 2, 187–194. ACM Symposium on Computational Geometry (Hong Kong, 2000). MR 1843435
H. Tverberg, A generalization of Radon’s theorem, J. London Math. Soc. 41 (1966), 123–128. MR 187147, DOI 10.1112/jlms/s1-41.1.123
V. N. Vapnik and A. Ja. Červonenkis, The uniform convergence of frequencies of the appearance of events to their probabilities, Teor. Verojatnost. i Primenen. 16 (1971), 264–279 (Russian, with English summary). MR 0288823
A. Yu. Volovikov, On a topological generalization of Tverberg’s theorem, Mat. Zametki 59 (1996), no. 3, 454–456 (Russian); English transl., Math. Notes 59 (1996), no. 3-4, 324–325. MR 1399973, DOI 10.1007/BF02308547
Rade T. Živaljević and Siniša T. Vrećica, The colored Tverberg’s problem and complexes of injective functions, J. Combin. Theory Ser. A 61 (1992), no. 2, 309–318. MR 1185000, DOI 10.1016/0097-3165(92)90028-S

Combinatorial Convexity

About this Title

Table of Contents

References [Enhancements On Off] (What's this?)