J. Matoušek

activity

19982019

most citedLower bounds for weak epsilon-nets and stair-convexity

44 citations · 279 across the 33 of their papers we have counts for

collaborators

Showing math.COShow all

22 papers · 1 filter

math.CO2014

Using Brouwer's fixed point theorem

Anders Björner, Jiří Matoušek, Günter M. Ziegler

Brouwer's fixed point theorem from 1911 is a basic result in topology - with a wealth of combinatorial and geometric consequences. In these lecture notes we present some of them, r…

math.CO2014

Factorization Norms and Hereditary Discrepancy

Jiri Matousek, Aleksandar Nikolov, Kunal Talwar

The $γ_{2}$ norm of a real $m \times n$ matrix $A$ is the minimum number $t$ such that the column vectors of $A$ are contained in a $0$ -centered ellipsoid $E \subseteq R^{m}$ whi…

math.CO2013★ 2 cited

Lower bounds on geometric Ramsey functions

Marek Eliáš, Jiří Matoušek, Edgardo Roldán-Pensado +1

We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in $R^{d}$ . A $k$ -ary semialgebraic predicate $Φ (x_{1}, \dots, x_{k})$ on $\mathbb{R…

math.CO2013

Near-optimal separators in string graphs

Jiri Matousek

Let G be a string graph (an intersection graph of continuous arcs in the plane) with m edges. Fox and Pach proved that G has a separator consisting of O(m^{3/4}\sqrt{log m})$ verti…

math.CO2013★ 7 cited

Untangling two systems of noncrossing curves

Jiří Matoušek, Eric Sedgwick, Martin Tancer +1

We consider two systems of curves $(α_{1}, ..., α_{m})$ and $(β_{1}, ..., β_{n})$ drawn on a compact two-dimensional surface $M$ with boundary. Each $α_{i}$ and each $β_{j}$ is either an arc meeti…

math.CO2012

Simplifying inclusion-exclusion formulas

Xavier Goaoc, Jiří Matoušek, Pavel Paták +2

Let $F = {F_{1}, F_{2}, \dots, F_{n}}$ be a family of $n$ sets on a ground set $S$ , such as a family of balls in $R^{d}$ . For every finite measure $μ$ on $S$ , such that t…