A Journey Through Discrete Mathematics: A Tribute to Jir� Matousek

by Martin Loebl (Editor), Jaroslav Nesetril (Editor), Robin Thomas (Editor)

Overview

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.

Product Details

ISBN-13:	9783319444789
Publisher:	Springer International Publishing
Publication date:	10/11/2017
Edition description:	1st ed. 2017
Pages:	810
Product dimensions:	6.10(w) x 9.25(h) x (d)

About the Author

Jiří Matoušek studied at Charles University in Prague, where he also took his doctorate and worked since 1986 till his early decease. He was a full professor at Charles University since 2000. Since 2012 he was also a full professor at ETH Zurich.

He was internationally very active, visited many institutions and delivered distinguished lectures, for example, at the European Congress of Mathematicians in 1996 and at the International Congress of Mathematicians in 1998. He was awarded the Prize of EMS for young researchers in 1996 and the Prize of the Czech Learned Society in 2000.

Jiří Matoušek was a brilliant and outstanding mathematician and computer scientist. Although his research focused on combinatorics, discrete geometry and algorithmics, his interests ranged well beyond these areas. He was a recognised expert in fields including algorithmic geometry, topological methods, discrepancy theory and linear programming.

Jiří Matoušek passed away on March 9, 2015.

Table of Contents

Simplex Range Searching and Its Variants: A Review: Pankaj K. Agarwal.- Fair Representation by Independent Sets: Ron Aharoni, Noga Alon, Eli Berger, Maria Chudnovsky, Dani Kotlar, Martin Loebl, and Ran Ziv.- Computing Heegaard Genus Is NP-Hard: David Bachman, Ryan Derby-Talbot, and Eric Sedgwick.- Approximation-Friendly Discrepancy Rounding: Nikhil Bansal and Viswanath Nagarajan.- A Tverberg Type Theorem for Matroids: Imre Barany, Gil Kalai, Roy Meshulam.- Gershgorin Disks for Multiple Eigenvalues of Non-Negative Matrices: Imre Bárány and József Solymosi.- Computing the Partition Function of a Polynomial on the Boolean Cube: Alexander Barvinok.- Siegel's Lemma Is Sharp: József Beck.- On Codimension One Embedding of Simplicial Complexes: Anders Björner and Afshin Goodarzi.- Around Brouwer's Fixed Point Theorem: Anders Björner, Jiri Matousek, and Günter M. Ziegler.- Beyond the Borsuk-Ulam Theorem: The Topological Tverberg Story: Pavle V. M. Blagojevic and Günter M. Ziegler.- One-Sided Epsilon-Approximants: Boris Bukh and Gabriel Nivasch.- A Note on Induced Ramsey Numbers: David Conlon, Domingos Dellamonica Jr., Steven La Fleur, Vojtech Rödl, and Mathias Schacht.- ARRIVAL: A Zero-Player Graph Game in NP \ coNP: Jerome Dohrau, Bernd Gärtner, Manuel Kohler, Jiri Matousek, and Emo Welzl.- Constant-Factor Approximation for TSP with Disks: Adrian Dumitrescu, and Csaba D. Toth.- Transport-Entropy Inequalities and Curvature in Discrete-State Markov Chains: Ronen Eldan, James R. Lee, and Joseph Lehec.- Bounding Helly Numbers Via Betti Numbers: Xavier Goaoc, Pavel Patak, Zuzana Patakova, Martin Tancer, and Uli Wagner.- Ruled Surface Theory and Incidence Geometry: Larry Guth.- Approximating the k-Level in Three-Dimensional Plane Arrangements: Sariel Har-Peled, Haim Kaplan, and Micha Sharir.- Schrijver Graphs and Projective Quadrangulations: Tomas Kaiser and Matej Stehlik.- Near-Optimal Lower Bounds for nets for Halfspaces and Low Complexity Set Systems: Andrey Kupavskii, Nabil H. Mustafa, and Janos Pach.- Random Simplicial Complexes - Around the Phase Transition: Nathan Linial and Yuval Peled.- Nullspace Embeddings for Outerplanar Graphs: Laszlo Lovasz and Alexander Schrijver.- Homology of Spaces of Directed Paths in Euclidean Pattern Spaces: Roy Meshulam and Martin Raussen.- Sperner's Colorings and Optimal Partitioning of the Simplex: Maryam Mirzakhani and Jan Vondrak.- Teaching and Compressing for Low VC-Dimension: Shay Moran, Amir Shpilka, Avi Wigderson, and Amir Yehudayo.- Restricted Invertibility Revisited: Assaf Naor and Pierre Youssef.- Rational Polygons: Odd Compression Ratio and Odd Plane Coverings: Rom Pinchasi and Yuri Rabinovich.- First Order Probabilities for Galton{Watson Trees: Moumanti Podder and Joel Spencer.- Crossing-Free Perfect Matchings in Wheel Point Sets: Andres J. Ruiz-Vargas and Emo Welzl.- Network Essence: Page Rank Completion and Centrality-Conforming Markov Chains: Shang-Hua Teng.- Anti-Concentration Inequalities for Polynomials: Van Vu.