BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Martin Tancer

Martin Tancer contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.COComputational GeometryDiscrete Mathematicsmath.ATmath.GTmath.PR

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
12works
0followers
6topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

12 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
preprint2021arXiv

Shellings and sheddings induced by collapses

We say that a pure simplicial complex ${\mathbf K}$ of dimension $d$ satisfies the removal-collapsibility condition if ${\mathbf K}$ is either empty or ${\mathbf K}$ becomes collapsible after removing $\tilde β_d ({\mathbf K}; {\mathbb Z}_2)$ facets, where $\tilde β_d ({\mathbf K}; {\mathbb Z}_2)$ denotes the $d$th reduced Betti number. In this paper, we show that if the link of each face of a pure simplicial complex ${\mathbf K}$ (including the link of the empty face which is the whole ${\mathbf K}$) satisfy the removal-collapsibility condition, then the second barycentric subdivision of ${\mathbf K}$ is vertex decomposable and in particular shellable. This is a higher dimensional generalization of a result of Hachimori, who proved that that if the link of each vertex of a pure 2-dimensional simplicial complex ${\mathbf K}$ is connected, and ${\mathbf K}$ becomes simplicially collapsible after removing $\tildeχ({\mathbf K})$ facets, where $\tilde χ({\mathbf K})$ denotes the reduced Euler characteristic, then the second barycentric subdivision of ${\mathbf K}$ is shellable. For the proof, we introduce a new variant of decomposability of a simplicial complex, stronger than vertex decomposability, which we call star decomposability. This notion may be of independent interest.

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

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Even maps, the Colin de~Verdière number and representations of graphs

Van der Holst and Pendavingh introduced a graph parameter $σ$, which coincides with the more famous Colin de Verdière graph parameter $μ$ for small values. However, the definition of $σ$ is much more geometric/topological directly reflecting embeddability properties of the graph. They proved $μ(G) \leq σ(G) + 2$ and conjectured $μ(G) \leq σ(G)$ for any graph $G$. We confirm this conjecture. As far as we know, this is the first topological upper bound on $μ(G)$ which is, in general, tight. Equality between $μ$ and $σ$ does not hold in general as van der Holst and Pendavingh showed that there is a graph $G$ with $μ(G) \leq 18$ and $σ(G)\geq 20$. We show that the gap appears on much smaller values, namely, we exhibit a graph $H$ for which $μ(H)\leq 7$ and $σ(H)\geq 8$. We also prove that, in general, the gap can be large: The incidence graphs $H_q$ of finite projective planes of order $q$ satisfy $μ(H_q) \in O(q^{3/2})$ and $σ(H_q) \geq q^2$.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

On Betti numbers of flag complexes with forbidden induced subgraphs

We analyze the asymptotic extremal growth rate of the Betti numbers of clique complexes of graphs on n vertices not containing a fixed forbidden induced subgraph H. In particular, we prove a theorem of the alternative: for any H the growth rate achieves exactly one of five possible exponentials, that is, independent of the field of coefficients, the nth root of the maximal total Betti number over n-vertex graphs with no induced copy of H has a limit, as n tends to infinity, and, ranging over all H, exactly five different limits are attained. For the interesting case where H is the 4-cycle, the above limit is 1, and we prove a slightly superpolynomial upper bound.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Non-embeddability of geometric lattices and buildings

A fundamental question for simplicial complexes is to find the lowest dimensional Euclidean space in which they can be embedded. We investigate this question for order complexes of posets. We show that order complexes of thick geometric lattices as well as several classes of finite buildings, all of which are order complexes, are hard to embed. That means that such d-dimensional complexes require (2d + 1)-dimensional Euclidean space for an embedding. (This dimension is in general always sufficient for any d-complex.) We develop a method to show non-embeddability for general order complexes of posets which builds on properties of the van Kampen obstruction.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A geometric proof of the colored Tverberg theorem

The colored Tverberg theorem asserts that for every d and r there exists t=t(d,r) such that for every set C in R^d of cardinality (d+1)t, partitioned into t-point subsets C_1,C_2,...,C_{d+1} (which we think of as color classes; e.g., the points of C_1 are red, the points of C_2 blue, etc.), there exist r disjoint sets R_1,R_2,...,R_r \subseteq C that are &#34;rainbow&#34;, meaning that |R_i \cap C_j| < 2 for every i,j, and whose convex hulls all have a common point. All known proofs of this theorem are topological. We present a geometric version of a recent beautiful proof by Blagojević, Matschke, and Ziegler, avoiding a direct use of topological methods. The purpose of this de-topologization is to make the proof more concrete and intuitive, and accessible to a wider audience.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

d-Representability of simplicial complexes of fixed dimension

Let K be a simplicial complex with vertex set V = {v_1,..., v_n}. The complex K is d-representable if there is a collection {C_1,...,C_n} of convex sets in R^d such that a subcollection {C_{i_1},...,C_{i_j}} has a nonempty intersection if and only if {v_{i_1},...,v_{i_j}} is a face of K. In 1967 Wegner proved that every simplicial complex of dimension d is (2d+1)-representable. He also suggested that his bound is the best possible, i.e., that there are $d$-dimensional simplicial complexes which are not 2d-representable. However, he was not able to prove his suggestion. We prove that his suggestion was indeed right. Thus we add another piece to the puzzle of intersection patterns of convex sets in Euclidean space.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Intersection patterns of convex sets via simplicial complexes, a survey

The task of this survey is to present various results on intersection patterns of convex sets. One of main tools for studying intersection patterns is a point of view via simplicial complexes. We recall the definitions of so called $d$-representable, $d$-collapsible and $d$-Leray simplicial complexes which are very useful for this study. We study the differences among these notions and we also focus on computational complexity for recognizing them. A list of Helly-type theorems is presented in the survey and it is also discussed how (important) role play the above mentioned notions for the theorems. We also consider intersection patterns of good covers which generalize collections of convex sets (the sets may be `curvy&#39;; however, their intersections cannot be too complicated). We mainly focus on new results.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Complexity of Planar Covering of Small Graphs

The problem Cover(H) asks whether an input graph G covers a fixed graph H (i.e., whether there exists a homomorphism G to H which locally preserves the structure of the graphs). Complexity of this problem has been intensively studied. In this paper, we consider the problem PlanarCover(H) which restricts the input graph G to be planar. PlanarCover(H) is polynomially solvable if Cover(H) belongs to P, and it is even trivially solvable if H has no planar cover. Thus the interesting cases are when H admits a planar cover, but Cover(H) is NP-complete. This also relates the problem to the long-standing Negami Conjecture which aims to describe all graphs having a planar cover. Kratochvil asked whether there are non-trivial graphs for which Cover(H) is NP-complete but PlanarCover(H) belongs to P. We examine the first nontrivial cases of graphs H for which Cover(H) is NP-complete and which admit a planar cover. We prove NP-completeness of PlanarCover(H) in these cases.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A counterexample to Wegner&#39;s conjecture on good covers

In 1975 Wegner conjectured that the nerve of every finite good cover in R^d is d-collapsible. We disprove this conjecture. A good cover is a collection of open sets in R^d such that the intersection of every subcollection is either empty or homeomorphic to an open d-ball. A simplicial complex is d-collapsible if it can be reduced to an empty complex by repeatedly removing a face of dimension at most d-1 which is contained in a unique maximal face.

0 citations0 reviewsNo code linkedOpen access