Source author record

Zuzana Patáková

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Geometry math.MG Discrete Mathematics math.AT math.PR

Catalog footprint

Research overview

6works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Barycentric cuts through a convex body

Let $K$ be a convex body in $\mathbb{R}^n$ (i.e., a compact convex set with nonempty interior). Given a point $p$ in the interior of $K$ , a hyperplane $h$ passing through $p$ is called barycentric if $p$ is the barycenter of $K \cap h$ . In 1961, Grünbaum raised the question whether, for every $K$ , there exists an interior point $p$ through which there are at least $n+1$ distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if $p=p_0$ is the point of maximal depth in $K$ . However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum's question. It follows from known results that for $n \geq 2$ , there are always at least three distinct barycentric cuts through the point $p_0 \in K$ of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through $p_0$ are guaranteed if $n \geq 3$ .

preprint2016arXiv

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

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 on the characterization of forbidden minors, which gives hope to extend it to other surfaces. Moreover, our approach can be used to provide an efficient algorithm turning a Hanani-Tutte drawing on the projective plane into an embedding.

preprint2016arXiv

Bounding Helly numbers via Betti numbers

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$ there exists an integer $h(b,d)$ such that the following holds. If $\mathcal F$ is a finite family of subsets of $\mathbb R^d$ such that $\tildeβ_i\left(\bigcap\mathcal G\right) \le b$ for any $\mathcal G \subsetneq \mathcal F$ and every $0 \le i \le \lceil d/2 \rceil-1$ then $\mathcal F$ has Helly number at most $h(b,d)$ . Here $\tildeβ_i$ denotes the reduced $\mathbb Z_2$ -Betti numbers (with singular homology). These topological conditions are sharp: not controlling any of these $\lceil d/2 \rceil$ first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex $K$ , some well-behaved chain map $C_*(K) \to C_*(\mathbb R^d)$ .

preprint2016arXiv

Colorful simplicial depth, Minkowski sums, and generalized Gale transforms

The colorful simplicial depth of a collection of d+1 finite sets of points in Euclidean d-space is the number of choices of a point from each set such that the origin is contained in their convex hull. We use methods from combinatorial topology to prove a tight upper bound on the colorful simplicial depth. This implies a conjecture of Deza et al. (2006). Furthermore, we introduce colorful Gale transforms as a bridge between colorful configurations and Minkowski sums. Our colorful upper bound then yields a tight upper bound on the number of totally mixed facets of certain Minkowski sums of simplices. This resolves a conjecture of Burton (2003) in the theory of normal surfaces.

preprint2016arXiv

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

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 problem for graphs on surfaces established that the complete graph $K_n$ embeds in a closed surface $M$ (other than the Klein bottle) if and only if $(n-3)(n-4)\leq 6b_1(M)$ , where $b_1(M)$ is the first $\mathbb Z_2$ -Betti number of $M$ . On the other hand, van Kampen and Flores proved that the $k$ -skeleton of the $n$ -dimensional simplex (the higher-dimensional analogue of $K_{n+1}$ ) embeds in $\mathbb R^{2k}$ if and only if~ $n \le 2k+1$ . Two decades ago, Kühnel conjectured that the $k$ -skeleton of the $n$ -simplex embeds in a compact, $(k-1)$ -connected $2k$ -manifold with $k$ th $\mathbb Z_2$ -Betti number $b_k$ only if the following generalized Heawood inequality holds: $\binom{n-k-1}{k+1} \le \binom{2k+1}{k+1}b_k$ . This is a common generalization of the case of graphs on surfaces as well as the van Kampen--Flores theorem (the special cases $k=1$ and $b_k=0$ , respectively), and also closely related to the theory of face numbers of triangulated manifolds. In the spirit of Kühnel's conjecture, we prove that if the $k$ -skeleton of the $n$ -simplex embeds in a $2k$ -manifold with $k$ th $\mathbb Z_2$ -Betti number $b_k$ , then $n \le 2b_k\binom{2k+2}{k} + 2k + 4$ . This bound is weaker than the generalized Heawood inequality, but does not require the assumption that $M$ is $(k-1)$ -connected. Our results generalize to maps without $q$ -covered points, in the spirit of Tverberg's theorem, for $q$ a prime power. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.

preprint2015arXiv

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

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_{d+1}$ are $n$ -element subsets of $\mathbb{R}^d$ , then we can find a point $\mathbf{p} \in \mathbb{R}^d$ and subsets $Y_i \subseteq X_i$ for every $i \in [d+1]$ , each of size at least $c_d n$ , such that $\mathbf{p}$ belongs to all {\em rainbow} $d$ -simplices determined by $Y_1,..., Y_{d+1}$ , that is, simplices with one vertex in each $Y_i$ . We show a super-exponentially decreasing upper bound $c_d\leq e^{-(1/2-o(1))(d \ln d)}$ . The ideas used in the proof of the upper bound also help us prove Pach's theorem with $c_d \geq 2^{-2^{d^2 + O(d)}}$ , which is a lower bound doubly exponentially decreasing in $d$ (up to some polynomial in the exponent). For comparison, Pach's original approach yields a triply exponentially decreasing lower bound. On the other hand, Fox, Pach, and Suk recently obtained a hypergraph density result implying a proof of Pach's theorem with $c_d \geq2^{-O(d^2\log d)}$ . In our construction for the upper bound, we use the fact that the minimum solid angle of every $d$ -simplex is super-exponentially small. This fact was previously unknown and might be of independent interest. For the lower bound, we improve the "separation" part of the argument by showing that in one of the key steps only $d+1$ separations are necessary, compared to $2^d$ separations in the original proof. We also provide a measure version of Pach's theorem.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Zuzana Patáková

Research overview

Is this your work?

6 publications

Barycentric cuts through a convex body

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

Bounding Helly numbers via Betti numbers

Colorful simplicial depth, Minkowski sums, and generalized Gale transforms

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

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

See the researcher in context

Building this map preview