A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek

Description

This collection of high-quality articles in the field of combinatorics, geometry, algebraic topology and theoretical computer science is a tribute to Jiří Matoušek, who passed away prematurely in March 2015. It is a collaborative effort by his colleagues and friends, who have paid particular attention to clarity of exposition – something Jirka would have approved of. The original research articles, surveys and expository articles, written by leading experts in their respective fields, map Jiří Matoušek’s numerous areas of mathematical interest. Front Matter ....Pages i-xxxiv Simplex Range Searching and Its Variants: A Review (Pankaj K. Agarwal)....Pages 1-30 Fair Representation by Independent Sets (Ron Aharoni, Noga Alon, Eli Berger, Maria Chudnovsky, Dani Kotlar, Martin Loebl et al.)....Pages 31-58 Computing Heegaard Genus is NP-Hard (David Bachman, Ryan Derby-Talbot, Eric Sedgwick)....Pages 59-87 Approximation-Friendly Discrepancy Rounding (Nikhil Bansal, Viswanath Nagarajan)....Pages 89-114 A Tverberg Type Theorem for Matroids (Imre Bárány, Gil Kalai, Roy Meshulam)....Pages 115-121 Gershgorin Disks for Multiple Eigenvalues of Non-negative Matrices (Imre Bárány, József Solymosi)....Pages 123-133 Computing the Partition Function of a Polynomial on the Boolean Cube (Alexander Barvinok)....Pages 135-164 Siegel’s Lemma Is Sharp (József Beck)....Pages 165-206 On Codimension One Embedding of Simplicial Complexes (Anders Björner, Afshin Goodarzi)....Pages 207-219 Using Brouwer’s Fixed Point Theorem (Anders Björner, Jiří Matoušek, Günter M. Ziegler)....Pages 221-271 Beyond the Borsuk–Ulam Theorem: The Topological Tverberg Story (Pavle V. M. Blagojević, Günter M. Ziegler)....Pages 273-341 One-Sided Epsilon-Approximants (Boris Bukh, Gabriel Nivasch)....Pages 343-356 A Note on Induced Ramsey Numbers (David Conlon, Domingos Dellamonica, Steven La Fleur, Vojtěch Rödl, Mathias Schacht)....Pages 357-366 ARRIVAL: A Zero-Player Graph Game in NP ∩ coNP (Jérôme Dohrau, Bernd Gärtner, Manuel Kohler, Jiří Matoušek, Emo Welzl)....Pages 367-374 Constant-Factor Approximation for TSP with Disks (Adrian Dumitrescu, Csaba D. Tóth)....Pages 375-390 Transport-Entropy Inequalities and Curvature in Discrete-Space Markov Chains (Ronen Eldan, James R. Lee, Joseph Lehec)....Pages 391-406 Bounding Helly Numbers via Betti Numbers (Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, Uli Wagner)....Pages 407-447 Ruled Surface Theory and Incidence Geometry (Larry Guth)....Pages 449-466 Approximating the k-Level in Three-Dimensional Plane Arrangements (Sariel Har-Peled, Haim Kaplan, Micha Sharir)....Pages 467-503 Schrijver Graphs and Projective Quadrangulations (Tomáš Kaiser, Matěj Stehlík)....Pages 505-526 Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems (Andrey Kupavskii, Nabil H. Mustafa, János Pach)....Pages 527-541 Random Simplicial Complexes: Around the Phase Transition (Nathan Linial, Yuval Peled)....Pages 543-570 Nullspace Embeddings for Outerplanar Graphs (László Lovász, Alexander Schrijver)....Pages 571-591 Homology of Spaces of Directed Paths in Euclidean Pattern Spaces (Roy Meshulam, Martin Raussen)....Pages 593-614 Sperner’s Colorings and Optimal Partitioning of the Simplex (Maryam Mirzakhani, Jan Vondrák)....Pages 615-631 Teaching and Compressing for Low VC-Dimension (Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff)....Pages 633-656 Restricted Invertibility Revisited (Assaf Naor, Pierre Youssef)....Pages 657-691 Rational Polygons: Odd Compression Ratio and Odd Plane Coverings (Rom Pinchasi, Yuri Rabinovich)....Pages 693-710 First Order Probabilities for Galton–Watson Trees (Moumanti Podder, Joel Spencer)....Pages 711-734 Crossing-Free Perfect Matchings in Wheel Point Sets (Andres J. Ruiz-Vargas, Emo Welzl)....Pages 735-764 Network Essence: PageRank Completion and Centrality-Conforming Markov Chains (Shang-Hua Teng)....Pages 765-799 Anti-concentration Inequalities for Polynomials (Van Vu)....Pages 801-810