P. Paták

activity

20122019

most citedBounds for Pach's selection theorem and for the minimum solid angle in a simplex

7 citations · 9 across the 5 of their papers we have counts for

collaborators

8 papers

math.AT2019

Embeddings of $k$ -complexes into $2 k$ -manifolds

Pavel Paták, Martin Tancer

We improve the bound on Kühnel's problem to determine the smallest $n$ such that the $k$ -skeleton of an $n$ -simplex $Δ_{n}^{(k)}$ does not embed into a compact PL $2 k$ -manifold $M$ b…

math.CO2017

Shellability is NP-complete

Xavier Goaoc, Pavel Paták, Zuzana Patáková +2

We prove that for every $d \geq 2$ , deciding if a pure, $d$ -dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Dan…

math.CO2016

On Generalized Heawood Inequalities for Manifolds: a van Kampen--Flores-type Nonembeddability Result

Xavier Goaoc, and Isaac Mabillard, Pavel Paták +3

The fact that the complete graph $K_{5}$ does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood proble…

cs.CG2016★ 1 cited

A Direct Proof of the Strong Hanani-Tutte Theorem on the Projective Plane

Éric Colin de Verdière, Vojtěch Kaluža, Pavel Paták +2

We reprove the strong Hanani-Tutte theorem on the projective plane. In contrast to the previous proof by Pelsmajer, Schaefer and Stasi, our method is constructive and does not rely…

cs.CG2014★ 1 cited

Three-monotone interpolation

Josef Cibulka, Jiří Matoušek, Pavel Paták

A function $f : R \to R$ is called \emph{ $k$ -monotone} if it is $(k - 2)$ -times differentiable and its $(k - 2)$ nd derivative is convex. A point set $P\subset\mathbb R…

math.MG2014★ 7 cited

Bounds for Pach's selection theorem and for the minimum solid angle in a simplex

Roman Karasev, Jan Kynčl, Pavel Paták +2

We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer $d$ there is a constant $c_{d} > 0$ such that whenever $X_1,..., X…

math.CO2013

Bounding Helly numbers via Betti numbers

Xavier Goaoc, Pavel Paták, Zuzana Patáková +2

We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers $b$ and $d$ th…

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…