×

The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg. (English) Zbl 1460.52010

This paper surveys the theory and applications of the five fundamental theorems of discrete geometry mentioned in the title. In the first part are presented some of the many reformulations and variations of these theorems and explore how these results fit together. The second part of the paper is devoted to the multiple applications of the five theorems. The authors work on wide areas and examine examples from game theory and fair division, from graph theory, from optimization, and from geometric data analysis. Some of the given examples are classical (e.g., Nash equilibria, von Neumann’s min-max theorem, linear programming), others are more specialized (e.g., {D}ol’nikov’s colorability defect or the polynomial partitioning technique) but for all these, the five theorems provide elegant and simple proofs. For other examples (for instance for Meshulam’s lemma, or for the ham sandwich theorem) the authors present new proofs. The paper is well written supplying ample background information and interesting open problems accompany the presentation.

MSC:

52A35 Helly-type theorems and geometric transversal theory
57M99 General low-dimensional topology
90C25 Convex programming
91A80 Applications of game theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aardal, Karen I.; van Hoesel, Stan P. M.; Koster, Arie M. C. A.; Mannino, Carlo; Sassano, Antonio, Models and solution techniques for frequency assignment problems, Ann. Oper. Res., 153, 79-129 (2007) · Zbl 1157.90005
[2] Adamaszek, Micha\l; Barmak, Jonathan Ariel, On a lower bound for the connectivity of the independence complex of a graph, Discrete Math., 311, 21, 2566-2569 (2011) · Zbl 1238.05152
[3] adiprasito+barany+mustafa K. Adiprasito, I. B\'ar\'any, and N. Mustafa, Theorems of Carath\'eodory, Helly, and Tverberg without dimension, arXiv:1806.08725 (2018). · Zbl 1432.52013
[4] adiprasito2016colorful K. A. Adiprasito, P. Brinkmann, A. Padrol, P. Pat\'ak, and Z. Pat\'akov\'a, and R. Sanyal, Colorful simplicial depth, Minkowski sums, and generalized Gale transforms, Int. Math. Res. Not. IMRN (2017), rnx184. · Zbl 1417.52036
[5] Adler, Ilan, The equivalence of linear programs and zero-sum games, Internat. J. Game Theory, 42, 1, 165-177 (2013) · Zbl 1282.91018
[6] Agarwal, Pankaj K.; Matou\v{s}ek, Ji\v{r}\'{i}; Sharir, Micha, On range searching with semialgebraic sets. II, SIAM J. Comput., 42, 6, 2039-2062 (2013) · Zbl 1285.68192
[7] Aharoni, Ron; Berger, Eli; Ziv, Ran, Independent systems of representatives in weighted graphs, Combinatorica, 27, 3, 253-267 (2007) · Zbl 1164.05020
[8] Aharoni, Ron; Holzman, Ron, Fractional kernels in digraphs, J. Combin. Theory Ser. B, 73, 1, 1-6 (1998) · Zbl 0904.05036
[9] Ahmed, Maya; De Loera, Jes\'{u}s; Hemmecke, Raymond, Polyhedral cones of magic cubes and squares. Discrete and computational geometry, Algorithms Combin. 25, 25-41 (2003), Springer, Berlin · Zbl 1077.52506
[10] Aigner, Martin; Ziegler, G\"{u}nter M., Proofs from The Book, viii+308 pp. (2014), Springer-Verlag, Berlin · Zbl 1294.01001
[11] aisenbergetal2015 J. Aisenberg, M. L. Bonet, and S. Buss, 2-d Tucker is PPA-complete. Electronic Colloquium on Computational Complexity (ECCC) 22 (2015), 163. · Zbl 1436.68127
[12] Aliev, Iskander; Bassett, Robert; De Loera, Jes\'{u}s A.; Louveaux, Quentin, A quantitative Doignon-Bell-Scarf theorem, Combinatorica, 37, 3, 313-332 (2017) · Zbl 1399.52011
[13] Aliev, I.; De Loera, J. A.; Eisenbrand, F.; Oertel, T.; Weismantel, R., The support of integer optimal solutions, SIAM J. Optim., 28, 3, 2152-2157 (2018) · Zbl 1402.90091
[14] Aliev, Iskander; De Loera, Jes\'{u}s A.; Oertel, Timm; O’Neill, Christopher, Sparse solutions of linear Diophantine equations, SIAM J. Appl. Algebra Geom., 1, 1, 239-253 (2017) · Zbl 1370.13022
[15] Alishahi, Meysam, Colorful subhypergraphs in uniform hypergraphs, Electron. J. Combin., 24, 1, Paper 1.23, 26 pp. (2017) · Zbl 1355.05102
[16] Alishahi, Meysam; Hajiabolhassan, Hossein, On the chromatic number of general Kneser hypergraphs, J. Combin. Theory Ser. B, 115, 186-209 (2015) · Zbl 1319.05046
[17] Alishahi, Meysam; Hajiabolhassan, Hossein; Meunier, Fr\'{e}d\'{e}ric, Strengthening topological colorful results for graphs, European J. Combin., 64, 27-44 (2017) · Zbl 1365.05081
[18] Alishahi, Meysam; Meunier, Fr\'{e}d\'{e}ric, Fair splitting of colored paths, Electron. J. Combin., 24, 3, Paper 3.41, 8 pp. (2017) · Zbl 1369.05157
[19] Alon, Noga, Splitting necklaces, Adv. in Math., 63, 3, 247-253 (1987) · Zbl 0635.05008
[20] Alon, Noga; B\'{a}r\'{a}ny, Imre; F\`“{u}redi, Zolt\'”{a}n; Kleitman, Daniel J., Point selections and weak \(\epsilon \)-nets for convex hulls, Combin. Probab. Comput., 1, 3, 189-200 (1992) · Zbl 0797.52004
[21] Alon, Noga; Kalai, Gil; Matou\v{s}ek, Ji\v{r}\'{i}; Meshulam, Roy, Transversal numbers for hypergraphs arising in geometry, Adv. in Appl. Math., 29, 1, 79-101 (2002) · Zbl 1027.52003
[22] Alon, Noga; Kleitman, Daniel J., Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem, Adv. Math., 96, 1, 103-112 (1992) · Zbl 0768.52001
[23] Alon, Noga; Moshkovitz, Dana; Safra, Shmuel, Algorithmic construction of sets for \(k\)-restrictions, ACM Trans. Algorithms, 2, 2, 153-177 (2006) · Zbl 1321.68445
[24] Alon, Noga; West, Douglas B., The Borsuk-Ulam theorem and bisection of necklaces, Proc. Amer. Math. Soc., 98, 4, 623-628 (1986) · Zbl 0614.05005
[25] Aloupis, Greg; Langerman, Stefan; Soss, Michael; Toussaint, Godfried, Algorithms for bivariate medians and a Fermat-Torricelli problem for lines, Comput. Geom., 26, 1, 69-79 (2003) · Zbl 1039.62045
[26] Amenta, N., Helly-type theorems and generalized linear programming, Discrete Comput. Geom., 12, 3, 241-261 (1994) · Zbl 0819.90056
[27] Amenta, N.; Bern, M.; Eppstein, D.; Teng, S.-H., Regression depth and center points, Discrete Comput. Geom., 23, 3, 305-323 (2000) · Zbl 1039.62058
[28] Amenta, Nina; De Loera, Jes\'{u}s A.; Sober\'{o}n, Pablo, Helly’s theorem: new variations and applications. Algebraic and geometric methods in discrete mathematics, Contemp. Math. 685, 55-95 (2017), Amer. Math. Soc., Providence, RI · Zbl 1383.52006
[29] Arocha, Jorge L.; B\'{a}r\'{a}ny, Imre; Bracho, Javier; Fabila, Ruy; Montejano, Luis, Very colorful theorems, Discrete Comput. Geom., 42, 2, 142-154 (2009) · Zbl 1173.52002
[30] Arora, Sanjeev; Barak, Boaz, Computational complexity, xxiv+579 pp. (2009), Cambridge University Press, Cambridge · Zbl 1193.68112
[31] Asada, Megumi; Chen, Ryan; Frick, Florian; Huang, Frederick; Polevy, Maxwell; Stoner, David; Tsang, Ling Hei; Wellner, Zoe, On Reay’s relaxed Tverberg conjecture and generalizations of Conway’s thrackle conjecture, Electron. J. Combin., 25, 3, Paper 3.16, 14 pp. (2018) · Zbl 1397.52004
[32] Asada, Megumi; Frick, Florian; Pisharody, Vivek; Polevy, Maxwell; Stoner, David; Tsang, Ling Hei; Wellner, Zoe, Fair division and generalizations of Sperner- and KKM-type results, SIAM J. Discrete Math., 32, 1, 591-610 (2018) · Zbl 1385.54013
[33] Aumann, Robert J., Subjectivity and correlation in randomized strategies, J. Math. Econom., 1, 1, 67-96 (1974) · Zbl 0297.90106
[34] Averkov, Gennadiy, On maximal \(S\)-free sets and the Helly number for the family of \(S\)-convex sets, SIAM J. Discrete Math., 27, 3, 1610-1624 (2013) · Zbl 1282.90109
[35] Averkov, Gennadiy; Gonz\'{a}lez Merino, Bernardo; Paschke, Ingo; Schymura, Matthias; Weltge, Stefan, Tight bounds on discrete quantitative Helly numbers, Adv. in Appl. Math., 89, 76-101 (2017) · Zbl 1369.52011
[36] Averkov, G.; Weismantel, R., Transversal numbers over subsets of linear spaces, Adv. Geom., 12, 1, 19-28 (2012) · Zbl 1250.52006
[37] Avis, David; Friedmann, Oliver, An exponential lower bound for Cunningham’s rule, Math. Program., 161, 1-2, Ser. A, 271-305 (2017) · Zbl 1360.90163
[38] Aziz, Haris; Mackenzie, Simon, A discrete and bounded envy-free cake cutting protocol for any number of agents. 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2016, 416-427 (2016), IEEE Computer Soc., Los Alamitos, CA
[39] Bajm\'{o}czy, E. G.; B\'{a}r\'{a}ny, I., On a common generalization of Borsuk’s and Radon’s theorem, Acta Math. Acad. Sci. Hungar., 34, 3-4, 347-350 (1980) (1979) · Zbl 0446.52010
[40] B\'{a}r\'{a}ny, Imre, A generalization of Carath\'{e}odory’s theorem, Discrete Math., 40, 2-3, 141-152 (1982) · Zbl 0492.52005
[41] barany1993geometric I. B\'ar\'any, Geometric and combinatorial applications of Borsuk’s theorem, New trends in discrete and computational geometry. Springer, 1993, pp. 235-249. · Zbl 0788.52012
[42] B\'{a}r\'{a}ny, Imre; Blagojevi\'{c}, Pavle V. M.; Ziegler, G\`“{u}nter M., Tverberg”s theorem at 50: extensions and counterexamples, Notices Amer. Math. Soc., 63, 7, 732-739 (2016) · Zbl 1358.52022
[43] B\'{a}r\'{a}ny, Imre; Katchalski, Meir; Pach, J\'{a}nos, Quantitative Helly-type theorems, Proc. Amer. Math. Soc., 86, 1, 109-114 (1982) · Zbl 0511.52005
[44] B\'{a}r\'{a}ny, I.; Larman, D. G., A colored version of Tverberg’s theorem, J. London Math. Soc. (2), 45, 2, 314-320 (1992) · Zbl 0769.52008
[45] B\'{a}r\'{a}ny, Imre; Matou\v{s}ek, Ji\v{r}\'{i}, A fractional Helly theorem for convex lattice sets, Adv. Math., 174, 2, 227-235 (2003) · Zbl 1028.52003
[46] B\'{a}r\'{a}ny, I.; Onn, S., Carath\'{e}odory’s theorem, colourful and applicable. Intuitive geometry, Budapest, 1995, Bolyai Soc. Math. Stud. 6, 11-21 (1997), J\'{a}nos Bolyai Math. Soc., Budapest · Zbl 0883.52004
[47] B\'{a}r\'{a}ny, Imre; Onn, Shmuel, Colourful linear programming and its relatives, Math. Oper. Res., 22, 3, 550-567 (1997) · Zbl 0887.90111
[48] B\'{a}r\'{a}ny, I.; Shlosman, S. B.; Sz\H{u}cs, A., On a topological generalization of a theorem of Tverberg, J. London Math. Soc. (2), 23, 1, 158-164 (1981) · Zbl 0453.55003
[49] B\'{a}r\'{a}ny, Imre; Sober\'{o}n, Pablo, Tverberg plus minus, Discrete Comput. Geom., 60, 3, 588-598 (2018) · Zbl 1401.52014
[50] B\'{a}r\'{a}ny, Imre; Sober\'{o}n, Pablo, Tverberg’s theorem is 50 years old: a survey, Bull. Amer. Math. Soc. (N.S.), 55, 4, 459-492 (2018) · Zbl 1401.52012
[51] Barman, Siddharth, Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carath\'{e}odory’s theorem. STOC’15-Proceedings of the 2015 ACM Symposium on Theory of Computing, 361-369 (2015), ACM, New York · Zbl 1322.91006
[52] Barvinok, Alexander, A course in convexity, Graduate Studies in Mathematics 54, x+366 pp. (2002), American Mathematical Society, Providence, RI · Zbl 1014.52001
[53] Basit, Abdul; Mustafa, Nabil H.; Ray, Saurabh; Raza, Sarfraz, Hitting simplices with points in \(\mathbb{R}^3\), Discrete Comput. Geom., 44, 3, 637-644 (2010) · Zbl 1211.52026
[54] Basu, Amitabh; Conforti, Michele; Cornu\'{e}jols, G\'{e}rard; Weismantel, Robert; Weltge, Stefan, Optimality certificates for convex minimization and Helly numbers, Oper. Res. Lett., 45, 6, 671-674 (2017) · Zbl 1409.90137
[55] Basu, Amitabh; Oertel, Timm, Centerpoints: a link between optimization and convex geometry. Integer programming and combinatorial optimization, Lecture Notes in Comput. Sci. 9682, 14-25 (2016), Springer, Cham · Zbl 1419.90073
[56] Bell, David E., A theorem concerning the integer lattice, Studies in Appl. Math., 56, 2, 187-188 (1976/77) · Zbl 0388.90051
[57] BeDu83 C. Berge and P. Duchet, Seminar, MSHi (Maison des Sciences de l’Homme), 1983.
[58] Bertsekas, Dimitri P., Convex optimization algorithms, xii+564 pp. (2015), Athena Scientific, Belmont, MA · Zbl 1347.90001
[59] Bertsimas, Dimitris; Vempala, Santosh, Solving convex programs by random walks, J. ACM, 51, 4, 540-556 (2004) · Zbl 1204.90074
[60] Bezdek, K\'{a}roly; Blokhuis, Aart, The Radon number of the three-dimensional integer lattice, Discrete Comput. Geom., 30, 2, 181-184 (2003) · Zbl 1043.52010
[61] Birch, B. J., On \(3N\) points in a plane, Proc. Cambridge Philos. Soc., 55, 289-293 (1959) · Zbl 0089.38502
[62] Bj\"{o}rner, A., Topological methods. Handbook of combinatorics, Vol. 2, 1819-1872 (1995), Elsevier Sci. B. V., Amsterdam · Zbl 0851.52016
[63] Blagojevi\'{c}, Pavle V. M.; Blagojevi\'{c}, Aleksandra S. Dimitrijevi\'{c}; Ziegler, G\"{u}nter M., Polynomial partitioning for several sets of varieties, J. Fixed Point Theory Appl., 19, 3, 1653-1660 (2017) · Zbl 1386.52016
[64] Blagojevi\'{c}, Pavle V. M.; Frick, Florian; Haase, Albert; Ziegler, G\`“{u}nter M., Topology of the Gr\'”{u}nbaum-Hadwiger-Ramos hyperplane mass partition problem, Trans. Amer. Math. Soc., 370, 10, 6795-6824 (2018) · Zbl 1396.52011
[65] Blagojevi\'{c}, Pavle V. M.; Frick, Florian; Haase, Albert; Ziegler, G\"{u}nter M., Hyperplane mass partitions via relative equivariant obstruction theory, Doc. Math., 21, 735-771 (2016) · Zbl 1361.55007
[66] Blagojevi\'{c}, Pavle V. M.; Frick, Florian; Ziegler, G\"{u}nter M., Tverberg plus constraints, Bull. Lond. Math. Soc., 46, 5, 953-967 (2014) · Zbl 1305.52021
[67] blafrickzie P. V. M. Blagojevi\'c, F. Frick, and G. M. Ziegler, G. M. Barycenters of polytope skeleta and counterexamples to the topological Tverberg conjecture, via constraints, J. Europ. Math. Soc. (to appear) (2017). · Zbl 1428.52008
[68] Blagojevi\'{c}, Pavle V. M.; Matschke, Benjamin; Ziegler, G\`“{u}nter M., Optimal bounds for a colorful Tverberg-Vre\'”{c}ica type problem, Adv. Math., 226, 6, 5198-5215 (2011) · Zbl 1213.52009
[69] Blagojevi\'{c}, Pavle V. M.; Matschke, Benjamin; Ziegler, G\"{u}nter M., Optimal bounds for the colored Tverberg problem, J. Eur. Math. Soc. (JEMS), 17, 4, 739-754 (2015) · Zbl 1327.52009
[70] Blagojevi\'{c}, Pavle V. M.; Sober\'{o}n, Pablo, Thieves can make sandwiches, Bull. Lond. Math. Soc., 50, 1, 108-123 (2018) · Zbl 1390.52008
[71] Blagojevi\'{c}, Pavle V. M.; Ziegler, G\"{u}nter M., Beyond the Borsuk-Ulam theorem: the topological Tverberg story. A journey through discrete mathematics, 273-341 (2017), Springer, Cham · Zbl 1470.52007
[72] Blum, Avrim; Har-Peled, Sariel; Raichel, Benjamin, Sparse approximation via generating point sets. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 548-557 (2016), ACM, New York · Zbl 1411.68165
[73] Boros, E.; F\"{u}redi, Z., The number of triangles covering the center of an \(n\)-set, Geom. Dedicata, 17, 1, 69-77 (1984) · Zbl 0595.52002
[74] Boros, Endre; Gurvich, Vladimir, Perfect graphs are kernel solvable, Discrete Math., 159, 1-3, 35-55 (1996) · Zbl 0861.05053
[75] Borsuk, Karol, On the imbedding of systems of compacta in simplicial complexes, Fund. Math., 35, 217-234 (1948) · Zbl 0032.12303
[76] Boyd, Stephen; Vandenberghe, Lieven, Convex optimization, xiv+716 pp. (2004), Cambridge University Press, Cambridge · Zbl 1058.90049
[77] Brams, Steven J.; Taylor, Alan D., Fair division, xiv+272 pp. (1996), Cambridge University Press, Cambridge · Zbl 0991.91019
[78] Brams, Steven J.; Jones, Michael A.; Klamler, Christian, \(N\)-person cake-cutting: there may be no perfect division, Amer. Math. Monthly, 120, 1, 35-47 (2013) · Zbl 1266.91011
[79] Brams, Steven J.; Kilgour, D. Marc; Klamler, Christian, How to divide things fairly, Math. Mag., 88, 5, 338-348 (2015) · Zbl 1353.91023
[80] Brazitikos, Silouanos, Quantitative Helly-type theorem for the diameter of convex sets, Discrete Comput. Geom., 57, 2, 494-505 (2017) · Zbl 1368.52001
[81] Br\"{o}nnimann, H.; Goodrich, M. T., Almost optimal set covers in finite VC-dimension, Discrete Comput. Geom., 14, 4, 463-479 (1995) · Zbl 0841.68122
[82] Brualdi, Richard A.; Ryser, Herbert J., Combinatorial matrix theory, Encyclopedia of Mathematics and its Applications 39, x+367 pp. (1991), Cambridge University Press, Cambridge · Zbl 1286.05001
[83] Bruns, Winfried; Gubeladze, Joseph; Henk, Martin; Martin, Alexander; Weismantel, Robert, A counterexample to an integer analogue of Carath\'{e}odory’s theorem, J. Reine Angew. Math., 510, 179-185 (1999) · Zbl 0938.52011
[84] Bukh, Boris, A point in many triangles, Electron. J. Combin., 13, 1, Note 10, 3 pp. (2006) · Zbl 1165.52301
[85] Bukh, Boris; Matou\v{s}ek, Ji\v{r}\'{i}; Nivasch, Gabriel, Lower bounds for weak epsilon-nets and stair-convexity, Israel J. Math., 182, 199-208 (2011) · Zbl 1222.68395
[86] Bukh, Boris; Matou\v{s}ek, Ji\v{r}\'{i}; Nivasch, Gabriel, Stabbing simplices by points and flats, Discrete Comput. Geom., 43, 2, 321-338 (2010) · Zbl 1186.52001
[87] Calafiore, Giuseppe; Campi, M. C., Uncertain convex programs: randomized solutions and confidence levels, Math. Program., 102, 1, Ser. A, 25-46 (2005) · Zbl 1177.90317
[88] Calafiore, Giuseppe C.; Campi, Marco C., The scenario approach to robust control design, IEEE Trans. Automat. Control, 51, 5, 742-753 (2006) · Zbl 1366.93457
[89] Carath\'{e}odory, C., \`“{U}ber den Variabilit\'”{a}tsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen, Math. Ann., 64, 1, 95-115 (1907) · JFM 38.0448.01
[90] Carl, Bernd, Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces, Ann. Inst. Fourier (Grenoble), 35, 3, 79-118 (1985) · Zbl 0564.47009
[91] Chakerian, G. D.; Stein, S. K., Some intersection properties of convex bodies, Proc. Amer. Math. Soc., 18, 109-112 (1967) · Zbl 0149.39905
[92] Chakerian, G. D., Intersection and covering properties of convex sets, Amer. Math. Monthly, 76, 753-766 (1969) · Zbl 0181.50302
[93] Chan, Timothy M., An optimal randomized algorithm for maximum Tukey depth. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 430-436 (2004), ACM, New York · Zbl 1317.68246
[94] Chan, Timothy M., Improved deterministic algorithms for linear programming in low dimensions. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1213-1219 (2016), ACM, New York · Zbl 1414.90209
[95] Chan, Timothy M.; Grant, Elyot; K\"{o}nemann, Jochen; Sharpe, Malcolm, Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 1576-1585 (2012), ACM, New York · Zbl 1421.68198
[96] Chazelle, Bernard, Cutting hyperplanes for divide-and-conquer, Discrete Comput. Geom., 9, 2, 145-158 (1993) · Zbl 0784.52018
[97] Chazelle, Bernard, The discrepancy method, xviii+463 pp. (2000), Cambridge University Press, Cambridge · Zbl 0960.65149
[98] CEGGSW93 B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, M. Sharir, and E. Welzl, Improved bounds on weak \(\epsilon \)-nets for convex sets, Proceedings ACM symposium on Theory of computing (STOC) (1993), pp. 495-504. · Zbl 1310.68201
[99] Chen, Dan; Devillers, Olivier; Iacono, John; Langerman, Stefan; Morin, Pat, Oja centers and centers of gravity, Comput. Geom., 46, 2, 140-147 (2013) · Zbl 1320.62119
[100] chen2015multichromatic P.-A. Chen, On the multichromatic number of \(s\)-stable Kneser graphs, J. Graph Theory 79 (2015), no. 3, 233-248. · Zbl 1316.05040
[101] chen2017 P.-A. Chen, On the chromatic number of almost \(s\)-stable Kneser graphs, arXiv:1711.06621 (2017).
[102] Chen, Peng-An, On the multichromatic number of \(s\)-stable Kneser graphs, J. Graph Theory, 79, 3, 233-248 (2015) · Zbl 1316.05040
[103] Chen, Xi; Deng, Xiaotie, On the complexity of 2D discrete fixed point problem, Theoret. Comput. Sci., 410, 44, 4448-4456 (2009) · Zbl 1183.68294
[104] Chen, Xi; Deng, Xiaotie; Teng, Shang-Hua, Settling the complexity of computing two-player Nash equilibria, J. ACM, 56, 3, Art. 14, 57 pp. (2009) · Zbl 1325.68095
[105] CMR16 O. Cheong, K. Mulmuley, and E. Ramos, Randomization and derandomization, Handbook of Discrete Comput. Geom. (J. E. Goodman, J. O’Rourke, and C. D. T\'oth, Eds.), CRC Press LLC, 2016, to appear.
[106] Chestnut, Stephen R.; Hildebrand, Robert; Zenklusen, Rico, Sublinear bounds for a quantitative Doignon-Bell-Scarf theorem, SIAM J. Discrete Math., 32, 1, 352-371 (2018) · Zbl 1431.52010
[107] Chung, S. J., NP-completeness of the linear complementarity problem, J. Optim. Theory Appl., 60, 3, 393-399 (1989) · Zbl 0632.90072
[108] Chv73 V. Chv\'atal, On the computational complexity of finding a kernel, Tech. Rep., Centre de Recherches Math\'ematiques, Universit\'e de Montr\'eal, 1973.
[109] Clarkson, Kenneth L., New applications of random sampling in computational geometry, Discrete Comput. Geom., 2, 2, 195-222 (1987) · Zbl 0615.68037
[110] Clarkson, Kenneth L., Las Vegas algorithms for linear and integer programming when the dimension is small, J. Assoc. Comput. Mach., 42, 2, 488-499 (1995) · Zbl 0885.65063
[111] Clarkson, Kenneth L.; Edelsbrunner, Herbert; Guibas, Leonidas J.; Sharir, Micha; Welzl, Emo, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom., 5, 2, 99-160 (1990) · Zbl 0704.51003
[112] Clarkson, Kenneth L.; Eppstein, David; Miller, Gary L.; Sturtivant, Carl; Teng, Shang-Hua, Approximating center points with iterative Radon points, Internat. J. Comput. Geom. Appl., 6, 3, 357-377 (1996) · Zbl 0859.68114
[113] Clarkson, Kenneth L.; Shor, Peter W., Applications of random sampling in computational geometry. II, Discrete Comput. Geom., 4, 5, 387-421 (1989) · Zbl 0681.68060
[114] Cloutier, John; Nyman, Kathryn L.; Su, Francis Edward, Two-player envy-free multi-cake division, Math. Social Sci., 59, 1, 26-37 (2010) · Zbl 1200.91146
[115] Cook, W.; Fonlupt, J.; Schrijver, A., An integer analogue of Carath\'{e}odory’s theorem, J. Combin. Theory Ser. B, 40, 1, 63-70 (1986) · Zbl 0589.52005
[116] Cottle, Richard W.; Pang, Jong-Shi; Stone, Richard E., The linear complementarity problem, Classics in Applied Mathematics 60, xxvii+761 pp. (2009), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 1192.90001
[117] collectionmathdecisionsgames K.-D. Crisman and M. A. Jones, Eds. The mathematics of decisions, elections, and games (2014), vol. 624 of Contemporary Mathematics, American Mathematical Society, Providence, RI.
[118] Cunningham, W. H., Theoretical properties of the network simplex method, Math. Oper. Res., 4, 2, 196-208 (1979) · Zbl 0412.90068
[119] Dantzig, George B., Constructive proof of the Min-Max theorem, Pacific J. Math., 6, 25-33 (1956) · Zbl 0074.34501
[120] Danzer, Ludwig; Gr\`“{u}nbaum, Branko; Klee, Victor, Helly”s theorem and its relatives. Proc. Sympos. Pure Math., Vol. VII, 101-180 (1963), Amer. Math. Soc., Providence, R.I.
[121] Daskalakis, Constantinos; Goldberg, Paul W.; Papadimitriou, Christos H., The complexity of computing a Nash equilibrium. STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 71-78 (2006), ACM, New York · Zbl 1301.68142
[122] Datta, Ruchira S., Universality of Nash equilibria, Math. Oper. Res., 28, 3, 424-432 (2003) · Zbl 1082.91010
[123] de Berg, Mark; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark, Computational geometry, xii+386 pp. (2008), Springer-Verlag, Berlin · Zbl 1140.68069
[124] De Loera, Jes\'{u}s A.; Hemmecke, Raymond; K\"{o}ppe, Matthias, Algebraic and geometric ideas in the theory of discrete optimization, MOS-SIAM Series on Optimization 14, xx+322 pp. (2013), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA · Zbl 1401.90012
[125] lowdimTverberg J. A. De Loera, T. Hogan, F. Meunier, and N. Mustafa, Integer and mixed integer Tverberg numbers, Proceedings European Congress of Computational Geometry (2018).
[126] DeLoeraetal-tv-2018 J. A. De Loera, T. A. Hogan, D. Oliveros, and D. Yang, Tverberg-Type Theorems with Trees and Cycles as (Nerve) Intersection Patterns, arXiv:1808.00551 (2018).
[127] De Loera, Jes\'{u}s A.; La Haye, Reuben N.; Rolnick, David; Sober\'{o}n, Pablo, Quantitative combinatorial geometry for continuous parameters, Discrete Comput. Geom., 57, 2, 318-334 (2017) · Zbl 1369.52012
[128] De Loera, J. A.; La Haye, R. N.; Oliveros, D.; Rold\'{a}n-Pensado, E., Chance-constrained convex mixed-integer optimization and beyond: two sampling algorithms within \(S\)-optimization, J. Convex Anal., 25, 1, 201-218 (2018) · Zbl 1390.90405
[129] De Loera, J. A.; La Haye, R. N.; Oliveros, D.; Rold\'{a}n-Pensado, E., Helly numbers of algebraic subsets of \(\mathbb{R}^d\) and an extension of Doignon’s theorem, Adv. Geom., 17, 4, 473-482 (2017) · Zbl 1431.52011
[130] De Loera, Jesus A.; La Haye, Reuben N.; Rolnick, David; Sober\'{o}n, Pablo, Quantitative Tverberg theorems over lattices and other discrete sets, Discrete Comput. Geom., 58, 2, 435-448 (2017) · Zbl 1386.52004
[131] De Loera, Jesus A.; Peterson, Elisha; Su, Francis Edward, A polytopal generalization of Sperner’s lemma, J. Combin. Theory Ser. A, 100, 1, 1-26 (2002) · Zbl 1015.05089
[132] De Loera, Jes\'{u}s A.; Rambau, J\"{o}rg; Santos, Francisco, Triangulations, Algorithms and Computation in Mathematics 25, xiv+535 pp. (2010), Springer-Verlag, Berlin · Zbl 1207.52002
[133] de Longueville, Mark, A course in topological combinatorics, Universitext, xii+238 pp. (2013), Springer, New York · Zbl 1273.05001
[134] de Longueville, Mark; Zivaljevi\'{c}, Rade T., Splitting multidimensional necklaces, Adv. Math., 218, 3, 926-939 (2008) · Zbl 1154.05006
[135] Colin de Verdi\`“ere, \'”{E}ric; Ginot, Gr\'{e}gory; Goaoc, Xavier, Helly numbers of acyclic families, Adv. Math., 253, 163-193 (2014) · Zbl 1301.52019
[136] de1997combinatorics D. de Werra, The combinatorics of timetabling, European J. Oper. Res. 96 (1997), no. 3, 504-513. · Zbl 0917.90190
[137] dengetal2017 X. Deng, Z. Feng, and R. Kulkarni, Octahedral tucker is PPA-complete, Electronic Colloquium on Computational Complexity (ECCC) (2017), vol. 24, p. 118.
[138] Deng, Xiaotie; Qi, Qi; Saberi, Amin, Algorithmic solutions for envy-free cake cutting, Oper. Res., 60, 6, 1461-1476 (2012) · Zbl 1262.91016
[139] Deza, Antoine; Huang, Sui; Stephen, Tamon; Terlaky, Tam\'{a}s, Colourful simplicial depth, Discrete Comput. Geom., 35, 4, 597-615 (2006) · Zbl 1118.62058
[140] Diestel, Reinhard, Graph theory, Graduate Texts in Mathematics 173, xvi+411 pp. (2005), Springer-Verlag, Berlin · Zbl 1074.05001
[141] Dobbins, Michael Gene, A point in a \(nd\)-polytope is the barycenter of \(n\) points in its \(d\)-faces, Invent. Math., 199, 1, 287-292 (2015) · Zbl 1321.52018
[142] Dodson, C. T. J.; Parker, Phillip E., A user’s guide to algebraic topology, Mathematics and its Applications 387, xii+405 pp. (1997), Kluwer Academic Publishers Group, Dordrecht · Zbl 0886.55001
[143] Doignon, Jean-Paul, Convexity in cristallographical lattices, J. Geometry, 3, 71-85 (1973) · Zbl 0245.52004
[144] Dold, Albrecht, Simple proofs of some Borsuk-Ulam results. Proceedings of the Northwestern Homotopy Theory Conference, Evanston, Ill., 1982, Contemp. Math. 19, 65-69 (1983), Amer. Math. Soc., Providence, RI · Zbl 0521.55002
[145] dol1981transversals V. Dol’nikov, Transversals of families of sets. Studies in the theory of functions of several real variables (Russian) (1981), 30-36.
[146] Dubins, L. E.; Spanier, E. H., How to cut a cake fairly, Amer. Math. Monthly, 68, 1-17 (1961) · Zbl 0108.31601
[147] Duchet, P., Graphes noyau-parfaits, Ann. Discrete Math., 9, 93-101 (1980) · Zbl 0462.05033
[148] Duchet, Pierre, Convexity in combinatorial structures, Rend. Circ. Mat. Palermo (2) Suppl.. Proceedings of the 14th winter school on abstract analysis (Srn\'{i}, 1986), 14, 261-293 (1987) · Zbl 0644.52001
[149] Duchet, Pierre; Meyniel, Henri, Une g\'{e}n\'{e}ralisation du th\'{e}or\`“eme de Richardson sur l”existence de noyaux dans les graphes orient\'{e}s, Discrete Math., 43, 1, 21-27 (1983) · Zbl 0502.05027
[150] Durand, Arnaud; Hermann, Miki; Juban, Laurent, On the complexity of recognizing the Hilbert basis of a linear Diophantine system, Theoret. Comput. Sci., 270, 1-2, 625-642 (2002) · Zbl 0988.68083
[151] Eckhoff, J\"{u}rgen, An upper-bound theorem for families of convex sets, Geom. Dedicata, 19, 2, 217-227 (1985) · Zbl 0588.52012
[152] Eckhoff, J\`“{u}rgen, Helly, Radon, and Carath\'”{e}odory type theorems. Handbook of convex geometry, Vol. A, B, 389-448 (1993), North-Holland, Amsterdam · Zbl 0791.52009
[153] Eckhoff, J\"{u}rgen, The partition conjecture, Discrete Math., 221, 1-3, 61-78 (2000) · Zbl 0971.52008
[154] Edmonds, Jack; Giles, Rick, A min-max relation for submodular functions on graphs. Studies in integer programming, Proc. Workshop, Bonn, 1975, 185-204. Ann. of Discrete Math., Vol. 1 (1977), North-Holland, Amsterdam
[155] Eisenbrand, Friedrich; Shmonin, Gennady, Carath\'{e}odory bounds for integer cones, Oper. Res. Lett., 34, 5, 564-568 (2006) · Zbl 1152.90662
[156] Erd\"{o}s, P., On sets of distances of \(n\) points, Amer. Math. Monthly, 53, 248-250 (1946) · Zbl 0060.34805
[157] Erickson, J., New lower bounds for Hopcroft’s problem, Discrete Comput. Geom., 16, 4, 389-418 (1996) · Zbl 0857.68061
[158] Etessami, Kousha; Yannakakis, Mihalis, On the complexity of Nash equilibria and other fixed points, SIAM J. Comput., 39, 6, 2531-2597 (2010) · Zbl 1204.91003
[159] Even, Guy; Rawitz, Dror; Shahar, Shimon, Hitting sets when the VC-dimension is small, Inform. Process. Lett., 95, 2, 358-362 (2005) · Zbl 1184.68632
[160] Fan, Ky, A generalization of Tucker’s combinatorial lemma with topological applications, Ann. of Math. (2), 56, 431-437 (1952) · Zbl 0047.42004
[161] Fan, Ky, Simplicial maps from an orientable \(n\)-pseudomanifold into \(S^m\)with the octahedral triangulation, J. Combinatorial Theory, 2, 588-602 (1967) · Zbl 0149.41302
[162] Farb, Benson, Group actions and Helly’s theorem, Adv. Math., 222, 5, 1574-1588 (2009) · Zbl 1177.22007
[163] Filos-Ratsikas, Aris; Goldberg, Paul W., Consensus halving is PPA-complete. STOC’18-Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 51-64 (2018), ACM, New York · Zbl 1428.68162
[164] 2018Filos-Ratsikas A. Filos-Ratsikas and P. W. Goldberg, The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches, arXiv:1805.12559 (2018). · Zbl 1433.68157
[165] Flores:NichtEinbettbar-1933 A. I. Flores, \"Uber die Existenz \(n\)-dimensionaler Komplexe, die nicht in den \(R^2n\) topologisch einbettbar sind, Ergeb. Math. Kolloqu. 5 (1933), 17-24.
[166] FGLNP11 J. Fox, M. Gromov, V. Lafforgue, A. Naor, and J. Pach, Overlap properties of geometric expanders, Proceedings ACM-SIAM Symposium on Discrete Algorithms (SODA) 2011, pp. 1188-1197. · Zbl 1376.05101
[167] Freund, Robert M.; Todd, Michael J., A constructive proof of Tucker’s combinatorial lemma, J. Combin. Theory Ser. A, 30, 3, 321-325 (1981) · Zbl 0462.05026
[168] frick15 F. Frick, Counterexamples to the topological Tverberg conjecture, Oberwolfach Reports 12, (1) (2015), 318-321.
[169] Frick, Florian, Intersection patterns of finite sets and of convex sets, Proc. Amer. Math. Soc., 145, 7, 2827-2842 (2017) · Zbl 1360.05058
[170] FrickKneser F. Frick, Chromatic numbers of stable Kneser hypergraphs via topological Tverberg-type theorems, Int. Math. Res. Not. IMRN (2018).
[171] frickhoustonmeunier F. Frick, K. Houston-Edwards, and F. Meunier, Achieving rental harmony with a secretive roommate, Amer. Math. Monthly (to appear, 2017). · Zbl 1419.91396
[172] frick+zerbib F. Frick, and S. Zerbib, Colorful coverings of polytopes and piercing numbers of colorful \(d\)-intervals, Combinatorica (to appear, 2018). · Zbl 1463.05533
[173] Friedmann, Oliver, A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games. Integer programming and combinatorial optimization, Lecture Notes in Comput. Sci. 6655, 192-206 (2011), Springer, Heidelberg · Zbl 1341.90143
[174] Fulek, Radoslav; Holmsen, Andreas F.; Pach, J\'{a}nos, Intersecting convex sets by rays, Discrete Comput. Geom., 42, 3, 343-358 (2009) · Zbl 1178.52002
[175] Fulek, Radoslav; Pach, J\'{a}nos, A computational approach to Conway’s thrackle conjecture, Comput. Geom., 44, 6-7, 345-355 (2011) · Zbl 1232.05143
[176] Gale, David, The game of Hex and the Brouwer fixed-point theorem, Amer. Math. Monthly, 86, 10, 818-827 (1979) · Zbl 0448.90097
[177] Gale, D., Equilibrium in a discrete exchange economy with money, Internat. J. Game Theory, 13, 1, 61-64 (1984) · Zbl 0531.90011
[178] Galeana-S\'{a}nchez, H.; Neumann Lara, V., On kernels and semikernels of digraphs, Discrete Math., 48, 1, 67-76 (1984) · Zbl 0529.05024
[179] garber A. Garber, On Helly number for crystals and cut-and-project sets, arXiv:1605.07881 (2016). · Zbl 1342.65142
[180] Garc\'{i}a-Col\'{i}n, Natalia; Raggi, Miguel; Rold\'{a}n-Pensado, Edgardo, A note on the tolerant Tverberg theorem, Discrete Comput. Geom., 58, 3, 746-754 (2017) · Zbl 1377.52010
[181] Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra, ETR-completeness for decision versions of multi-player \textup{(}symmetric\textup{)} Nash equilibria. Automata, languages, and programming. Part I, Lecture Notes in Comput. Sci. 9134, 554-566 (2015), Springer, Heidelberg · Zbl 1441.68072
[182] G\`“{a}rtner, B.; Matou\v{s}ek, J.; R\'”{u}st, L.; Skovro\v{n}, P., Violator spaces: structure and algorithms, Discrete Appl. Math., 156, 11, 2124-2141 (2008) · Zbl 1163.90651
[183] GKM14 P. Giannopoulos, M. Konzack, and W. Mulzer, Low-crossing spanning trees: an alternative proof and experiments, Proceedings European Workshop on Computational Geometry (2014).
[184] Gijswijt, Dion; Regts, Guus, Polyhedra with the integer Carath\'{e}odory property, J. Combin. Theory Ser. B, 102, 1, 62-70 (2012) · Zbl 1252.52009
[185] Gil, Joseph; Steiger, William; Wigderson, Avi, Geometric medians, Discrete Math., 108, 1-3, 37-51 (1992) · Zbl 0759.68087
[186] Gilboa, Itzhak; Zemel, Eitan, Nash and correlated equilibria: some complexity considerations, Games Econom. Behav., 1, 1, 80-93 (1989) · Zbl 0755.90093
[187] Giles, F. R.; Pulleyblank, W. R., Total dual integrality and integer polyhedra, Linear Algebra Appl., 25, 191-196 (1979) · Zbl 0413.90054
[188] Goaoc, Xavier; Pat\'{a}k, Pavel; Pat\'{a}kov\'{a}, Zuzana; Tancer, Martin; Wagner, Uli, Bounding Helly numbers via Betti numbers. A journey through discrete mathematics, 407-447 (2017), Springer, Cham · Zbl 1390.52012
[189] Goemans, Michel X.; Rothvo\ss, Thomas, Polynomiality for bin packing with a constant number of item types. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 830-839 (2014), ACM, New York · Zbl 1421.68080
[190] Goldberg, Charles H.; West, Douglas B., Bisection of circle colorings, SIAM J. Algebraic Discrete Methods, 6, 1, 93-106 (1985) · Zbl 0558.05008
[191] Goldberg, Paul W.; Papadimitriou, Christos H., TFNP: an update. Algorithms and complexity, Lecture Notes in Comput. Sci. 10236, 3-9 (2017), Springer, Cham · Zbl 1486.68080
[192] Graver, Jack E., On the foundations of linear and integer linear programming. I, Math. Programming, 9, 2, 207-226 (1975) · Zbl 0323.90035
[193] Gromov, Mikhail, Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry, Geom. Funct. Anal., 20, 2, 416-526 (2010) · Zbl 1251.05039
[194] handbookofconvexgeo P. Gruber and J. Wills, Eds. Handbook of Convex Geometry. North-Holland, Amsterdam, 1993.
[195] Gruber, Peter M., Convex and discrete geometry, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 336, xiv+578 pp. (2007), Springer, Berlin · Zbl 1139.52001
[196] Guth, Larry, Polynomial partitioning for a set of varieties, Math. Proc. Cambridge Philos. Soc., 159, 3, 459-469 (2015) · Zbl 1371.14065
[197] Guth, Larry, Polynomial methods in combinatorics, University Lecture Series 64, ix+273 pp. (2016), American Mathematical Society, Providence, RI · Zbl 1388.05003
[198] Guth, Larry; Katz, Nets Hawk, On the Erd\H{o}s distinct distances problem in the plane, Ann. of Math. (2), 181, 1, 155-190 (2015) · Zbl 1310.52019
[199] gyori1976division E. Gyori, On division of graphs to connected subgraphs, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), (1976), vol. 1, pp. 485-494.
[200] Hahn, Ge\v{n}a; Tardif, Claude, Graph homomorphisms: structure and symmetry. Graph symmetry, Montreal, PQ, 1996, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 497, 107-166 (1997), Kluwer Acad. Publ., Dordrecht · Zbl 0880.05079
[201] Hanke, Bernhard; Sanyal, Raman; Schultz, Carsten; Ziegler, G\"{u}nter M., Combinatorial Stokes formulas via minimal resolutions, J. Combin. Theory Ser. A, 116, 2, 404-420 (2009) · Zbl 1200.05025
[202] HP09 S. Har-Peled, Approximating Spanning Trees with Low Crossing Number, arXiv:0907.1131 (2009).
[203] Haussler, David; Welzl, Emo, \( \epsilon \)-nets and simplex range queries, Discrete Comput. Geom., 2, 2, 127-151 (1987) · Zbl 0619.68056
[204] Haxell, P. E., A condition for matchability in hypergraphs, Graphs Combin., 11, 3, 245-248 (1995) · Zbl 0837.05082
[205] HT06 S. Hell, Tverberg-type theorems, and the Fractional Helly property, PhD thesis, T.U. Berlin, 2006. · Zbl 1235.52002
[206] Hell, Stephan, On the number of Tverberg partitions in the prime power case, European J. Combin., 28, 1, 347-355 (2007) · Zbl 1121.05007
[207] Hell, Stephan, On the number of Birch partitions, Discrete Comput. Geom., 40, 4, 586-594 (2008) · Zbl 1169.05008
[208] Hoffman, A. J., Binding constraints and Helly numbers. Second International Conference on Combinatorial Mathematics (New York, 1978), Ann. New York Acad. Sci. 319, 284-288 (1979), New York Acad. Sci., New York
[209] Holmsen, Andreas F., The intersection of a matroid and an oriented matroid, Adv. Math., 290, 1-14 (2016) · Zbl 1329.05058
[210] Holmsen, Andreas F.; Pach, J\'{a}nos; Tverberg, Helge, Points surrounding the origin, Combinatorica, 28, 6, 633-644 (2008) · Zbl 1199.52013
[211] Holmsen, A. F.; Wenger, Rephael, Helly-type theorems and geometric transversals. Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., 63-82 (1997), CRC, Boca Raton, FL · Zbl 0912.52006
[212] Holmsen, Andreas F.; Karasev, Roman, Colorful theorems for strong convexity, Proc. Amer. Math. Soc., 145, 6, 2713-2726 (2017) · Zbl 1364.52006
[213] NervesMinors A. F. Holmsen, M. Kim, and S. Lee, Nerves, minors, and piercing numbers, arXiv:1706.05181 (2017). · Zbl 1414.05202
[214] PBS-sperner K. Houston-Edwards, Splitting rent with triangles, Infinite series, PBS digital studios February 23, 2017. https://www.youtube.com/watch?v=48oBEvpdYSE.
[215] Jadhav, S.; Mukhopadhyay, A., Computing a centerpoint of a finite planar set of points in linear time, Discrete Comput. Geom., 12, 3, 291-312 (1994) · Zbl 0819.68137
[216] jonsson2012chromatic J. Jonsson, On the chromatic number of generalized stable Kneser graphs, http://www.math.kth.se/ jakobj/doc/submitted/stablekneser.pdf (2012).
[217] Kalai, Gil, Intersection patterns of convex sets, Israel J. Math., 48, 2-3, 161-174 (1984) · Zbl 0557.52005
[218] kalai1992subexponential G. Kalai, A subexponential randomized simplex algorithm, Proceedings ACM Symposium on Theory of computing (STOC) (1992), pp. 475-482.
[219] Kalai, Gil, Combinatorics and convexity. Proceedings of the International Congress of Mathematicians, Vol. 1, 2, Z\`“{u}rich, 1994, 1363-1374 (1995), Birkh\'”{a}user, Basel · Zbl 0843.52002
[220] Kalai, Gil, Algebraic shifting. Computational commutative algebra and combinatorics, Osaka, 1999, Adv. Stud. Pure Math. 33, 121-163 (2002), Math. Soc. Japan, Tokyo
[221] kalai_conjectures G. Kalai, Combinatorial expectations from commutative algebra, Combinatorial Commutative Algebra (I. Peeva and V. Welker, Eds.), vol. 1(3). Oberwolfach Reports, 2004, pp. 1729-1734.
[222] Kalai, Gil; Meshulam, Roy, A topological colorful Helly theorem, Adv. Math., 191, 2, 305-311 (2005) · Zbl 1064.52008
[223] Kannan, Ravi; Theobald, Thorsten, Games of fixed rank: a hierarchy of bimatrix games. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1124-1132 (2007), ACM, New York · Zbl 1303.91011
[224] Karas\"{e}v, R. N., Dual theorems on a central point and their generalizations, Mat. Sb.. Sb. Math., 199 199, 9-10, 1459-1479 (2008) · Zbl 1159.52008
[225] Karas\"{e}v, R. N., Topological methods in combinatorial geometry, Uspekhi Mat. Nauk. Russian Math. Surveys, 63 63, 6, 1031-1078 (2008) · Zbl 1200.52001
[226] Karasev, R. N., Tverberg-type theorems for intersecting by rays, Discrete Comput. Geom., 45, 2, 340-347 (2011) · Zbl 1213.52005
[227] Karasev, Roman, A simpler proof of the Boros-F\`“{u}redi-B\'”{a}r\'{a}ny-Pach-Gromov theorem, Discrete Comput. Geom., 47, 3, 492-495 (2012) · Zbl 1237.05054
[228] Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 4, 373-395 (1984) · Zbl 0557.90065
[229] Katchalski, M.; Liu, A., A problem of geometry in \({\bf R}^n\), Proc. Amer. Math. Soc., 75, 2, 284-288 (1979) · Zbl 0418.52013
[230] Kay, David C.; Womble, Eugene W., Axiomatic convexity theory and relationships between the Carath\'{e}odory, Helly, and Radon numbers, Pacific J. Math., 38, 471-485 (1971) · Zbl 0235.52001
[231] khachiyan1980polynomial L. G. Khachiyan, Polynomial algorithms in linear programming, USSR Computational Mathematics and Mathematical Physics 20 1 (1980), 53-72. · Zbl 0459.90047
[232] Kir\'{a}ly, Tam\'{a}s; Pap, J\'{u}lia, A note on kernels and Sperner’s lemma, Discrete Appl. Math., 157, 15, 3327-3331 (2009) · Zbl 1227.05153
[233] Klee, Victor; Minty, George J., How good is the simplex algorithm?. Inequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, Calif., 1969; dedicated to the memory of Theodore S. Motzkin), 159-175 (1972), Academic Press, New York
[234] Kozlov, Dmitry, Combinatorial algebraic topology, Algorithms and Computation in Mathematics 21, xx+389 pp. (2008), Springer, Berlin · Zbl 1157.57300
[235] Kr\'{a}\v{l}, Daniel; Mach, Luk\'{a}\v{s}; Sereni, Jean-S\'{e}bastien, A new lower bound based on Gromov’s method of selecting heavily covered points, Discrete Comput. Geom., 48, 2, 487-498 (2012) · Zbl 1262.05151
[236] Krasnosel\cprime ski\u{\i}, M. A., On a proof of Helly’s theorem on sets of convex bodies with common points, Vorone\v{z}. Gos. Univ. Trudy. Fiz.-Mat. Sb., 33, 19-20 (1954)
[237] KMV02 S. Krishnan, N. H. Mustafa, and S. Venkatasubramanian, Hardware-assisted computation of depth contours, Proceedings ACM-SIAM Symposium on Discrete Algorithms (SODA) 2002, pp. 558-567. · Zbl 1093.68658
[238] Krishnan, Shankar; Mustafa, Nabil H.; Venkatasubramanian, Suresh, Statistical data depth and the graphics hardware. Data depth: robust multivariate analysis, computational geometry and applications, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 72, 223-246 (2006), Amer. Math. Soc., Providence, RI
[239] Kupavskii, Andrey; Mustafa, Nabil H.; Pach, J\'{a}nos, New lower bounds for \(\epsilon \)-nets. 32nd International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 51, Art. 54, 16 pp. (2016), Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern · Zbl 1390.68721
[240] Langerman, Stefan; Steiger, William, The complexity of hyperplane depth in the plane, Discrete Comput. Geom., 30, 2, 299-309 (2003) · Zbl 1066.68141
[241] Lebert, Nicolas; Meunier, Fr\'{e}d\'{e}ric; Carbonneaux, Quentin, Envy-free two-player \(m\)-cake and three-player two-cake divisions, Oper. Res. Lett., 41, 6, 607-610 (2013) · Zbl 1287.91101
[242] Lemke, C. E.; Howson, J. T., Jr., Equilibrium points of bimatrix games, J. Soc. Indust. Appl. Math., 12, 413-423 (1964) · Zbl 0128.14804
[243] liptonetal R. J. Lipton, E. Markakis, and A. Mehta, Playing large games using simple strategies, Proceedings ACM Conference on Electronic Commerce, (EC) (2003), pp. 36-41.
[244] Liu, Regina Y., On a notion of simplicial depth, Proc. Nat. Acad. Sci. U.S.A., 85, 6, 1732-1734 (1988) · Zbl 0635.62039
[245] Lo, Chi-Yuan; Matou\v{s}ek, J.; Steiger, W., Algorithms for ham-sandwich cuts, Discrete Comput. Geom., 11, 4, 433-452 (1994) · Zbl 0806.68061
[246] Lov\'{a}sz, L., Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2, 3, 253-267 (1972) · Zbl 0239.05111
[247] Lov\'{a}sz, L., Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, 25, 3, 319-324 (1978) · Zbl 0418.05028
[248] Lov\'{a}sz, L\'{a}szl\'{o}, Graph minor theory, Bull. Amer. Math. Soc. (N.S.), 43, 1, 75-86 (2006) · Zbl 1082.05082
[249] Lov\'{a}sz, L\'{a}szl\'{o}; Plummer, Michael D., Matching theory, xxxiv+554 pp. (2009), AMS Chelsea Publishing, Providence, RI · Zbl 1175.05002
[250] LStheorem L. Lyusternik and L. Schnirel’mann, M\'ethodes topologiques dans les probl\`“emes variationnels, Gosudarstvennoe Izdat. (1930); French transl., Actualit\'”es Sci. Indust., no. 118, Hermann, Paris, 1934.
[251] Krein, M.; Milman, D., On extreme points of regular convex sets, Studia Math., 9, 133-138 (1940) · Zbl 0063.03360
[252] Mabillard, Isaac; Wagner, Uli, Eliminating Tverberg points, I. An analogue of the Whitney trick. Computational geometry (SoCG’14), 171-180 (2014), ACM, New York · Zbl 1397.57042
[253] Mart\'{i}nez-Sandoval, Leonardo; Rold\'{a}n-Pensado, Edgardo; Rubin, Natan, Further consequences of the colorful Helly hypothesis. 34th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 99, Art. No. 59, 14 pp. (2018), Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern · Zbl 1491.52011
[254] leo+tamam L. Mart\'nez-Sandoval and R. Tamam, Depth with respect to a family of convex sets, arXiv:1612.03435 (2016).
[255] Matou\v{s}ek, Ji\v{r}\'{i}, Efficient partition trees, Discrete Comput. Geom., 8, 3, 315-334 (1992) · Zbl 0752.68088
[256] M99 J. Matousek, Geometric Discrepancy: An Illustrated Guide, Springer, 1999. · Zbl 0930.11060
[257] Matou\v{s}ek, Ji\v{r}\'{i}, Lectures on discrete geometry, Graduate Texts in Mathematics 212, xvi+481 pp. (2002), Springer-Verlag, New York · Zbl 0999.52006
[258] Matou\v{s}ek, Ji\v{r}\'{i}, Using the Borsuk-Ulam theorem, Universitext, xii+196 pp. (2003), Springer-Verlag, Berlin · Zbl 1016.05001
[259] Matou\v{s}ek, Ji\v{r}\'{i}, A combinatorial proof of Kneser’s conjecture, Combinatorica, 24, 1, 163-170 (2004) · Zbl 1047.05018
[260] Matou\v{s}ek, Ji\v{r}\'{i}, Bounded VC-dimension implies a fractional Helly theorem, Discrete Comput. Geom., 31, 2, 251-255 (2004) · Zbl 1059.52012
[261] Matou\v{s}ek, Ji\v{r}\'{i}, Thirty-three miniatures, Student Mathematical Library 53, x+182 pp. (2010), American Mathematical Society, Providence, RI · Zbl 1195.00043
[262] matousek2007understanding J. Matousek and B. G\"artner, Understanding and using linear programming, Springer Science & Business Media, 2007. · Zbl 1133.90001
[263] Matou\v{s}ek, Ji\v{r}\'{i}; Ziegler, G\"{u}nter M., Topological lower bounds for the chromatic number: a hierarchy, Jahresber. Deutsch. Math.-Verein., 106, 2, 71-90 (2004) · Zbl 1063.05047
[264] Matou\v{s}ek, J.; Sharir, M.; Welzl, E., A subexponential bound for linear programming, Algorithmica, 16, 4-5, 498-516 (1996) · Zbl 0857.68119
[265] Matou\v{s}ek, Ji\v{r}\'{i}; Wagner, Uli, New constructions of weak \(\epsilon \)-nets, Discrete Comput. Geom., 32, 2, 195-206 (2004) · Zbl 1104.68124
[266] Matou\v{s}ek, Ji\v{r}\'{i}; Wagner, Uli, On Gromov’s method of selecting heavily covered points, Discrete Comput. Geom., 52, 1, 1-33 (2014) · Zbl 1298.51027
[267] McKelvey, Richard D.; McLennan, Andrew, Computation of equilibria in finite games. Handbook of computational economics, Vol. I, Handbooks in Econom. 13, 87-142 (1996), North-Holland, Amsterdam · Zbl 1126.91304
[268] McLennan, Andrew, The expected number of Nash equilibria of a normal form game, Econometrica, 73, 1, 141-174 (2005) · Zbl 1152.91326
[269] McLennan, Andrew; Tourky, Rabee, Using volume to prove Sperner’s lemma, Econom. Theory, 35, 3, 593-597 (2008) · Zbl 1139.51008
[270] Meshulam, Roy, The clique complex and hypergraph matching, Combinatorica, 21, 1, 89-94 (2001) · Zbl 1107.05302
[271] Meshulam, Roy, Domination numbers and homology, J. Combin. Theory Ser. A, 102, 2, 321-330 (2003) · Zbl 1030.05086
[272] Me05 F. Meunier, A \(\mathbbZ_q-F\) an theorem, Tech. Rep., Laboratoire Leibniz-IMAG, Grenoble, 2005.
[273] Meunier, Fr\'{e}d\'{e}ric, Sperner labellings: a combinatorial approach, J. Combin. Theory Ser. A, 113, 7, 1462-1475 (2006) · Zbl 1108.52012
[274] Meunier, Fr\'{e}d\'{e}ric, The chromatic number of almost stable Kneser hypergraphs, J. Combin. Theory Ser. A, 118, 6, 1820-1828 (2011) · Zbl 1297.05087
[275] Meunier, Fr\'{e}d\'{e}ric; Deza, Antoine, A further generalization of the colourful Carath\'{e}odory theorem. Discrete geometry and optimization, Fields Inst. Commun. 69, 179-190 (2013), Springer, New York · Zbl 1275.52020
[276] Meunier, Fr\'{e}d\'{e}ric; Mulzer, Wolfgang; Sarrabezolles, Pauline; Stein, Yannik, The rainbow at the end of the line-a \(\mathsf{PPAD}\) formulation of the colorful Carath\'{e}odory theorem with applications. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1342-1351 (2017), SIAM, Philadelphia, PA · Zbl 1410.68373
[277] Meunier, Fr\'{e}d\'{e}ric; Sarrabezolles, Pauline, Colorful linear programming, Nash equilibrium, and pivots, Discrete Appl. Math., 240, 78-91 (2018) · Zbl 1395.90179
[278] Meunier+Zerbib F. Meunier and S. Zerbib Envy-free divisions of a partially burnt cake, arXiv:1804.00449 (2018). · Zbl 1432.91067
[279] MT90 G. L. Miller, and W. P. Thurston, Separators in two and three dimensions, Proceedings ACM Symposium on Theory of computing (STOC) (1990), pp. 300-309.
[280] Miller, Kim; Ramaswami, Suneeta; Rousseeuw, Peter; Sellar\`es, Toni; Souvaine, Diane; Streinu, Ileana; Struyf, Anja, Fast implementation of depth contours using topological sweep. Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, DC, 2001, 690-699 (2001), SIAM, Philadelphia, PA · Zbl 0988.65005
[281] Mirzakhani, Maryam; Vondr\'{a}k, Jan, Sperner’s colorings, hypergraph labeling problems and fair division. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 873-886 (2015), SIAM, Philadelphia, PA · Zbl 1371.05094
[282] Mirzakhani, Maryam; Vondr\'{a}k, Jan, Sperner’s colorings and optimal partitioning of the simplex. A journey through discrete mathematics, 615-631 (2017), Springer, Cham · Zbl 1384.05188
[283] Mizera, Ivan, On depth and deep points: a calculus, Ann. Statist., 30, 6, 1681-1736 (2002) · Zbl 1039.62046
[284] Motzkin, T. S.; Raiffa, H.; Thompson, G. L.; Thrall, R. M., The double description method. Contributions to the theory of games, vol. 2, Annals of Mathematics Studies, no. 28, 51-73 (1953), Princeton University Press, Princeton, N. J.
[285] Mulzer, Wolfgang; Stein, Yannik, Algorithms for tolerated Tverberg partitions. Algorithms and computation, Lecture Notes in Comput. Sci. 8283, 295-305 (2013), Springer, Heidelberg · Zbl 1406.68122
[286] Mulzer, Wolfgang; Stein, Yannik, Computational aspects of the colorful Carath\'{e}odory theorem. 31st International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 34, 44-58 (2015), Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern · Zbl 1378.68182
[287] Mulzer, Wolfgang; Werner, Daniel, Approximating Tverberg points in linear time for any fixed dimension, Discrete Comput. Geom., 50, 2, 520-535 (2013) · Zbl 1298.68281
[288] Munkres, James R., Elements of algebraic topology, ix+454 pp. (1984), Addison-Wesley Publishing Company, Menlo Park, CA · Zbl 0673.55001
[289] Musin, Oleg R., Extensions of Sperner and Tucker’s lemma for manifolds, J. Combin. Theory Ser. A, 132, 172-187 (2015) · Zbl 1307.05195
[290] Musin, Oleg R., Homotopy invariants of covers and KKM-type lemmas, Algebr. Geom. Topol., 16, 3, 1799-1812 (2016) · Zbl 1350.55006
[291] Musin, Oleg R., KKM type theorems with boundary conditions, J. Fixed Point Theory Appl., 19, 3, 2037-2049 (2017) · Zbl 1383.54050
[292] MDG16 N. H. Mustafa, K. Dutta, and A. Ghosh, A Simple Proof of Optimal Epsilon-nets. Combinatorica (2017). https://doi.org/10.1007/s00493-017-3564-5. · Zbl 1424.52020
[293] Mustafa, Nabil H.; Ray, Saurabh, Weak \(\epsilon \)-nets have basis of size \(O(1/\epsilon\log(1/\epsilon))\) in any dimension, Comput. Geom., 40, 1, 84-91 (2008) · Zbl 1135.68054
[294] Mustafa, Nabil H.; Ray, Saurabh, An optimal extension of the centerpoint theorem, Comput. Geom., 42, 6-7, 505-510 (2009) · Zbl 1169.65020
[295] Mustafa, Nabil H.; Ray, Saurabh, An optimal generalization of the colorful Carath\'{e}odory theorem, Discrete Math., 339, 4, 1300-1305 (2016) · Zbl 1333.52005
[296] Mustafa, Nabil H.; Ray, Saurabh; Shabbir, Mudassir, Ray-shooting depth: computing statistical data depth of point sets in the plane. Algorithms-ESA 2011, Lecture Notes in Comput. Sci. 6942, 506-517 (2011), Springer, Heidelberg · Zbl 1347.68342
[297] Mustafa, Nabil H.; Ray, Saurabh; Shabbir, Mudassir, \(k\)-centerpoints conjectures for pointsets in \(\mathbb{R}^d\), Internat. J. Comput. Geom. Appl., 25, 3, 163-185 (2015) · Zbl 1344.68260
[298] Mustafa, Nabil H.; Tiwary, Hans Raj; Werner, Daniel, A proof of the Oja depth conjecture in the plane, Comput. Geom., 47, 6, 668-674 (2014) · Zbl 06296499
[299] MV16 N. H. Mustafa and K. Varadarajan, Epsilon-approximations and epsilon-nets. Handbook of Discrete Comput. Geom. (J. E. Goodman, J. O’Rourke, and C. D. T\'oth, Eds.), CRC Press LLC, 2017.
[300] Nash, John F., Jr., Equilibrium points in \(n\)-person games, Proc. Nat. Acad. Sci. U. S. A., 36, 48-49 (1950) · Zbl 0036.01104
[301] Nash, John, Non-cooperative games, Ann. of Math. (2), 54, 286-295 (1951) · Zbl 0045.08202
[302] nashhex J. F. Nash, Jr., Some games and machines for playing them, Tech. Rep. D-1164, Rand Corporation, 1952.
[303] Nasz\'{o}di, M\'{a}rton, Proof of a conjecture of B\'{a}r\'{a}ny, Katchalski and Pach, Discrete Comput. Geom., 55, 1, 243-248 (2016) · Zbl 1339.52009
[304] Nisanetal-2007 N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, Algorithmic Game Theory. Cambridge University Press, New York, NY, 2007. · Zbl 1130.91005
[305] Novikoff, A., On convergence proofs for perceptrons. Proc. Sympos. Math. Theory of Automata, New York, 1962, 615-622 (1963), Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y.
[306] Nyman, Kathryn L.; Su, Francis Edward, A Borsuk-Ulam equivalent that directly implies Sperner’s lemma, Amer. Math. Monthly, 120, 4, 346-354 (2013) · Zbl 1280.55001
[307] Oja, Hannu, Descriptive statistics for multivariate distributions, Statist. Probab. Lett., 1, 6, 327-332 (1983) · Zbl 0517.62051
[308] Onn, Shmuel, On the geometry and computational complexity of Radon partitions in the integer lattice, SIAM J. Discrete Math., 4, 3, 436-446 (1991) · Zbl 0735.52007
[309] Onn, Shmuel, Nonlinear discrete optimization, Zurich Lectures in Advanced Mathematics, x+137 pp. (2010), European Mathematical Society (EMS), Z\"{u}rich · Zbl 1219.90003
[310] Oza87 M. \"Ozaydin, Equivariant maps for the symmetric group (unpublished preprint), University of Winsconsin-Madison, 17 pages, available at http://digital.library.wisc.edu/1793/63829, 1987.
[311] Pach, J\'{a}nos; Agarwal, Pankaj K., Combinatorial geometry, Wiley-Interscience Series in Discrete Mathematics and Optimization, xiv+354 pp. (1995), John Wiley & Sons, Inc., New York · Zbl 0881.52001
[312] palvolgyi20092d D. P\'alv\"olgyi, \(2d- T\) ucker is PPAD-complete, International Workshop on Internet and Network Economics (2009), Springer, pp. 569-574.
[313] P\'{a}lv\`“{o}lgyi, D\'”{o}m\`“{o}t\'”{o}r, Combinatorial necklace splitting, Electron. J. Combin., 16, 1, Research Paper 79, 8 pp. (2009)
[314] Papadimitriou, Christos H., On the complexity of the parity argument and other inefficient proofs of existence, J. Comput. System Sci., 48, 3, 498-532 (1994) · Zbl 0806.68048
[315] Pinchasi, Rom, A note on smaller fractional Helly numbers, Discrete Comput. Geom., 54, 3, 663-668 (2015) · Zbl 1326.52009
[316] Pisier, G., Remarques sur un r\'{e}sultat non publi\'{e} de B. Maurey. Seminar on Functional Analysis, 1980-1981, Exp. No. V, 13 pp. (1981), \'{E}cole Polytech., Palaiseau
[317] Por-2018 A. Por, Universality of vector sequences and universality of Tverberg partitions, arXiv:1805.07197 (2018). · Zbl 1052.52011
[318] Prescott, Timothy; Su, Francis Edward, A constructive proof of Ky Fan’s generalization of Tucker’s lemma, J. Combin. Theory Ser. A, 111, 2, 257-265 (2005) · Zbl 1080.55005
[319] Queyranne, Maurice; Tardella, Fabio, Carath\'{e}odory, Helly, and Radon numbers for sublattice and related convexities, Math. Oper. Res., 42, 2, 495-516 (2017) · Zbl 1367.52001
[320] Rado, R., A theorem on general measure, J. London Math. Soc., 21, 291-300 (1947) (1946) · Zbl 0061.09606
[321] Radon, Johann, Mengen konvexer K\"{o}rper, die einen gemeinsamen Punkt enthalten, Math. Ann., 83, 1-2, 113-115 (1921) · JFM 48.0834.04
[322] Reay, John R., Generalizations of a theorem of Carath\'{e}odory, Mem. Amer. Math. Soc. No., 54, 50 pp. (1965) · Zbl 0137.41503
[323] Richardson, Moses, Solutions of irreflexive relations, Ann. of Math. (2), 58, 573-590; errata 60 (1954), 595 (1953) · Zbl 0053.02902
[324] Robertson, Jack; Webb, William, Cake-cutting algorithms, x+181 pp. (1998), A K Peters, Ltd., Natick, MA · Zbl 0939.91001
[325] rolnick+soberon2 D. Rolnick and P. Sober\'on, Algorithmic aspects of Tverberg’s theorem, arXiv:1601.03083 (2016).
[326] Rolnick, David; Sober\'{o}n, Pablo, Quantitative \((p,q)\) theorems in combinatorial geometry, Discrete Math., 340, 10, 2516-2527 (2017) · Zbl 1379.52007
[327] Ronkainen, T.; Oja, H.; Orponen, P., Computation of the multivariate Oja median. Developments in robust statistics, Vorau, 2001, 344-359 (2003), Physica, Heidelberg · Zbl 05280064
[328] Economics and computation, Springer Texts in Business and Economics, xiii+612 pp. (2016), Springer, Heidelberg · Zbl 1332.91003
[329] Roudneff, Jean-Pierre, Partitions of points into simplices with \(k\)-dimensional intersection. I. The conic Tverberg’s theorem, European J. Combin., 22, 5, 733-743 (2001) · Zbl 1007.52005
[330] RR96 P. Rousseeuw and I. Ruts, Algorithm AS 307: Bivariate location depth, J. R. Stat. Soc. Ser. C. Appl. Stat. 45 (1996), 516-526. · Zbl 0905.62002
[331] Rousseeuw, Peter J.; Hubert, Mia, Regression depth, J. Amer. Statist. Assoc., 94, 446, 388-433 (1999) · Zbl 1007.62060
[332] rubin18 N. Rubin, An improved bound for weak epsilon-nets in the plane, Proceedings IEEE Symposium on Foundations of Computer Science (FOCS) 2018. · Zbl 07679900
[333] R67 H. J. Ryser, Neuere Probleme der Kombinatorik, Vortr\`“age \'”uber Kombinatorik (July 1967), Oberwolfach, Mathematisches Forschunginstitute.
[334] Sarkaria, K. S., Tverberg’s theorem via number fields, Israel J. Math., 79, 2-3, 317-320 (1992) · Zbl 0786.52005
[335] Sarkaria, K. S., Tverberg partitions and Borsuk-Ulam theorems, Pacific J. Math., 196, 1, 231-241 (2000) · Zbl 1045.55002
[336] Sarrabezolles, Pauline, The colourful simplicial depth conjecture, J. Combin. Theory Ser. A, 130, 119-128 (2015) · Zbl 1305.52008
[337] savani-vonstengel R. Savani and B. von Stengel, Exponentially many steps for finding a Nash equilibrium in a bimatrix game, Proceedings IEEE Symposium on Foundations of Computer Science (FOCS) 2004, pp. 258-267.
[338] Scarf, Herbert, The approximation of fixed points of a continuous mapping, SIAM J. Appl. Math., 15, 1328-1343 (1967) · Zbl 0153.49401
[339] Scarf, Herbert E., The core of an \(N\) person game, Econometrica, 35, 50-69 (1967) · Zbl 0183.24003
[340] Scarf, Herbert E., An observation on the structure of production sets with indivisibilities, Proc. Nat. Acad. Sci. U.S.A., 74, 9, 3637-3641 (1977) · Zbl 0381.90081
[341] Schaefer, Marcus; Stefankovi\v{c}, Daniel, Fixed points, Nash equilibria, and the existential theory of the reals, Theory Comput. Syst., 60, 2, 172-193 (2017) · Zbl 1362.68088
[342] Sch\`“{o}neborn, Torsten; Ziegler, G\'”{u}nter M., The topological Tverberg theorem and winding numbers, J. Combin. Theory Ser. A, 112, 1, 82-104 (2005) · Zbl 1081.05079
[343] Schrijver, A., Vertex-critical subgraphs of Kneser graphs, Nieuw Arch. Wisk. (3), 26, 3, 454-461 (1978) · Zbl 0432.05026
[344] Schrijver, Alexander, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, xii+471 pp. (1986), John Wiley & Sons, Ltd., Chichester · Zbl 0970.90052
[345] Sch03 A. Schrijver, Combinatorial Optimization: polyhedra and efficiency, Springer, 2003.
[346] Seacrest, Tyler; Su, Francis Edward, A lower bound technique for triangulations of simplotopes, SIAM J. Discrete Math., 32, 1, 1-28 (2018) · Zbl 1381.52022
[347] sebocaratheodory A. Sebo, Hilbert bases, Carath\'eodory’s theorem and combinatorial optimization, Integer programming and combinatorial optimization (Waterloo, 1990), Univ. of Waterloo Press, 1990, pp. 431-455.
[348] Segal-Halevi E. Segal-Halevi, Fairly dividing a cake after some parts were burnt in the oven, arXiv:1704.00726 (2017).
[349] Seidel, Raimund, Small-dimensional linear programming and convex hulls made easy, Discrete Comput. Geom., 6, 5, 423-434 (1991) · Zbl 0747.90066
[350] Seymour, P. D., Decomposition of regular matroids, J. Combin. Theory Ser. B, 28, 3, 305-359 (1980) · Zbl 0443.05027
[351] Shapiro, Alexander; Dentcheva, Darinka; Ruszczy\'{n}ski, Andrzej, Lectures on stochastic programming, MOS-SIAM Series on Optimization 9, xviii+494 pp. (2014), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA · Zbl 1302.90003
[352] siegel C. L. Siegel, \"Uber einige Anwendungen diophantischer Approximationen, Abh. der Preus. Akad. der Wissenschaften. Phys.–math., 1 (1929), 209-266. · JFM 56.0180.05
[353] Simmons, Forest W.; Su, Francis Edward, Consensus-halving via theorems of Borsuk-Ulam and Tucker, Math. Social Sci., 45, 1, 15-25 (2003) · Zbl 1027.91047
[354] Simon, Steven, Hyperplane equipartitions plus constraints, J. Combin. Theory Ser. A, 161, 29-50 (2019) · Zbl 1410.52017
[355] Smale, Steve, Mathematical problems for the next century, Math. Intelligencer, 20, 2, 7-15 (1998) · Zbl 0947.01011
[356] Sober\'{o}n, Pablo, Gerrymandering, sandwiches, and topology, Notices Amer. Math. Soc., 64, 9, 1010-1013 (2017) · Zbl 1379.52002
[357] Sober\'{o}n, Pablo, Robust Tverberg and colourful Carath\'{e}odory results via random choice, Combin. Probab. Comput., 27, 3, 427-440 (2018) · Zbl 1387.52012
[358] Sober\'{o}n, Pablo; Strausz, Ricardo, A generalisation of Tverberg’s theorem, Discrete Comput. Geom., 47, 3, 455-460 (2012) · Zbl 1243.52005
[359] Spencer, Gwen; Su, Francis Edward, The LSB theorem implies the KKM lemma, Amer. Math. Monthly, 114, 2, 156-159 (2007) · Zbl 1122.55003
[360] Stahl, Saul, \(n\)-tuple colorings and associated graphs, J. Combinatorial Theory Ser. B, 20, 2, 185-203 (1976) · Zbl 0293.05115
[361] Hex-Tucker M. Stehlik, Personal communication.
[362] Stein, S. K., Transversals of Latin squares and their generalizations, Pacific J. Math., 59, 2, 567-575 (1975) · Zbl 0302.05015
[363] Steinhaus, H., Sur la division pragmatique, Econometrica, 17, (Supplement), 315-319 (1949) · Zbl 0039.34602
[364] Steinitz, Ernst, Bedingt konvergente Reihen und konvexe Systeme, J. Reine Angew. Math., 143, 128-176 (1913) · JFM 44.0287.01
[365] Stone, A. H.; Tukey, J. W., Generalized “sandwich” theorems, Duke Math. J., 9, 356-359 (1942) · Zbl 0061.38405
[366] Stromquist, Walter, How to cut a cake fairly, Amer. Math. Monthly, 87, 8, 640-644 (1980) · Zbl 0441.90002
[367] Stromquist, Walter, Envy-free cake divisions cannot be found by finite protocols, Electron. J. Combin., 15, 1, Research Paper 11, 10 pp. (2008) · Zbl 1158.91403
[368] Su, Francis Edward, Rental harmony: Sperner’s lemma in fair division, Amer. Math. Monthly, 106, 10, 930-942 (1999) · Zbl 1010.05077
[369] su-hex F. Su, A rectangular Sperner’s lemma implies the Hex theorem, Working manuscript (2018).
[370] NYT-sperner A. Sun, To divide the rent, start with a triangle, New York Times, April 29, 2014. https://www.nytimes.com/2014/04/29/science/to-divide-the-rent-start-with-a-triangle.html?_r=1.
[371] Szemer\'{e}di, Endre; Trotter, William T., Jr., Extremal problems in discrete geometry, Combinatorica, 3, 3-4, 381-392 (1983) · Zbl 0541.05012
[372] Tancer, Martin, Intersection patterns of convex sets via simplicial complexes: a survey. Thirty essays on geometric graph theory, 521-540 (2013), Springer, New York · Zbl 1276.52010
[373] todd1977number M. J. Todd, The number of necessary constraints in an integer program: a new proof of Scarf’s theorem, Tech. Rep. 355, Cornell University, 1977.
[374] Todd, Michael J.; Tun\c{c}el, Levent, A new triangulation for simplicial algorithms, SIAM J. Discrete Math., 6, 1, 167-180 (1993) · Zbl 0778.65038
[375] Tukey, John W., Mathematics and the picturing of data. Proceedings of the International Congress of Mathematicians, Vancouver, B. C., 1974, 523-531 (1975), Canad. Math. Congress, Montreal, Que.
[376] Tverberg, H., A generalization of Radon’s theorem, J. London Math. Soc., 41, 123-128 (1966) · Zbl 0131.20002
[377] Tverberg, H., A generalization of Radon’s theorem. II, Bull. Austral. Math. Soc., 24, 3, 321-325 (1981) · Zbl 0465.52002
[378] Tverberg, Helge; Vre\'{c}ica, Sini\v{s}a, On generalizations of Radon’s theorem and the ham sandwich theorem, European J. Combin., 14, 3, 259-264 (1993) · Zbl 0777.52005
[379] Vaaler, Jeffrey D., The best constant in Siegel’s lemma, Monatsh. Math., 140, 1, 71-89 (2003) · Zbl 1034.11038
[380] van de Vel, M. L. J., Theory of convex structures, North-Holland Mathematical Library 50, xvi+540 pp. (1993), North-Holland Publishing Co., Amsterdam · Zbl 0785.52001
[381] van Kampen, E. R., Komplexe in euklidischen R\"{a}umen, Abh. Math. Sem. Univ. Hamburg, 9, 1, 72-78 (1933) · Zbl 0005.02604
[382] van Kreveld, Marc; Mitchell, Joseph S. B.; Rousseeuw, Peter; Sharir, Micha; Snoeyink, Jack; Speckmann, Bettina, Efficient algorithms for maximum regression depth, Discrete Comput. Geom., 39, 4, 656-677 (2008) · Zbl 1161.62043
[383] Vapnik, V. N.; Cervonenkis, A. Ja., The uniform convergence of frequencies of the appearance of events to their probabilities, Teor. Verojatnost. i Primenen., 16, 264-279 (1971)
[384] Varadarajan, Kasturi, Weighted geometric set cover via quasi-uniform sampling. STOC’10-Proceedings of the 2010 ACM International Symposium on Theory of Computing, 641-647 (2010), ACM, New York · Zbl 1293.68300
[385] Vazirani, Vijay V., Approximation algorithms, xx+378 pp. (2001), Springer-Verlag, Berlin · Zbl 1005.68002
[386] Volovikov, A. Yu., On a topological generalization of Tverberg’s theorem, Mat. Zametki. Math. Notes, 59 59, 3-4, 324-325 (1996) · Zbl 0879.55004
[387] von Neumann, John; Morgenstern, Oskar, Theory of Games and Economic Behavior, xviii+625 pp. (1944), Princeton University Press, Princeton, New Jersey · Zbl 1241.91002
[388] Vu\v{c}i\'{c}, Aleksandar; Zivaljevi\'{c}, Rade T., Note on a conjecture of Sierksma, Discrete Comput. Geom., 9, 4, 339-349 (1993) · Zbl 0784.52007
[389] W03 U. Wagner, On \(k\)-Sets and Applications, PhD thesis, ETH Zurich, 2003.
[390] Walter, Matthias; Truemper, Klaus, Implementation of a unimodularity test, Math. Program. Comput., 5, 1, 57-73 (2013) · Zbl 1262.05020
[391] Williamson, David P.; Shmoys, David B., The design of approximation algorithms, xii+504 pp. (2011), Cambridge University Press, Cambridge · Zbl 1219.90004
[392] Woodall, D. R., Dividing a cake fairly, J. Math. Anal. Appl., 78, 1, 233-247 (1980) · Zbl 0476.28001
[393] YaoYao85 A. C. Yao and F. F. Yao, A general approach to \(d\)-dimensional geometric queries, Proceedings ACM Symposium on Theory of Computing (STOC) (1985), pp. 163-168.
[394] Zhu, Xuding, Recent developments in circular colouring of graphs. Topics in discrete mathematics, Algorithms Combin. 26, 497-550 (2006), Springer, Berlin · Zbl 1127.05046
[395] Ziegler, G\"{u}nter M., Generalized Kneser coloring theorems with combinatorial proofs, Invent. Math., 147, 3, 671-691 (2002) · Zbl 1029.05058
[396] Ziegler, G\"{u}nter M., 3N colored points in a plane, Notices Amer. Math. Soc., 58, 4, 550-557 (2011) · Zbl 1222.51003
[397] MR2728499 R. T. Zivaljevi\'c Oriented matroids and Ky Fan’s theorem, Combinatorica 30, 4 (2010), 471-484.
[398] Zivaljevi\'{c}, Rade T., Topological methods. Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., 209-224 (1997), CRC, Boca Raton, FL · Zbl 0955.52500
[399] Zivaljevi\'{c}, Rade T.; Vre\'{c}ica, Sini\v{s}a T., The colored Tverberg’s problem and complexes of injective functions, J. Combin. Theory Ser. A, 61, 2, 309-318 (1992) · Zbl 0782.52003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.