Martin Tancer

STOC Conference 2023 Conference Paper

Shellability Is Hard Even for Balls

• Pavel Paták
• Martin Tancer

SODA Conference 2020 Conference Paper

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

• Vojtech Kaluza
• Martin Tancer

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 ) ≤ σ ( G ) + 2 and conjectured µ ( G ) ≤ σ ( 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 ) ≤ 18 and σ ( G ) ≥ 20. We show that the gap appears on much smaller values, namely, we exhibit a graph H for which µ ( H ) ≤ 7 and σ ( H ) ≥ 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 ) ϵ O ( q 3/2 ) and σ ( H q ) ≥ q 2.

SODA Conference 2018 Conference Paper

Embeddability in ℝ 3 is NP-hard

• Arnaud de Mesmay
• Yo'av Rieck
• Eric Sedgwick
• Martin Tancer

We prove that the problem of deciding whether a 2- or 3-dimensional simplicial complex embeds into ℝ 3 is NP -hard. This stands in contrast with the lower dimensional cases which can be solved in linear time, and a variety of computational problems in ℝ 3 like unknot or 3-sphere recognition which are in NP ∩ co- NP (assuming the generalized Riemann hypothesis). Our reduction encodes a satisfiability instance into the embeddability problem of a 3-manifold with boundary tori, and relies extensively on techniques from low-dimensional topology, most importantly Dehn fillings on link complements.

SODA Conference 2009 Conference Paper

Hardness of embedding simplicial complexes in R d

• Jirí Matousek 0001
• Martin Tancer
• Uli Wagner 0001