A Journey Through Discrete Mathematics

A Tribute to Jiří Matoušek

Martin Loebl, Jaroslav Nešetřil, Robin Thomas

• Publisher: Springer
• Year: 2017
• Print ISBN:
  9783319444789
• eBook ISBN:
  9783319444796
• Topic: Computer Science
• Subtopic: Management
• Index: Computer Science

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.

Table of contents

• Contents
• Introduction
• Curriculum Vitae of Jiří Matoušek
• List of Publications
• Simplex Range Searching and Its Variants: A Review
• Fair Representation by Independent Sets
• Computing Heegaard Genus is NP-Hard
• Approximation-Friendly Discrepancy Rounding
• A Tverberg Type Theorem for Matroids
• Gershgorin Disks for Multiple Eigenvalues of Non-negative Matrices
• Computing the Partition Function of a Polynomialon the Boolean Cube
• Siegel's Lemma Is Sharp
• On Codimension One Embedding of Simplicial Complexes
• Using Brouwer's Fixed Point Theorem
• Beyond the Borsuk–Ulam Theorem: The Topological Tverberg Story
• One-Sided Epsilon-Approximants
• A Note on Induced Ramsey Numbers
• ARRIVAL: A Zero-Player Graph Game in NPcoNP
• Constant-Factor Approximation for TSP with Disks
• Transport-Entropy Inequalities and Curvature in Discrete-Space Markov Chains
• Bounding Helly Numbers via Betti Numbers
• Ruled Surface Theory and Incidence Geometry
• Approximating the k-Level in Three-Dimensional PlaneArrangements
• Schrijver Graphs and Projective Quadrangulations
• Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems
• Random Simplicial Complexes: Around the Phase Transition
• Nullspace Embeddings for Outerplanar Graphs
• Homology of Spaces of Directed Paths in Euclidean Pattern Spaces
• Sperner's Colorings and Optimal Partitioning of the Simplex
• Teaching and Compressing for Low VC-Dimension
• Restricted Invertibility Revisited
• Rational Polygons: Odd Compression Ratio and Odd Plane Coverings
• First Order Probabilities for Galton–Watson Trees
• Crossing-Free Perfect Matchings in Wheel Point Sets
• Network Essence: PageRank Completion and Centrality-Conforming Markov Chains
• Anti-concentration Inequalities for Polynomials