The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

De Loera, Jesús; Goaoc, Xavier; Meunier, Frédéric; Mustafa, Nabil

doi:10.1090/bull/1653

The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
HTML articles powered by AMS MathViewer

by Jesús A. De Loera, Xavier Goaoc, Frédéric Meunier and Nabil H. Mustafa PDF

Bull. Amer. Math. Soc. 56 (2019), 415-511 Request permission

Abstract:

We discuss five fundamental results of discrete mathematics: the lemmas of Sperner and Tucker from combinatorial topology and the theorems of Carathéodory, Helly, and Tverberg from combinatorial geometry. We explore their connections and emphasize their broad impact in application areas such as data science, game theory, graph theory, mathematical optimization, computational geometry, etc.

References

Karen I. Aardal, Stan P. M. van Hoesel, Arie M. C. A. Koster, Carlo Mannino, and Antonio Sassano, Models and solution techniques for frequency assignment problems, Ann. Oper. Res. 153 (2007), 79–129. MR 2329980, DOI 10.1007/s10479-007-0178-0
MichałAdamaszek and Jonathan Ariel Barmak, On a lower bound for the connectivity of the independence complex of a graph, Discrete Math. 311 (2011), no. 21, 2566–2569. MR 2832154, DOI 10.1016/j.disc.2011.06.010
K. Adiprasito, I. Bárány, and N. Mustafa, Theorems of Carathéodory, Helly, and Tverberg without dimension, arXiv:1806.08725 (2018).
K. A. Adiprasito, P. Brinkmann, A. Padrol, P. Paták, and Z. Patáková, and R. Sanyal, Colorful simplicial depth, Minkowski sums, and generalized Gale transforms, Int. Math. Res. Not. IMRN (2017), rnx184.
Ilan Adler, The equivalence of linear programs and zero-sum games, Internat. J. Game Theory 42 (2013), no. 1, 165–177. MR 3028051, DOI 10.1007/s00182-012-0328-8
Pankaj K. Agarwal, Jiří Matoušek, and Micha Sharir, On range searching with semialgebraic sets. II, SIAM J. Comput. 42 (2013), no. 6, 2039–2062. MR 3123833, DOI 10.1137/120890855
Ron Aharoni, Eli Berger, and Ran Ziv, Independent systems of representatives in weighted graphs, Combinatorica 27 (2007), no. 3, 253–267. MR 2345810, DOI 10.1007/s00493-007-2086-y
Ron Aharoni and Ron Holzman, Fractional kernels in digraphs, J. Combin. Theory Ser. B 73 (1998), no. 1, 1–6. MR 1620603, DOI 10.1006/jctb.1997.1731
Maya Ahmed, Jesús De Loera, and Raymond Hemmecke, Polyhedral cones of magic cubes and squares, Discrete and computational geometry, Algorithms Combin., vol. 25, Springer, Berlin, 2003, pp. 25–41. MR 2038468, DOI 10.1007/978-3-642-55566-4_{2}
Martin Aigner and Günter M. Ziegler, Proofs from The Book, 5th ed., Springer-Verlag, Berlin, 2014. Including illustrations by Karl H. Hofmann. MR 3288091, DOI 10.1007/978-3-662-44205-0
J. Aisenberg, M. L. Bonet, and S. Buss, 2-d Tucker is PPA-complete. Electronic Colloquium on Computational Complexity (ECCC) 22 (2015), 163.
Iskander Aliev, Robert Bassett, Jesús A. De Loera, and Quentin Louveaux, A quantitative Doignon-Bell-Scarf theorem, Combinatorica 37 (2017), no. 3, 313–332. MR 3666782, DOI 10.1007/s00493-015-3266-9
I. Aliev, J. A. De Loera, F. Eisenbrand, T. Oertel, and R. Weismantel, The support of integer optimal solutions, SIAM J. Optim. 28 (2018), no. 3, 2152–2157. MR 3835599, DOI 10.1137/17M1162792
Iskander Aliev, Jesús A. De Loera, Timm Oertel, and Christopher O’Neill, Sparse solutions of linear Diophantine equations, SIAM J. Appl. Algebra Geom. 1 (2017), no. 1, 239–253. MR 3633776, DOI 10.1137/16M1083876
Meysam Alishahi, Colorful subhypergraphs in uniform hypergraphs, Electron. J. Combin. 24 (2017), no. 1, Paper No. 1.23, 26. MR 3609193
Meysam Alishahi and Hossein Hajiabolhassan, On the chromatic number of general Kneser hypergraphs, J. Combin. Theory Ser. B 115 (2015), 186–209. MR 3383256, DOI 10.1016/j.jctb.2015.05.010
Meysam Alishahi, Hossein Hajiabolhassan, and Frédéric Meunier, Strengthening topological colorful results for graphs, European J. Combin. 64 (2017), 27–44. MR 3658818, DOI 10.1016/j.ejc.2017.03.011
Meysam Alishahi and Frédéric Meunier, Fair splitting of colored paths, Electron. J. Combin. 24 (2017), no. 3, Paper No. 3.41, 8. MR 3691558, DOI 10.37236/7079
Noga Alon, Splitting necklaces, Adv. in Math. 63 (1987), no. 3, 247–253. MR 877785, DOI 10.1016/0001-8708(87)90055-7
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
Noga Alon, Dana Moshkovitz, and Shmuel Safra, Algorithmic construction of sets for $k$-restrictions, ACM Trans. Algorithms 2 (2006), no. 2, 153–177. MR 2253804, DOI 10.1145/1150334.1150336
Noga Alon and Douglas B. West, The Borsuk-Ulam theorem and bisection of necklaces, Proc. Amer. Math. Soc. 98 (1986), no. 4, 623–628. MR 861764, DOI 10.1090/S0002-9939-1986-0861764-9
Greg Aloupis, Stefan Langerman, Michael Soss, and Godfried Toussaint, Algorithms for bivariate medians and a Fermat-Torricelli problem for lines, Comput. Geom. 26 (2003), no. 1, 69–79. Thirteenth Canadian Conference on Computational Geometry—CCCG’01 (Waterloo, ON). MR 1989273, DOI 10.1016/S0925-7721(02)00173-6
N. Amenta, Helly-type theorems and generalized linear programming, Discrete Comput. Geom. 12 (1994), no. 3, 241–261. ACM Symposium on Computational Geometry (San Diego, CA, 1993). MR 1298910, DOI 10.1007/BF02574379
N. Amenta, M. Bern, D. Eppstein, and S.-H. Teng, Regression depth and center points, Discrete Comput. Geom. 23 (2000), no. 3, 305–323. MR 1744506, DOI 10.1007/PL00009502
Nina Amenta, Jesús A. De Loera, and Pablo Soberón, Helly’s theorem: new variations and applications, Algebraic and geometric methods in discrete mathematics, Contemp. Math., vol. 685, Amer. Math. Soc., Providence, RI, 2017, pp. 55–95. MR 3625571, DOI 10.1090/conm/685
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
Sanjeev Arora and Boaz Barak, Computational complexity, Cambridge University Press, Cambridge, 2009. A modern approach. MR 2500087, DOI 10.1017/CBO9780511804090
Megumi Asada, Ryan Chen, Florian Frick, Frederick Huang, Maxwell Polevy, David Stoner, Ling Hei Tsang, and Zoe Wellner, On Reay’s relaxed Tverberg conjecture and generalizations of Conway’s thrackle conjecture, Electron. J. Combin. 25 (2018), no. 3, Paper No. 3.16, 14. MR 3853868, DOI 10.37236/6516
Megumi Asada, Florian Frick, Vivek Pisharody, Maxwell Polevy, David Stoner, Ling Hei Tsang, and Zoe Wellner, Fair division and generalizations of Sperner- and KKM-type results, SIAM J. Discrete Math. 32 (2018), no. 1, 591–610. MR 3769696, DOI 10.1137/17M1116210
Robert J. Aumann, Subjectivity and correlation in randomized strategies, J. Math. Econom. 1 (1974), no. 1, 67–96. MR 421694, DOI 10.1016/0304-4068(74)90037-8
Gennadiy Averkov, On maximal $S$-free sets and the Helly number for the family of $S$-convex sets, SIAM J. Discrete Math. 27 (2013), no. 3, 1610–1624. MR 3106473, DOI 10.1137/110850463
Gennadiy Averkov, Bernardo González Merino, Ingo Paschke, Matthias Schymura, and Stefan Weltge, Tight bounds on discrete quantitative Helly numbers, Adv. in Appl. Math. 89 (2017), 76–101. MR 3655733, DOI 10.1016/j.aam.2017.04.003
G. Averkov and R. Weismantel, Transversal numbers over subsets of linear spaces, Adv. Geom. 12 (2012), no. 1, 19–28. MR 2911157, DOI 10.1515/advgeom.2011.028
David Avis and Oliver Friedmann, An exponential lower bound for Cunningham’s rule, Math. Program. 161 (2017), no. 1-2, Ser. A, 271–305. MR 3592779, DOI 10.1007/s10107-016-1008-4
Haris Aziz and Simon Mackenzie, 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, IEEE Computer Soc., Los Alamitos, CA, 2016, pp. 416–427. MR 3631004, DOI 10.1109/FOCS.2016.52
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, Geometric and combinatorial applications of Borsuk’s theorem, New trends in discrete and computational geometry. Springer, 1993, pp. 235–249.
Imre Bárány, Pavle V. M. Blagojević, and Günter M. Ziegler, Tverberg’s theorem at 50: extensions and counterexamples, Notices Amer. Math. Soc. 63 (2016), no. 7, 732–739. MR 3495518, DOI 10.1090/noti1415
Imre Bárány, Meir Katchalski, and János Pach, Quantitative Helly-type theorems, Proc. Amer. Math. Soc. 86 (1982), no. 1, 109–114. MR 663877, DOI 10.1090/S0002-9939-1982-0663877-X
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
I. Bárány and S. Onn, Carathéodory’s theorem, colourful and applicable, Intuitive geometry (Budapest, 1995) Bolyai Soc. Math. Stud., vol. 6, János Bolyai Math. Soc., Budapest, 1997, pp. 11–21. MR 1470753
Imre Bárány and Shmuel Onn, Colourful linear programming and its relatives, Math. Oper. Res. 22 (1997), no. 3, 550–567. MR 1467385, DOI 10.1287/moor.22.3.550
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
Imre Bárány and Pablo Soberón, Tverberg plus minus, Discrete Comput. Geom. 60 (2018), no. 3, 588–598. MR 3849141, DOI 10.1007/s00454-017-9960-1
Imre Bárány and Pablo Soberón, Tverberg’s theorem is 50 years old: a survey, Bull. Amer. Math. Soc. (N.S.) 55 (2018), no. 4, 459–492. MR 3854075, DOI 10.1090/bull/1634
Siddharth Barman, Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory’s theorem, STOC’15—Proceedings of the 2015 ACM Symposium on Theory of Computing, ACM, New York, 2015, pp. 361–369. MR 3388215
Alexander Barvinok, A course in convexity, Graduate Studies in Mathematics, vol. 54, American Mathematical Society, Providence, RI, 2002. MR 1940576, DOI 10.1090/gsm/054
Abdul Basit, Nabil H. Mustafa, Saurabh Ray, and Sarfraz Raza, Hitting simplices with points in $\Bbb R^3$, Discrete Comput. Geom. 44 (2010), no. 3, 637–644. MR 2679059, DOI 10.1007/s00454-010-9263-2
Amitabh Basu, Michele Conforti, Gérard Cornuéjols, Robert Weismantel, and Stefan Weltge, Optimality certificates for convex minimization and Helly numbers, Oper. Res. Lett. 45 (2017), no. 6, 671–674. MR 3724203, DOI 10.1016/j.orl.2017.10.002
Amitabh Basu and Timm Oertel, Centerpoints: a link between optimization and convex geometry, Integer programming and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 9682, Springer, [Cham], 2016, pp. 14–25. MR 3534718, DOI 10.1007/978-3-319-33461-5_{2}
David E. Bell, A theorem concerning the integer lattice, Studies in Appl. Math. 56 (1976/77), no. 2, 187–188. MR 462617, DOI 10.1002/sapm1977562187
C. Berge and P. Duchet, Seminar, MSHi (Maison des Sciences de l’Homme), 1983.
Dimitri P. Bertsekas, Convex optimization algorithms, Athena Scientific, Belmont, MA, 2015. MR 3558548
Dimitris Bertsimas and Santosh Vempala, Solving convex programs by random walks, J. ACM 51 (2004), no. 4, 540–556. MR 2147847, DOI 10.1145/1008731.1008733
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
B. J. Birch, On $3N$ points in a plane, Proc. Cambridge Philos. Soc. 55 (1959), 289–293. MR 109315, DOI 10.1017/s0305004100034071
A. Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1819–1872. MR 1373690
Pavle V. M. Blagojević, Aleksandra S. Dimitrijević Blagojević, and Günter M. Ziegler, Polynomial partitioning for several sets of varieties, J. Fixed Point Theory Appl. 19 (2017), no. 3, 1653–1660. MR 3692419, DOI 10.1007/s11784-016-0322-z
Pavle V. M. Blagojević, Florian Frick, Albert Haase, and Günter M. Ziegler, Topology of the Grünbaum-Hadwiger-Ramos hyperplane mass partition problem, Trans. Amer. Math. Soc. 370 (2018), no. 10, 6795–6824. MR 3841833, DOI 10.1090/tran/7528
Pavle V. M. Blagojević, Florian Frick, Albert Haase, and Günter M. Ziegler, Hyperplane mass partitions via relative equivariant obstruction theory, Doc. Math. 21 (2016), 735–771. MR 3548132
Pavle V. M. Blagojević, Florian Frick, and Günter M. Ziegler, Tverberg plus constraints, Bull. Lond. Math. Soc. 46 (2014), no. 5, 953–967. MR 3262197, DOI 10.1112/blms/bdu049
P. V. M. Blagojević, 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).
Pavle V. M. Blagojević, Benjamin Matschke, and Günter M. Ziegler, Optimal bounds for a colorful Tverberg-Vrećica type problem, Adv. Math. 226 (2011), no. 6, 5198–5215. MR 2775898, DOI 10.1016/j.aim.2011.01.009
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
Pavle V. M. Blagojević and Pablo Soberón, Thieves can make sandwiches, Bull. Lond. Math. Soc. 50 (2018), no. 1, 108–123. MR 3778548, DOI 10.1112/blms.12109
Pavle V. M. Blagojević and Günter M. Ziegler, Beyond the Borsuk-Ulam theorem: the topological Tverberg story, A journey through discrete mathematics, Springer, Cham, 2017, pp. 273–341. MR 3726602
Avrim Blum, Sariel Har-Peled, and Benjamin Raichel, Sparse approximation via generating point sets, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2016, pp. 548–557. MR 3478416, DOI 10.1137/1.9781611974331.ch40
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
Endre Boros and Vladimir Gurvich, Perfect graphs are kernel solvable, Discrete Math. 159 (1996), no. 1-3, 35–55. MR 1415280, DOI 10.1016/0012-365X(95)00096-F
Karol Borsuk, On the imbedding of systems of compacta in simplicial complexes, Fund. Math. 35 (1948), 217–234. MR 28019, DOI 10.4064/fm-35-1-217-234
Stephen Boyd and Lieven Vandenberghe, Convex optimization, Cambridge University Press, Cambridge, 2004. MR 2061575, DOI 10.1017/CBO9780511804441
Steven J. Brams and Alan D. Taylor, Fair division, Cambridge University Press, Cambridge, 1996. From cake-cutting to dispute resolution. MR 1381896, DOI 10.1017/CBO9780511598975
Steven J. Brams, Michael A. Jones, and Christian Klamler, $N$-person cake-cutting: there may be no perfect division, Amer. Math. Monthly 120 (2013), no. 1, 35–47. MR 3007365, DOI 10.4169/amer.math.monthly.120.01.035
Steven J. Brams, D. Marc Kilgour, and Christian Klamler, How to divide things fairly, Math. Mag. 88 (2015), no. 5, 338–348. MR 3470684, DOI 10.4169/math.mag.88.5.338
Silouanos Brazitikos, Quantitative Helly-type theorem for the diameter of convex sets, Discrete Comput. Geom. 57 (2017), no. 2, 494–505. MR 3602863, DOI 10.1007/s00454-016-9840-0
H. Brönnimann and M. T. Goodrich, Almost optimal set covers in finite VC-dimension, Discrete Comput. Geom. 14 (1995), no. 4, 463–479. ACM Symposium on Computational Geometry (Stony Brook, NY, 1994). MR 1360948, DOI 10.1007/BF02570718
Richard A. Brualdi and Herbert J. Ryser, Combinatorial matrix theory, Encyclopedia of Mathematics and its Applications, vol. 39, Cambridge University Press, Cambridge, 1991. MR 1130611, DOI 10.1017/CBO9781107325708
Winfried Bruns, Joseph Gubeladze, Martin Henk, Alexander Martin, and Robert Weismantel, A counterexample to an integer analogue of Carathéodory’s theorem, J. Reine Angew. Math. 510 (1999), 179–185. MR 1696095, DOI 10.1515/crll.1999.045
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
Boris Bukh, Jiří Matoušek, and Gabriel Nivasch, Stabbing simplices by points and flats, Discrete Comput. Geom. 43 (2010), no. 2, 321–338. MR 2579699, DOI 10.1007/s00454-008-9124-4
Giuseppe Calafiore and M. C. Campi, Uncertain convex programs: randomized solutions and confidence levels, Math. Program. 102 (2005), no. 1, Ser. A, 25–46. MR 2115479, DOI 10.1007/s10107-003-0499-y
Giuseppe C. Calafiore and Marco C. Campi, The scenario approach to robust control design, IEEE Trans. Automat. Control 51 (2006), no. 5, 742–753. MR 2232597, DOI 10.1109/TAC.2006.875041
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
Bernd Carl, Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces, Ann. Inst. Fourier (Grenoble) 35 (1985), no. 3, 79–118. MR 810669
G. D. Chakerian and S. K. Stein, Some intersection properties of convex bodies, Proc. Amer. Math. Soc. 18 (1967), 109–112. MR 206818, DOI 10.1090/S0002-9939-1967-0206818-3
G. D. Chakerian, Intersection and covering properties of convex sets, Amer. Math. Monthly 76 (1969), 753–766. MR 250193, DOI 10.2307/2317863
Timothy M. Chan, An optimal randomized algorithm for maximum Tukey depth, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2004, pp. 430–436. MR 2291081
Timothy M. Chan, Improved deterministic algorithms for linear programming in low dimensions, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2016, pp. 1213–1219. MR 3478460, DOI 10.1137/1.9781611974331.ch84
Timothy M. Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe, Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2012, pp. 1576–1585. MR 3205315
Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete Comput. Geom. 9 (1993), no. 2, 145–158. MR 1194032, DOI 10.1007/BF02189314
Bernard Chazelle, The discrepancy method, Cambridge University Press, Cambridge, 2000. Randomness and complexity. MR 1779341, DOI 10.1017/CBO9780511626371
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.
Dan Chen, Olivier Devillers, John Iacono, Stefan Langerman, and Pat Morin, Oja centers and centers of gravity, Comput. Geom. 46 (2013), no. 2, 140–147. MR 2983943, DOI 10.1016/j.comgeo.2012.04.004
P.-A. Chen, On the multichromatic number of $s$-stable Kneser graphs, J. Graph Theory 79 (2015), no. 3, 233–248.
P.-A. Chen, On the chromatic number of almost $s$-stable Kneser graphs, arXiv:1711.06621 (2017).
Peng-An Chen, On the multichromatic number of $s$-stable Kneser graphs, J. Graph Theory 79 (2015), no. 3, 233–248. MR 3346141, DOI 10.1002/jgt.21826
Xi Chen and Xiaotie Deng, On the complexity of 2D discrete fixed point problem, Theoret. Comput. Sci. 410 (2009), no. 44, 4448–4456. MR 2561571, DOI 10.1016/j.tcs.2009.07.052
Xi Chen, Xiaotie Deng, and Shang-Hua Teng, Settling the complexity of computing two-player Nash equilibria, J. ACM 56 (2009), no. 3, Art. 14, 57. MR 2536129, DOI 10.1145/1516512.1516516
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óth, Eds.), CRC Press LLC, 2016, to appear.
Stephen R. Chestnut, Robert Hildebrand, and Rico Zenklusen, Sublinear bounds for a quantitative Doignon-Bell-Scarf theorem, SIAM J. Discrete Math. 32 (2018), no. 1, 352–371. MR 3757097, DOI 10.1137/16M1100095
S. J. Chung, NP-completeness of the linear complementarity problem, J. Optim. Theory Appl. 60 (1989), no. 3, 393–399. MR 993006, DOI 10.1007/BF00940344
V. Chvátal, On the computational complexity of finding a kernel, Tech. Rep., Centre de Recherches Mathématiques, Université de Montréal, 1973.
Kenneth L. Clarkson, New applications of random sampling in computational geometry, Discrete Comput. Geom. 2 (1987), no. 2, 195–222. MR 884226, DOI 10.1007/BF02187879
Kenneth L. Clarkson, Las Vegas algorithms for linear and integer programming when the dimension is small, J. Assoc. Comput. Mach. 42 (1995), no. 2, 488–499. MR 1409744, DOI 10.1145/201019.201036
Kenneth L. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, and Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom. 5 (1990), no. 2, 99–160. MR 1032370, DOI 10.1007/BF02187783
Kenneth L. Clarkson, David Eppstein, Gary L. Miller, Carl Sturtivant, and Shang-Hua Teng, Approximating center points with iterative Radon points, Internat. J. Comput. Geom. Appl. 6 (1996), no. 3, 357–377. ACM Symposium on Computational Geometry (San Diego, CA, 1993). MR 1409651, DOI 10.1142/S021819599600023X
Kenneth L. Clarkson and Peter W. Shor, Applications of random sampling in computational geometry. II, Discrete Comput. Geom. 4 (1989), no. 5, 387–421. MR 1014736, DOI 10.1007/BF02187740
John Cloutier, Kathryn L. Nyman, and Francis Edward Su, Two-player envy-free multi-cake division, Math. Social Sci. 59 (2010), no. 1, 26–37. MR 2587345, DOI 10.1016/j.mathsocsci.2009.09.002
W. Cook, J. Fonlupt, and A. Schrijver, An integer analogue of Carathéodory’s theorem, J. Combin. Theory Ser. B 40 (1986), no. 1, 63–70. MR 830593, DOI 10.1016/0095-8956(86)90064-X
Richard W. Cottle, Jong-Shi Pang, and Richard E. Stone, The linear complementarity problem, Classics in Applied Mathematics, vol. 60, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2009. Corrected reprint of the 1992 original [ MR1150683]. MR 3396730, DOI 10.1137/1.9780898719000.ch1
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.
W. H. Cunningham, Theoretical properties of the network simplex method, Math. Oper. Res. 4 (1979), no. 2, 196–208. MR 543931, DOI 10.1287/moor.4.2.196
George B. Dantzig, Constructive proof of the Min-Max theorem, Pacific J. Math. 6 (1956), 25–33. MR 81807
Ludwig Danzer, Branko Grünbaum, and Victor Klee, Helly’s theorem and its relatives, Proc. Sympos. Pure Math., Vol. VII, Amer. Math. Soc., Providence, R.I., 1963, pp. 101–180. MR 0157289
Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 71–78. MR 2277132, DOI 10.1145/1132516.1132527
Ruchira S. Datta, Universality of Nash equilibria, Math. Oper. Res. 28 (2003), no. 3, 424–432. MR 1997243, DOI 10.1287/moor.28.3.424.16397
Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Computational geometry, 3rd ed., Springer-Verlag, Berlin, 2008. Algorithms and applications. MR 2723879, DOI 10.1007/978-3-540-77974-2
Jesús A. De Loera, Raymond Hemmecke, and Matthias Köppe, Algebraic and geometric ideas in the theory of discrete optimization, MOS-SIAM Series on Optimization, vol. 14, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2013. MR 3024570
J. A. De Loera, T. Hogan, F. Meunier, and N. Mustafa, Integer and mixed integer Tverberg numbers, Proceedings European Congress of Computational Geometry (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).
Jesús A. De Loera, Reuben N. La Haye, David Rolnick, and Pablo Soberón, Quantitative combinatorial geometry for continuous parameters, Discrete Comput. Geom. 57 (2017), no. 2, 318–334. MR 3602856, DOI 10.1007/s00454-016-9857-4
J. A. De Loera, R. N. La Haye, D. Oliveros, and E. Roldán-Pensado, Chance-constrained convex mixed-integer optimization and beyond: two sampling algorithms within $S$-optimization, J. Convex Anal. 25 (2018), no. 1, 201–218. MR 3778498
J. A. De Loera, R. N. La Haye, D. Oliveros, and E. Roldán-Pensado, Helly numbers of algebraic subsets of $\Bbb R^d$ and an extension of Doignon’s theorem, Adv. Geom. 17 (2017), no. 4, 473–482. MR 3714450, DOI 10.1515/advgeom-2017-0028
Jesus A. De Loera, Reuben N. La Haye, David Rolnick, and Pablo Soberón, Quantitative Tverberg theorems over lattices and other discrete sets, Discrete Comput. Geom. 58 (2017), no. 2, 435–448. MR 3679944, DOI 10.1007/s00454-016-9858-3
Jesus A. De Loera, Elisha Peterson, and Francis Edward Su, A polytopal generalization of Sperner’s lemma, J. Combin. Theory Ser. A 100 (2002), no. 1, 1–26. MR 1932067, DOI 10.1006/jcta.2002.3274
Jesús A. De Loera, Jörg Rambau, and Francisco Santos, Triangulations, Algorithms and Computation in Mathematics, vol. 25, Springer-Verlag, Berlin, 2010. Structures for algorithms and applications. MR 2743368, DOI 10.1007/978-3-642-12971-1
Mark de Longueville, A course in topological combinatorics, Universitext, Springer, New York, 2013. MR 2976494, DOI 10.1007/978-1-4419-7910-0
Mark de Longueville and Rade T. Živaljević, Splitting multidimensional necklaces, Adv. Math. 218 (2008), no. 3, 926–939. MR 2414326, DOI 10.1016/j.aim.2008.02.003
Éric Colin de Verdière, Grégory Ginot, and Xavier Goaoc, Helly numbers of acyclic families, Adv. Math. 253 (2014), 163–193. MR 3148550, DOI 10.1016/j.aim.2013.11.004
D. de Werra, The combinatorics of timetabling, European J. Oper. Res. 96 (1997), no. 3, 504–513.
X. Deng, Z. Feng, and R. Kulkarni, Octahedral tucker is PPA-complete, Electronic Colloquium on Computational Complexity (ECCC) (2017), vol. 24, p. 118.
Xiaotie Deng, Qi Qi, and Amin Saberi, Algorithmic solutions for envy-free cake cutting, Oper. Res. 60 (2012), no. 6, 1461–1476. MR 3009176, DOI 10.1287/opre.1120.1116
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
Reinhard Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 2005. MR 2159259
Michael Gene Dobbins, A point in a $nd$-polytope is the barycenter of $n$ points in its $d$-faces, Invent. Math. 199 (2015), no. 1, 287–292. MR 3294963, DOI 10.1007/s00222-014-0523-2
C. T. J. Dodson and Phillip E. Parker, A user’s guide to algebraic topology, Mathematics and its Applications, vol. 387, Kluwer Academic Publishers Group, Dordrecht, 1997. MR 1430097, DOI 10.1007/978-1-4615-6309-9
Jean-Paul Doignon, Convexity in cristallographical lattices, J. Geom. 3 (1973), 71–85. MR 387090, DOI 10.1007/BF01949705
Albrecht Dold, Simple proofs of some Borsuk-Ulam results, Proceedings of the Northwestern Homotopy Theory Conference (Evanston, Ill., 1982) Contemp. Math., vol. 19, Amer. Math. Soc., Providence, RI, 1983, pp. 65–69. MR 711043, DOI 10.1090/conm/019/711043
V. Dol’nikov, Transversals of families of sets. Studies in the theory of functions of several real variables (Russian) (1981), 30–36.
L. E. Dubins and E. H. Spanier, How to cut a cake fairly, Amer. Math. Monthly 68 (1961), 1–17. MR 129031, DOI 10.2307/2311357
P. Duchet, Graphes noyau-parfaits, Ann. Discrete Math. 9 (1980), 93–101 (French, with English summary). MR 597359
Pierre Duchet, Convexity in combinatorial structures, Proceedings of the 14th winter school on abstract analysis (Srní, 1986), 1987, pp. 261–293. MR 920860
Pierre Duchet and Henri Meyniel, Une généralisation du théorème de Richardson sur l’existence de noyaux dans les graphes orientés, Discrete Math. 43 (1983), no. 1, 21–27 (French, with English summary). MR 680300, DOI 10.1016/0012-365X(83)90017-1
Arnaud Durand, Miki Hermann, and Laurent Juban, On the complexity of recognizing the Hilbert basis of a linear Diophantine system, Theoret. Comput. Sci. 270 (2002), no. 1-2, 625–642. MR 1871087, DOI 10.1016/S0304-3975(01)00017-2
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
Jürgen Eckhoff, Helly, Radon, and Carathéodory type theorems, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 389–448. MR 1242986
Jürgen Eckhoff, The partition conjecture, Discrete Math. 221 (2000), no. 1-3, 61–78. Selected papers in honor of Ludwig Danzer. MR 1778908, DOI 10.1016/S0012-365X(99)00386-6
Jack Edmonds and Rick Giles, A min-max relation for submodular functions on graphs, Studies in integer programming (Proc. Workshop, Bonn, 1975) Ann. of Discrete Math., Vol. 1, North-Holland, Amsterdam, 1977, pp. 185–204. MR 0460169
Friedrich Eisenbrand and Gennady Shmonin, Carathéodory bounds for integer cones, Oper. Res. Lett. 34 (2006), no. 5, 564–568. MR 2238405, DOI 10.1016/j.orl.2005.09.008
P. Erdös, On sets of distances of $n$ points, Amer. Math. Monthly 53 (1946), 248–250. MR 15796, DOI 10.2307/2305092
J. Erickson, New lower bounds for Hopcroft’s problem, Discrete Comput. Geom. 16 (1996), no. 4, 389–418. Eleventh Annual Symposium on Computational Geometry (Vancouver, BC, 1995). MR 1414963, DOI 10.1007/BF02712875
Kousha Etessami and Mihalis Yannakakis, On the complexity of Nash equilibria and other fixed points, SIAM J. Comput. 39 (2010), no. 6, 2531–2597. MR 2644357, DOI 10.1137/080720826
Guy Even, Dror Rawitz, and Shimon Shahar, Hitting sets when the VC-dimension is small, Inform. Process. Lett. 95 (2005), no. 2, 358–362. MR 2149262, DOI 10.1016/j.ipl.2005.03.010
Ky Fan, A generalization of Tucker’s combinatorial lemma with topological applications, Ann. of Math. (2) 56 (1952), 431–437. MR 51506, DOI 10.2307/1969651
Ky Fan, Simplicial maps from an orientable $n$-pseudomanifold into $S^{m}$ with the octahedral triangulation, J. Combinatorial Theory 2 (1967), 588–602. MR 214048
Benson Farb, Group actions and Helly’s theorem, Adv. Math. 222 (2009), no. 5, 1574–1588. MR 2555905, DOI 10.1016/j.aim.2009.06.004
Aris Filos-Ratsikas and Paul W. Goldberg, Consensus halving is PPA-complete, STOC’18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2018, pp. 51–64. MR 3826233, DOI 10.1145/3188745.3188880
A. Filos-Ratsikas and P. W. Goldberg, The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches, arXiv:1805.12559 (2018).
A. I. Flores, Über die Existenz $n$-dimensionaler Komplexe, die nicht in den $\mathbb {R}^{2n}$ topologisch einbettbar sind, Ergeb. Math. Kolloqu. 5 (1933), 17–24.
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.
Robert M. Freund and Michael J. Todd, A constructive proof of Tucker’s combinatorial lemma, J. Combin. Theory Ser. A 30 (1981), no. 3, 321–325. MR 618536, DOI 10.1016/0097-3165(81)90027-3
F. Frick, Counterexamples to the topological Tverberg conjecture, Oberwolfach Reports 12, (1) (2015), 318–321.
Florian Frick, Intersection patterns of finite sets and of convex sets, Proc. Amer. Math. Soc. 145 (2017), no. 7, 2827–2842. MR 3637933, DOI 10.1090/proc/13443
F. Frick, Chromatic numbers of stable Kneser hypergraphs via topological Tverberg-type theorems, Int. Math. Res. Not. IMRN (2018).
F. Frick, K. Houston-Edwards, and F. Meunier, Achieving rental harmony with a secretive roommate, Amer. Math. Monthly (to appear, 2017).
F. Frick, and S. Zerbib, Colorful coverings of polytopes and piercing numbers of colorful $d$-intervals, Combinatorica (to appear, 2018).
Oliver Friedmann, 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., vol. 6655, Springer, Heidelberg, 2011, pp. 192–206. MR 2820908, DOI 10.1007/978-3-642-20807-2_{1}6
Radoslav Fulek, Andreas F. Holmsen, and János Pach, Intersecting convex sets by rays, Discrete Comput. Geom. 42 (2009), no. 3, 343–358. MR 2519884, DOI 10.1007/s00454-009-9163-5
Radoslav Fulek and János Pach, A computational approach to Conway’s thrackle conjecture, Comput. Geom. 44 (2011), no. 6-7, 345–355. MR 2785903, DOI 10.1016/j.comgeo.2011.02.001
David Gale, The game of Hex and the Brouwer fixed-point theorem, Amer. Math. Monthly 86 (1979), no. 10, 818–827. MR 551501, DOI 10.2307/2320146
D. Gale, Equilibrium in a discrete exchange economy with money, Internat. J. Game Theory 13 (1984), no. 1, 61–64. MR 741586, DOI 10.1007/BF01769865
H. Galeana-Sánchez and V. Neumann Lara, On kernels and semikernels of digraphs, Discrete Math. 48 (1984), no. 1, 67–76. MR 732201, DOI 10.1016/0012-365X(84)90131-6
A. Garber, On Helly number for crystals and cut-and-project sets, arXiv:1605.07881 (2016).
Natalia García-Colín, Miguel Raggi, and Edgardo Roldán-Pensado, A note on the tolerant Tverberg theorem, Discrete Comput. Geom. 58 (2017), no. 3, 746–754. MR 3690670, DOI 10.1007/s00454-017-9875-x
Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod, ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria, Automata, languages, and programming. Part I, Lecture Notes in Comput. Sci., vol. 9134, Springer, Heidelberg, 2015, pp. 554–566. MR 3382467, DOI 10.1007/978-3-662-47672-7_{4}5
B. Gärtner, J. Matoušek, L. Rüst, and P. Škovroň, Violator spaces: structure and algorithms, Discrete Appl. Math. 156 (2008), no. 11, 2124–2141. MR 2437006, DOI 10.1016/j.dam.2007.08.048
P. Giannopoulos, M. Konzack, and W. Mulzer, Low-crossing spanning trees: an alternative proof and experiments, Proceedings European Workshop on Computational Geometry (2014).
Dion Gijswijt and Guus Regts, Polyhedra with the integer Carathéodory property, J. Combin. Theory Ser. B 102 (2012), no. 1, 62–70. MR 2871767, DOI 10.1016/j.jctb.2011.04.004
Joseph Gil, William Steiger, and Avi Wigderson, Geometric medians, Discrete Math. 108 (1992), no. 1-3, 37–51. Topological, algebraical and combinatorial structures. Frolík’s memorial volume. MR 1189827, DOI 10.1016/0012-365X(92)90658-3
Itzhak Gilboa and Eitan Zemel, Nash and correlated equilibria: some complexity considerations, Games Econom. Behav. 1 (1989), no. 1, 80–93. MR 1000049, DOI 10.1016/0899-8256(89)90006-7
F. R. Giles and W. R. Pulleyblank, Total dual integrality and integer polyhedra, Linear Algebra Appl. 25 (1979), 191–196. MR 528725, DOI 10.1016/0024-3795(79)90018-1
Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner, Bounding Helly numbers via Betti numbers, A journey through discrete mathematics, Springer, Cham, 2017, pp. 407–447. MR 3726608
Michel X. Goemans and Thomas Rothvoß, Polynomiality for bin packing with a constant number of item types, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2014, pp. 830–839. MR 3376421, DOI 10.1137/1.9781611973402.61
Charles H. Goldberg and Douglas B. West, Bisection of circle colorings, SIAM J. Algebraic Discrete Methods 6 (1985), no. 1, 93–106. MR 772181, DOI 10.1137/0606010
Paul W. Goldberg and Christos H. Papadimitriou, TFNP: an update, Algorithms and complexity, Lecture Notes in Comput. Sci., vol. 10236, Springer, Cham, 2017, pp. 3–9. MR 3657533, DOI 10.1007/978-3-319-57586-5_{1}
Jack E. Graver, On the foundations of linear and integer linear programming. I, Math. Programming 9 (1975), no. 2, 207–226. MR 386673, DOI 10.1007/BF01681344
Mikhail Gromov, Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry, Geom. Funct. Anal. 20 (2010), no. 2, 416–526. MR 2671284, DOI 10.1007/s00039-010-0073-8
P. Gruber and J. Wills, Eds. Handbook of Convex Geometry. North-Holland, Amsterdam, 1993.
Peter M. Gruber, Convex and discrete geometry, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 336, Springer, Berlin, 2007. MR 2335496
Larry Guth, Polynomial partitioning for a set of varieties, Math. Proc. Cambridge Philos. Soc. 159 (2015), no. 3, 459–469. MR 3413420, DOI 10.1017/S0305004115000468
Larry Guth, Polynomial methods in combinatorics, University Lecture Series, vol. 64, American Mathematical Society, Providence, RI, 2016. MR 3495952, DOI 10.1090/ulect/064
Larry Guth and Nets Hawk Katz, On the Erdős distinct distances problem in the plane, Ann. of Math. (2) 181 (2015), no. 1, 155–190. MR 3272924, DOI 10.4007/annals.2015.181.1.2
E. Győri, On division of graphs to connected subgraphs, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), (1976), vol. 1, pp. 485–494.
Geňa Hahn and Claude Tardif, Graph homomorphisms: structure and symmetry, Graph symmetry (Montreal, PQ, 1996) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 497, Kluwer Acad. Publ., Dordrecht, 1997, pp. 107–166. MR 1468789, DOI 10.1007/978-94-015-8937-6_{4}
Bernhard Hanke, Raman Sanyal, Carsten Schultz, and Günter M. Ziegler, Combinatorial Stokes formulas via minimal resolutions, J. Combin. Theory Ser. A 116 (2009), no. 2, 404–420. MR 2475024, DOI 10.1016/j.jcta.2008.06.009
S. Har-Peled, Approximating Spanning Trees with Low Crossing Number, arXiv:0907.1131 (2009).
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
P. E. Haxell, A condition for matchability in hypergraphs, Graphs Combin. 11 (1995), no. 3, 245–248. MR 1354745, DOI 10.1007/BF01793010
S. Hell, Tverberg-type theorems, and the Fractional Helly property, PhD thesis, T.U. Berlin, 2006.
Stephan Hell, On the number of Tverberg partitions in the prime power case, European J. Combin. 28 (2007), no. 1, 347–355. MR 2261824, DOI 10.1016/j.ejc.2005.06.005
Stephan Hell, On the number of Birch partitions, Discrete Comput. Geom. 40 (2008), no. 4, 586–594. MR 2453329, DOI 10.1007/s00454-008-9083-9
A. J. Hoffman, Binding constraints and Helly numbers, Second International Conference on Combinatorial Mathematics (New York, 1978) Ann. New York Acad. Sci., vol. 319, New York Acad. Sci., New York, 1979, pp. 284–288. MR 556036
Andreas F. Holmsen, The intersection of a matroid and an oriented matroid, Adv. Math. 290 (2016), 1–14. MR 3451916, DOI 10.1016/j.aim.2015.11.040
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
Rephael Wenger, Helly-type theorems and geometric transversals, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 63–82. MR 1730160
Andreas F. Holmsen and Roman Karasev, Colorful theorems for strong convexity, Proc. Amer. Math. Soc. 145 (2017), no. 6, 2713–2726. MR 3626523, DOI 10.1090/proc/13405
A. F. Holmsen, M. Kim, and S. Lee, Nerves, minors, and piercing numbers, arXiv:1706.05181 (2017).
K. Houston-Edwards, Splitting rent with triangles, Infinite series, PBS digital studios February 23, 2017. https://www.youtube.com/watch?v=48oBEvpdYSE.
S. Jadhav and A. Mukhopadhyay, Computing a centerpoint of a finite planar set of points in linear time, Discrete Comput. Geom. 12 (1994), no. 3, 291–312. ACM Symposium on Computational Geometry (San Diego, CA, 1993). MR 1298913, DOI 10.1007/BF02574382
J. Jonsson, On the chromatic number of generalized stable Kneser graphs, http://www.math.kth.se/~jakobj/doc/submitted/stablekneser.pdf (2012).
Gil Kalai, Intersection patterns of convex sets, Israel J. Math. 48 (1984), no. 2-3, 161–174. MR 770699, DOI 10.1007/BF02761162
G. Kalai, A subexponential randomized simplex algorithm, Proceedings ACM Symposium on Theory of computing (STOC) (1992), pp. 475–482.
Gil Kalai, Combinatorics and convexity, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994) Birkhäuser, Basel, 1995, pp. 1363–1374. MR 1404038
Gil Kalai, Algebraic shifting, Computational commutative algebra and combinatorics (Osaka, 1999) Adv. Stud. Pure Math., vol. 33, Math. Soc. Japan, Tokyo, 2002, pp. 121–163. MR 1890098, DOI 10.2969/aspm/03310121
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.
Gil Kalai and Roy Meshulam, A topological colorful Helly theorem, Adv. Math. 191 (2005), no. 2, 305–311. MR 2103215, DOI 10.1016/j.aim.2004.03.009
Ravi Kannan and Thorsten Theobald, Games of fixed rank: a hierarchy of bimatrix games, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2007, pp. 1124–1132. MR 2485264
R. N. Karasëv, Dual theorems on a central point and their generalizations, Mat. Sb. 199 (2008), no. 10, 41–62 (Russian, with Russian summary); English transl., Sb. Math. 199 (2008), no. 9-10, 1459–1479. MR 2473811, DOI 10.1070/SM2008v199n10ABEH003968
R. N. Karasëv, Topological methods in combinatorial geometry, Uspekhi Mat. Nauk 63 (2008), no. 6(384), 39–90 (Russian, with Russian summary); English transl., Russian Math. Surveys 63 (2008), no. 6, 1031–1078. MR 2492772, DOI 10.1070/RM2008v063n06ABEH004578
R. N. Karasev, Tverberg-type theorems for intersecting by rays, Discrete Comput. Geom. 45 (2011), no. 2, 340–347. MR 2765534, DOI 10.1007/s00454-010-9294-8
Roman Karasev, A simpler proof of the Boros-Füredi-Bárány-Pach-Gromov theorem, Discrete Comput. Geom. 47 (2012), no. 3, 492–495. MR 2891243, DOI 10.1007/s00454-011-9332-1
N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984), no. 4, 373–395. MR 779900, DOI 10.1007/BF02579150
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
David C. Kay and Eugene W. Womble, Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers, Pacific J. Math. 38 (1971), 471–485. MR 310766
L. G. Khachiyan, Polynomial algorithms in linear programming, USSR Computational Mathematics and Mathematical Physics 20 1 (1980), 53–72.
Tamás Király and Júlia Pap, A note on kernels and Sperner’s lemma, Discrete Appl. Math. 157 (2009), no. 15, 3327–3331. MR 2554802, DOI 10.1016/j.dam.2009.07.005
Victor Klee and George J. Minty, 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), Academic Press, New York, 1972, pp. 159–175. MR 0332165
Dmitry Kozlov, Combinatorial algebraic topology, Algorithms and Computation in Mathematics, vol. 21, Springer, Berlin, 2008. MR 2361455, DOI 10.1007/978-3-540-71962-5
Daniel Kráľ, Lukáš Mach, and Jean-Sébastien Sereni, A new lower bound based on Gromov’s method of selecting heavily covered points, Discrete Comput. Geom. 48 (2012), no. 2, 487–498. MR 2946458, DOI 10.1007/s00454-012-9419-3
M. A. Krasnosel′skiĭ, On a proof of Helly’s theorem on sets of convex bodies with common points, Voronež. Gos. Univ. Trudy. Fiz.-Mat. Sb. 33 (1954), 19–20 (Russian). MR 0075615
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.
Shankar Krishnan, Nabil H. Mustafa, and Suresh Venkatasubramanian, Statistical data depth and the graphics hardware, Data depth: robust multivariate analysis, computational geometry and applications, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 72, Amer. Math. Soc., Providence, RI, 2006, pp. 223–246. MR 2343123, DOI 10.1090/dimacs/072/15
Andrey Kupavskii, Nabil H. Mustafa, and János Pach, New lower bounds for $\epsilon$-nets, 32nd International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform., vol. 51, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, pp. Art. No. 54, 16. MR 3540896
Stefan Langerman and William Steiger, The complexity of hyperplane depth in the plane, Discrete Comput. Geom. 30 (2003), no. 2, 299–309. U.S.-Hungarian Workshops on Discrete Geometry and Convexity (Budapest, 1999/Auburn, AL, 2000). MR 2007967, DOI 10.1007/s00454-003-0011-x
Nicolas Lebert, Frédéric Meunier, and Quentin Carbonneaux, Envy-free two-player $m$-cake and three-player two-cake divisions, Oper. Res. Lett. 41 (2013), no. 6, 607–610. MR 3131831, DOI 10.1016/j.orl.2013.07.010
C. E. Lemke and J. T. Howson Jr., Equilibrium points of bimatrix games, J. Soc. Indust. Appl. Math. 12 (1964), 413–423. MR 173556
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.
Regina Y. Liu, On a notion of simplicial depth, Proc. Nat. Acad. Sci. U.S.A. 85 (1988), no. 6, 1732–1734. MR 930658, DOI 10.1073/pnas.85.6.1732
Chi-Yuan Lo, J. Matoušek, and W. Steiger, Algorithms for ham-sandwich cuts, Discrete Comput. Geom. 11 (1994), no. 4, 433–452. MR 1273227, DOI 10.1007/BF02574017
L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972), no. 3, 253–267. MR 302480, DOI 10.1016/0012-365X(72)90006-4
L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), no. 3, 319–324. MR 514625, DOI 10.1016/0097-3165(78)90022-5
László Lovász, Graph minor theory, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 1, 75–86. MR 2188176, DOI 10.1090/S0273-0979-05-01088-8
László Lovász and Michael D. Plummer, Matching theory, AMS Chelsea Publishing, Providence, RI, 2009. Corrected reprint of the 1986 original [MR0859549]. MR 2536865, DOI 10.1090/chel/367
L. Lyusternik and L. Schnirel’mann, Méthodes topologiques dans les problèmes variationnels, Gosudarstvennoe Izdat. (1930); French transl., Actualités Sci. Indust., no. 118, Hermann, Paris, 1934.
M. Krein and D. Milman, On extreme points of regular convex sets, Studia Math. 9 (1940), 133–138 (English, with Ukrainian summary). MR 4990, DOI 10.4064/sm-9-1-133-138
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
Leonardo Martínez-Sandoval, Edgardo Roldán-Pensado, and Natan Rubin, Further consequences of the colorful Helly hypothesis, 34th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform., vol. 99, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, pp. Art. No. 59, 14. MR 3824303
L. Martínez-Sandoval and R. Tamam, Depth with respect to a family of convex sets, arXiv:1612.03435 (2016).
Jiří Matoušek, Efficient partition trees, Discrete Comput. Geom. 8 (1992), no. 3, 315–334. ACM Symposium on Computational Geometry (North Conway, NH, 1991). MR 1174360, DOI 10.1007/BF02293051
J. Matoušek, Geometric Discrepancy: An Illustrated Guide, Springer, 1999.
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
Jiří Matoušek, Using the Borsuk-Ulam theorem, Universitext, Springer-Verlag, Berlin, 2003. Lectures on topological methods in combinatorics and geometry; Written in cooperation with Anders Björner and Günter M. Ziegler. MR 1988723
Jiří Matoušek, A combinatorial proof of Kneser’s conjecture, Combinatorica 24 (2004), no. 1, 163–170. MR 2057690, DOI 10.1007/s00493-004-0011-1
Jiří Matoušek, Bounded VC-dimension implies a fractional Helly theorem, Discrete Comput. Geom. 31 (2004), no. 2, 251–255. MR 2060639, DOI 10.1007/s00454-003-2859-z
Jiří Matoušek, Thirty-three miniatures, Student Mathematical Library, vol. 53, American Mathematical Society, Providence, RI, 2010. Mathematical and algorithmic applications of linear algebra. MR 2656313, DOI 10.1090/stml/053
J. Matoušek and B. Gärtner, Understanding and using linear programming, Springer Science & Business Media, 2007.
Jiří Matoušek and Günter M. Ziegler, Topological lower bounds for the chromatic number: a hierarchy, Jahresber. Deutsch. Math.-Verein. 106 (2004), no. 2, 71–90. MR 2073516
J. Matoušek, M. Sharir, and E. Welzl, A subexponential bound for linear programming, Algorithmica 16 (1996), no. 4-5, 498–516. MR 1407586, DOI 10.1007/s004539900062
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
Jiří Matoušek and Uli Wagner, On Gromov’s method of selecting heavily covered points, Discrete Comput. Geom. 52 (2014), no. 1, 1–33. MR 3231028, DOI 10.1007/s00454-014-9584-7
Richard D. McKelvey and Andrew McLennan, Computation of equilibria in finite games, Handbook of computational economics, Vol. I, Handbooks in Econom., vol. 13, North-Holland, Amsterdam, 1996, pp. 87–142. MR 1416607
Andrew McLennan, The expected number of Nash equilibria of a normal form game, Econometrica 73 (2005), no. 1, 141–174. MR 2115633, DOI 10.1111/j.1468-0262.2005.00567.x
Andrew McLennan and Rabee Tourky, Using volume to prove Sperner’s lemma, Econom. Theory 35 (2008), no. 3, 593–597. MR 2398817, DOI 10.1007/s00199-007-0257-0
Roy Meshulam, The clique complex and hypergraph matching, Combinatorica 21 (2001), no. 1, 89–94. MR 1805715, DOI 10.1007/s004930170006
Roy Meshulam, Domination numbers and homology, J. Combin. Theory Ser. A 102 (2003), no. 2, 321–330. MR 1979537, DOI 10.1016/S0097-3165(03)00045-1
F. Meunier, A $\mathbb {Z}_q$-Fan theorem, Tech. Rep., Laboratoire Leibniz-IMAG, Grenoble, 2005.
Frédéric Meunier, Sperner labellings: a combinatorial approach, J. Combin. Theory Ser. A 113 (2006), no. 7, 1462–1475. MR 2259071, DOI 10.1016/j.jcta.2006.01.006
Frédéric Meunier, The chromatic number of almost stable Kneser hypergraphs, J. Combin. Theory Ser. A 118 (2011), no. 6, 1820–1828. MR 2793613, DOI 10.1016/j.jcta.2011.02.010
Frédéric Meunier and Antoine Deza, A further generalization of the colourful Carathéodory theorem, Discrete geometry and optimization, Fields Inst. Commun., vol. 69, Springer, New York, 2013, pp. 179–190. MR 3156783, DOI 10.1007/978-3-319-00200-2_{1}1
Frédéric Meunier, Wolfgang Mulzer, Pauline Sarrabezolles, and Yannik Stein, The rainbow at the end of the line—a $\mathsf {PPAD}$ formulation of the colorful Carathéodory theorem with applications, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2017, pp. 1342–1351. MR 3627816, DOI 10.1137/1.9781611974782.87
Frédéric Meunier and Pauline Sarrabezolles, Colorful linear programming, Nash equilibrium, and pivots, Discrete Appl. Math. 240 (2018), 78–91. MR 3775040, DOI 10.1016/j.dam.2016.10.006
F. Meunier and S. Zerbib Envy-free divisions of a partially burnt cake, arXiv:1804.00449 (2018).
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.
Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, Toni Sellarès, Diane Souvaine, Ileana Streinu, and Anja Struyf, Fast implementation of depth contours using topological sweep, Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001) SIAM, Philadelphia, PA, 2001, pp. 690–699. MR 1958543
Maryam Mirzakhani and Jan Vondrák, Sperner’s colorings, hypergraph labeling problems and fair division, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2015, pp. 873–886. MR 3451084, DOI 10.1137/1.9781611973730.60
Maryam Mirzakhani and Jan Vondrák, Sperner’s colorings and optimal partitioning of the simplex, A journey through discrete mathematics, Springer, Cham, 2017, pp. 615–631. MR 3726616
Ivan Mizera, On depth and deep points: a calculus, Ann. Statist. 30 (2002), no. 6, 1681–1736. MR 1969447, DOI 10.1214/aos/1043351254
T. S. Motzkin, H. Raiffa, G. L. Thompson, and R. M. Thrall, The double description method, Contributions to the theory of games, vol. 2, Annals of Mathematics Studies, no. 28, Princeton University Press, Princeton, N.J., 1953, pp. 51–73. MR 0060202
Wolfgang Mulzer and Yannik Stein, Algorithms for tolerated Tverberg partitions, Algorithms and computation, Lecture Notes in Comput. Sci., vol. 8283, Springer, Heidelberg, 2013, pp. 295–305. MR 3161009, DOI 10.1007/978-3-642-45030-3_{2}8
Wolfgang Mulzer and Yannik Stein, Computational aspects of the colorful Carathéodory theorem, 31st International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform., vol. 34, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2015, pp. 44–58. MR 3392769
Wolfgang Mulzer and Daniel Werner, Approximating Tverberg points in linear time for any fixed dimension, Discrete Comput. Geom. 50 (2013), no. 2, 520–535. MR 3090531, DOI 10.1007/s00454-013-9528-7
James R. Munkres, Elements of algebraic topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. MR 755006
Oleg R. Musin, Extensions of Sperner and Tucker’s lemma for manifolds, J. Combin. Theory Ser. A 132 (2015), 172–187. MR 3311342, DOI 10.1016/j.jcta.2014.12.001
Oleg R. Musin, Homotopy invariants of covers and KKM-type lemmas, Algebr. Geom. Topol. 16 (2016), no. 3, 1799–1812. MR 3523055, DOI 10.2140/agt.2016.16.1799
Oleg R. Musin, KKM type theorems with boundary conditions, J. Fixed Point Theory Appl. 19 (2017), no. 3, 2037–2049. MR 3692438, DOI 10.1007/s11784-016-0388-7
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.
Nabil H. Mustafa and Saurabh Ray, Weak $\epsilon$-nets have basis of size $O(1/\epsilon \log (1/\epsilon ))$ in any dimension, Comput. Geom. 40 (2008), no. 1, 84–91. MR 2392655, DOI 10.1016/j.comgeo.2007.02.006
Nabil H. Mustafa and Saurabh Ray, An optimal extension of the centerpoint theorem, Comput. Geom. 42 (2009), no. 6-7, 505–510. MR 2519371, DOI 10.1016/j.comgeo.2007.10.004
Nabil H. Mustafa and Saurabh Ray, An optimal generalization of the colorful Carathéodory theorem, Discrete Math. 339 (2016), no. 4, 1300–1305. MR 3442538, DOI 10.1016/j.disc.2015.11.019
Nabil H. Mustafa, Saurabh Ray, and Mudassir Shabbir, Ray-shooting depth: computing statistical data depth of point sets in the plane, Algorithms—ESA 2011, Lecture Notes in Comput. Sci., vol. 6942, Springer, Heidelberg, 2011, pp. 506–517. MR 2893227, DOI 10.1007/978-3-642-23719-5_{4}3
Nabil H. Mustafa, Saurabh Ray, and Mudassir Shabbir, $k$-centerpoints conjectures for pointsets in $\Bbb {R}^d$, Internat. J. Comput. Geom. Appl. 25 (2015), no. 3, 163–185. MR 3411828, DOI 10.1142/S0218195915500107
Nabil H. Mustafa, Hans Raj Tiwary, and Daniel Werner, A proof of the Oja depth conjecture in the plane, Comput. Geom. 47 (2014), no. 6, 668–674. MR 3168976, DOI 10.1016/j.comgeo.2013.12.006
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óth, Eds.), CRC Press LLC, 2017.
John F. Nash Jr., Equilibrium points in $n$-person games, Proc. Nat. Acad. Sci. U.S.A. 36 (1950), 48–49. MR 31701, DOI 10.1073/pnas.36.1.48
John Nash, Non-cooperative games, Ann. of Math. (2) 54 (1951), 286–295. MR 43432, DOI 10.2307/1969529
J. F. Nash, Jr., Some games and machines for playing them, Tech. Rep. D-1164, Rand Corporation, 1952.
Márton Naszódi, Proof of a conjecture of Bárány, Katchalski and Pach, Discrete Comput. Geom. 55 (2016), no. 1, 243–248. MR 3439267, DOI 10.1007/s00454-015-9753-3
N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, Algorithmic Game Theory. Cambridge University Press, New York, NY, 2007.
A. Novikoff, On convergence proofs for perceptrons, Proc. Sympos. Math. Theory of Automata (New York, 1962) Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y., 1963, pp. 615–622. MR 0175722
Kathryn L. Nyman and Francis Edward Su, A Borsuk-Ulam equivalent that directly implies Sperner’s lemma, Amer. Math. Monthly 120 (2013), no. 4, 346–354. MR 3035127, DOI 10.4169/amer.math.monthly.120.04.346
Hannu Oja, Descriptive statistics for multivariate distributions, Statist. Probab. Lett. 1 (1983), no. 6, 327–332. MR 721446, DOI 10.1016/0167-7152(83)90054-8
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
Shmuel Onn, Nonlinear discrete optimization, Zurich Lectures in Advanced Mathematics, European Mathematical Society (EMS), Zürich, 2010. An algorithmic theory. MR 2724387, DOI 10.4171/093
M. Özaydin, Equivariant maps for the symmetric group (unpublished preprint), University of Winsconsin-Madison, 17 pages, available at http://digital.library.wisc.edu/1793/63829, 1987.
János Pach and Pankaj K. Agarwal, Combinatorial geometry, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1995. A Wiley-Interscience Publication. MR 1354145, DOI 10.1002/9781118033203
D. Pálvölgyi, $2d$-Tucker is PPAD-complete, International Workshop on Internet and Network Economics (2009), Springer, pp. 569–574.
Dömötör Pálvölgyi, Combinatorial necklace splitting, Electron. J. Combin. 16 (2009), no. 1, Research Paper 79, 8. MR 2529788
Christos H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, J. Comput. System Sci. 48 (1994), no. 3, 498–532. 31st Annual Symposium on Foundations of Computer Science (FOCS) (St. Louis, MO, 1990). MR 1279412, DOI 10.1016/S0022-0000(05)80063-7
Rom Pinchasi, A note on smaller fractional Helly numbers, Discrete Comput. Geom. 54 (2015), no. 3, 663–668. MR 3392971, DOI 10.1007/s00454-015-9712-z
G. Pisier, Remarques sur un résultat non publié de B. Maurey, Seminar on Functional Analysis, 1980–1981, École Polytech., Palaiseau, 1981, pp. Exp. No. V, 13 (French). MR 659306
A. Por, Universality of vector sequences and universality of Tverberg partitions, arXiv:1805.07197 (2018).
Timothy Prescott and Francis Edward Su, A constructive proof of Ky Fan’s generalization of Tucker’s lemma, J. Combin. Theory Ser. A 111 (2005), no. 2, 257–265. MR 2156212, DOI 10.1016/j.jcta.2004.12.005
Maurice Queyranne and Fabio Tardella, Carathéodory, Helly, and Radon numbers for sublattice and related convexities, Math. Oper. Res. 42 (2017), no. 2, 495–516. MR 3652003, DOI 10.1287/moor.2016.0815
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
John R. Reay, Generalizations of a theorem of Carathéodory, Mem. Amer. Math. Soc. 54 (1965), 50. MR 188891
Moses Richardson, Solutions of irreflexive relations, Ann. of Math. (2) 58 (1953), 573–590; errata 60 (1954), 595. MR 75184, DOI 10.2307/1969755
Jack Robertson and William Webb, Cake-cutting algorithms, A K Peters, Ltd., Natick, MA, 1998. Be fair if you can. MR 1643406
D. Rolnick and P. Soberón, Algorithmic aspects of Tverberg’s theorem, arXiv:1601.03083 (2016).
David Rolnick and Pablo Soberón, Quantitative $(p,q)$ theorems in combinatorial geometry, Discrete Math. 340 (2017), no. 10, 2516–2527. MR 3674153, DOI 10.1016/j.disc.2017.06.017
T. Ronkainen, H. Oja, and P. Orponen, Computation of the multivariate Oja median, Developments in robust statistics (Vorau, 2001) Physica, Heidelberg, 2003, pp. 344–359. MR 1977491
Jörg Rothe (ed.), Economics and computation, Springer Texts in Business and Economics, Springer, Heidelberg, 2016. An introduction to algorithmic game theory, computational social choice, and fair division; With illustrations by Irene Rothe. MR 3381851, DOI 10.1007/978-3-662-47904-9
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
P. Rousseeuw and I. Ruts, Algorithm AS 307: Bivariate location depth, J. R. Stat. Soc. Ser. C. Appl. Stat. 45 (1996), 516–526.
Peter J. Rousseeuw and Mia Hubert, Regression depth, J. Amer. Statist. Assoc. 94 (1999), no. 446, 388–433. With discussion and a reply by the authors and Stefan Van Aelst. MR 1702314, DOI 10.2307/2670155
N. Rubin, An improved bound for weak epsilon-nets in the plane, Proceedings IEEE Symposium on Foundations of Computer Science (FOCS) 2018.
H. J. Ryser, Neuere Probleme der Kombinatorik, Vorträge über Kombinatorik (July 1967), Oberwolfach, Mathematisches Forschunginstitute.
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
K. S. Sarkaria, Tverberg partitions and Borsuk-Ulam theorems, Pacific J. Math. 196 (2000), no. 1, 231–241. MR 1797243, DOI 10.2140/pjm.2000.196.231
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
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.
Herbert Scarf, The approximation of fixed points of a continuous mapping, SIAM J. Appl. Math. 15 (1967), 1328–1343. MR 242483, DOI 10.1137/0115116
Herbert E. Scarf, The core of an $N$ person game, Econometrica 35 (1967), 50–69. MR 234735, DOI 10.2307/1909383
Herbert E. Scarf, An observation on the structure of production sets with indivisibilities, Proc. Nat. Acad. Sci. U.S.A. 74 (1977), no. 9, 3637–3641. MR 452678, DOI 10.1073/pnas.74.9.3637
Marcus Schaefer and Daniel Štefankovič, Fixed points, Nash equilibria, and the existential theory of the reals, Theory Comput. Syst. 60 (2017), no. 2, 172–193. MR 3600379, DOI 10.1007/s00224-015-9662-0
Torsten Schöneborn and Günter M. Ziegler, The topological Tverberg theorem and winding numbers, J. Combin. Theory Ser. A 112 (2005), no. 1, 82–104. MR 2167476, DOI 10.1016/j.jcta.2005.01.005
A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuw Arch. Wisk. (3) 26 (1978), no. 3, 454–461. MR 512648
Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114
A. Schrijver, Combinatorial Optimization: polyhedra and efficiency, Springer, 2003.
Tyler Seacrest and Francis Edward Su, A lower bound technique for triangulations of simplotopes, SIAM J. Discrete Math. 32 (2018), no. 1, 1–28. MR 3740317, DOI 10.1137/140972020
A. Sebő, Hilbert bases, Carathéodory’s theorem and combinatorial optimization, Integer programming and combinatorial optimization (Waterloo, 1990), Univ. of Waterloo Press, 1990, pp. 431–455.
E. Segal-Halevi, Fairly dividing a cake after some parts were burnt in the oven, arXiv:1704.00726 (2017).
Raimund Seidel, Small-dimensional linear programming and convex hulls made easy, Discrete Comput. Geom. 6 (1991), no. 5, 423–434. MR 1115100, DOI 10.1007/BF02574699
P. D. Seymour, Decomposition of regular matroids, J. Combin. Theory Ser. B 28 (1980), no. 3, 305–359. MR 579077, DOI 10.1016/0095-8956(80)90075-1
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczyński, Lectures on stochastic programming, 2nd ed., MOS-SIAM Series on Optimization, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2014. Modeling and theory. MR 3242164
C. L. Siegel, Über einige Anwendungen diophantischer Approximationen, Abh. der Preus. Akad. der Wissenschaften. Phys.–math., 1 (1929), 209–266.
Forest W. Simmons and Francis Edward Su, Consensus-halving via theorems of Borsuk-Ulam and Tucker, Math. Social Sci. 45 (2003), no. 1, 15–25. MR 1963117, DOI 10.1016/S0165-4896(02)00087-2
Steven Simon, Hyperplane equipartitions plus constraints, J. Combin. Theory Ser. A 161 (2019), 29–50. MR 3861769, DOI 10.1016/j.jcta.2018.07.012
Steve Smale, Mathematical problems for the next century, Math. Intelligencer 20 (1998), no. 2, 7–15. MR 1631413, DOI 10.1007/BF03025291
Pablo Soberón, Gerrymandering, sandwiches, and topology, Notices Amer. Math. Soc. 64 (2017), no. 9, 1010–1013. MR 3699775, DOI 10.1090/noti1582
Pablo Soberón, Robust Tverberg and colourful Carathéodory results via random choice, Combin. Probab. Comput. 27 (2018), no. 3, 427–440. MR 3788169, DOI 10.1017/S0963548317000591
Pablo Soberón and Ricardo Strausz, A generalisation of Tverberg’s theorem, Discrete Comput. Geom. 47 (2012), no. 3, 455–460. MR 2891241, DOI 10.1007/s00454-011-9379-z
Gwen Spencer and Francis Edward Su, The LSB theorem implies the KKM lemma, Amer. Math. Monthly 114 (2007), no. 2, 156–159. MR 2290367, DOI 10.1080/00029890.2007.11920401
Saul Stahl, $n$-tuple colorings and associated graphs, J. Combinatorial Theory Ser. B 20 (1976), no. 2, 185–203. MR 406850, DOI 10.1016/0095-8956(76)90010-1
M. Stehlik, Personal communication.
S. K. Stein, Transversals of Latin squares and their generalizations, Pacific J. Math. 59 (1975), no. 2, 567–575. MR 387083
H. Steinhaus, Sur la division pragmatique, Econometrica 17 (1949), no. (Sup, (Supplement), 315–319 (French). MR 39231, DOI 10.2307/1907319
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
A. H. Stone and J. W. Tukey, Generalized “sandwich” theorems, Duke Math. J. 9 (1942), 356–359. MR 7036
Walter Stromquist, How to cut a cake fairly, Amer. Math. Monthly 87 (1980), no. 8, 640–644. MR 600922, DOI 10.2307/2320951
Walter Stromquist, Envy-free cake divisions cannot be found by finite protocols, Electron. J. Combin. 15 (2008), no. 1, Research Paper 11, 10. MR 2368916
Francis Edward Su, Rental harmony: Sperner’s lemma in fair division, Amer. Math. Monthly 106 (1999), no. 10, 930–942. MR 1732499, DOI 10.2307/2589747
F. Su, A rectangular Sperner’s lemma implies the Hex theorem, Working manuscript (2018).
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.
Endre Szemerédi and William T. Trotter Jr., Extremal problems in discrete geometry, Combinatorica 3 (1983), no. 3-4, 381–392. MR 729791, DOI 10.1007/BF02579194
Martin Tancer, Intersection patterns of convex sets via simplicial complexes: a survey, Thirty essays on geometric graph theory, Springer, New York, 2013, pp. 521–540. MR 3205172, DOI 10.1007/978-1-4614-0110-0_{2}8
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.
Michael J. Todd and Levent Tunçel, A new triangulation for simplicial algorithms, SIAM J. Discrete Math. 6 (1993), no. 1, 167–180. MR 1201998, DOI 10.1137/0406013
John W. Tukey, Mathematics and the picturing of data, Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974) Canad. Math. Congress, Montreal, Que., 1975, pp. 523–531. MR 0426989
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
H. Tverberg, A generalization of Radon’s theorem. II, Bull. Austral. Math. Soc. 24 (1981), no. 3, 321–325. MR 647358, DOI 10.1017/S0004972700004858
Helge Tverberg and Siniša Vrećica, On generalizations of Radon’s theorem and the ham sandwich theorem, European J. Combin. 14 (1993), no. 3, 259–264. MR 1215336, DOI 10.1006/eujc.1993.1029
Jeffrey D. Vaaler, The best constant in Siegel’s lemma, Monatsh. Math. 140 (2003), no. 1, 71–89. MR 2007141, DOI 10.1007/s00605-003-0047-0
M. L. J. van de Vel, Theory of convex structures, North-Holland Mathematical Library, vol. 50, North-Holland Publishing Co., Amsterdam, 1993. MR 1234493
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
Marc van Kreveld, Joseph S. B. Mitchell, Peter Rousseeuw, Micha Sharir, Jack Snoeyink, and Bettina Speckmann, Efficient algorithms for maximum regression depth, Discrete Comput. Geom. 39 (2008), no. 4, 656–677. MR 2413152, DOI 10.1007/s00454-007-9046-6
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
Kasturi Varadarajan, Weighted geometric set cover via quasi-uniform sampling, STOC’10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, New York, 2010, pp. 641–647. MR 2743313
Vijay V. Vazirani, Approximation algorithms, Springer-Verlag, Berlin, 2001. MR 1851303
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
John von Neumann and Oskar Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princeton, N.J., 1944. MR 0011937
Aleksandar Vučić and Rade T. Živaljević, Note on a conjecture of Sierksma, Discrete Comput. Geom. 9 (1993), no. 4, 339–349. MR 1206796, DOI 10.1007/BF02189327
U. Wagner, On $k$-Sets and Applications, PhD thesis, ETH Zurich, 2003.
Matthias Walter and Klaus Truemper, Implementation of a unimodularity test, Math. Program. Comput. 5 (2013), no. 1, 57–73. MR 3030932, DOI 10.1007/s12532-012-0048-x
David P. Williamson and David B. Shmoys, The design of approximation algorithms, Cambridge University Press, Cambridge, 2011. MR 2798112, DOI 10.1017/CBO9780511921735
D. R. Woodall, Dividing a cake fairly, J. Math. Anal. Appl. 78 (1980), no. 1, 233–247. MR 595779, DOI 10.1016/0022-247X(80)90225-5
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.
Xuding Zhu, Recent developments in circular colouring of graphs, Topics in discrete mathematics, Algorithms Combin., vol. 26, Springer, Berlin, 2006, pp. 497–550. MR 2249284, DOI 10.1007/3-540-33700-8_{2}5
Günter M. Ziegler, Generalized Kneser coloring theorems with combinatorial proofs, Invent. Math. 147 (2002), no. 3, 671–691. MR 1893009, DOI 10.1007/s002220100188
Günter M. Ziegler, 3N colored points in a plane, Notices Amer. Math. Soc. 58 (2011), no. 4, 550–557. MR 2807521
R. T. Živaljević Oriented matroids and Ky Fan’s theorem, Combinatorica 30, 4 (2010), 471–484.
Rade T. Živaljević, Topological methods, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 209–224. MR 1730167
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