BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Pavel Paták

Pavel Paták appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COComputational Geometrymath.ATmath.MGDiscrete Mathematicsmath.GT

Catalog footprint

What is connected

8works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

8 published item(s)

preprint2022arXiv

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

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 $2k$-manifold $M$ by showing that if $Δ_n^{(k)}$ embeds into $M$, then $n\leq (2k+1)+(k+1)β_k(M;\mathbb Z_2)$. As a consequence we obtain improved Radon and Helly type results for set systems in such manifolds. Our main tool is a new description of an obstruction for embeddability of a $k$-complex $K$ into a compact PL $2k$-manifold $M$ via the intersection form on $M$. In our approach we need that for every map $f\colon K\to M$ the restriction to the $(k-1)$-skeleton of $K$ is nullhomotopic. In particular, this condition is satisfied in interesting cases if $K$ is $(k-1)$-connected, for example a $k$-skeleton of $n$-simplex, or if $M$ is $(k-1)$-connected. In addition, if $M$ is $(k-1)$-connected and $k\geq 3$, the obstruction is complete, meaning that a $k$-complex $K$ embeds into $M$ if and only if the obstruction vanishes. For trivial intersection forms, our obstruction coincides with the standard van Kampen obstruction. However, if the form is non-trivial, the obstruction is not linear but rather 'quadratic' in a sense that it vanishes if and only if certain system of quadratic diophantine equations is solvable. This may potentially be useful in attacking algorithmic decidability of embeddability of $k$-complexes into PL $2k$-manifolds.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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)$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Simplifying inclusion-exclusion formulas

Let $\mathcal{F}=\{F_1,F_2, \ldots,F_n\}$ be a family of $n$ sets on a ground set $S$, such as a family of balls in $\mathbb{R}^d$. For every finite measure $μ$ on $S$, such that the sets of $\mathcal{F}$ are measurable, the classical inclusion-exclusion formula asserts that $μ(F_1\cup F_2\cup\cdots\cup F_n)=\sum_{I:\emptyset\ne I\subseteq[n]} (-1)^{|I|+1}μ\Bigl(\bigcap_{i\in I} F_i\Bigr)$; that is, the measure of the union is expressed using measures of various intersections. The number of terms in this formula is exponential in $n$, and a significant amount of research, originating in applied areas, has been devoted to constructing simpler formulas for particular families $\mathcal{F}$. We provide an upper bound valid for an arbitrary $\mathcal{F}$: we show that every system $\mathcal{F}$ of $n$ sets with $m$ nonempty fields in the Venn diagram admits an inclusion-exclusion formula with $m^{O(\log^2n)}$ terms and with $\pm1$ coefficients, and that such a formula can be computed in $m^{O(\log^2n)}$ expected time. For every $\varepsilon>0$ we also construct systems with Venn diagram of size $m$ for which every valid inclusion-exclusion formula has the sum of absolute values of the coefficients at least $Ω(m^{2-\varepsilon})$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Three-monotone interpolation

A function $f\colon\mathbb R\to\mathbb 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^2$ is \emph{$k$-monotone interpolable} if it lies on a graph of a $k$-monotone function. These notions have been studied in analysis, approximation theory etc. since the 1940s. We show that 3-monotone interpolability is very non-local: we exhibit an arbitrarily large finite $P$ for which every proper subset is $3$-monotone interpolable but $P$ itself is not. On the other hand, we prove a Ramsey-type result: for every $n$ there exists $N$ such that every $N$-point $P$ with distinct $x$-coordinates contains an $n$-point $Q$ such that $Q$ or its vertical mirror reflection are $3$-monotone interpolable. The analogs for $k$-monotone interpolability with $k=1$ and $k=2$ are classical theorems of Erdős and Szekeres, while the cases with $k\ge4$ remain open. We also investigate the computational complexity of deciding $3$-monotone interpolability of a given point set. Using a known characterization, this decision problem can be stated as an instance of polynomial optimization and reformulated as a semidefinite program. We exhibit an example for which this semidefinite program has only doubly exponentially large feasible solutions, and thus known algorithms cannot solve it in polynomial time. While such phenomena have been well known for semidefinite programming in general, ours seems to be the first such example in polynomial optimization, and it involves only univariate quadratic polynomials.

0 citations0 reviewsNo code linkedOpen access