Martin Tancer - publications

My research interests:

Geometric and topological combinatorics, computational topology, graph theory

Remark on names of coauthors

In the lists below I spell my coauthors without special characters, since I sometimes experience problems with encoding special characters. The list of my coauthors, including special characters (if they appear correctly) can be found below the list of publications.

Submitted papers and/or preprints (possibly with currently existing conference version)

Z. Patakova, M. Tancer, U. Wagner: Barycentric cuts through a convex body. Preprint at Arxiv. (Accepted to SoCG 2020.)
T. Magnard, M. Skotnica, M. Tancer: Shellings and sheddings induced by collapses. Preprint at Arxiv.
V. Kaluza, M. Tancer: Even maps, the Colin de Verdière number and representations of graphs. Preprint at Arxiv. (Accepted to SODA 2020.)
P. Patak, M. Tancer: Embeddings of k-complexes into 2k-manifolds. Preprint at Arxiv.
A. de Mesmay, Y. Rieck, E. Sedgwick, M. Tancer: The unbearable hardness of unknotting. Preprint at Arxiv. (Appeared at SoCG 2019.)
A. de Mesmay, Y. Rieck, E. Sedgwick, M. Tancer: Embeddability in R^3 is NP-hard. Preprint at Arxiv. (Appeared at SODA 2018.)

Original research papers accepted for publication in refereed international journals (or as a book chapter), newest first

K. Adiprasito, E. Nevo, M. Tancer: On Betti numbers of flag complexes with forbidden induced subgraphs. Preprint at Arxiv. (To appear in Mathematical Proceedings of the Cambridge Philosophical Society.)
V. Jelinek, I. Kantor, J. Kyncl, M. Tancer: On the growth of the Möbius function of permutations. Preprint at Arxiv. Journal of Combinatorial Theory, Series A 169 (2020), art. no. 105121.
X. Goaoc, P. Patak, Z. Patakova, M. Tancer, U. Wagner: Shellability is NP-complete. Preprint at Arxiv. Journal of the ACM 66(3) (2019), art. no. 21.
A. Skopenkov, M. Tancer: Hardness of almost embedding simplicial complexes in R^d. Preprint at Arxiv. Discrete and Computational Geometry 61(2) (2019), 452-463.
I. Barany, R. Meshulam, E. Nevo, M. Tancer: Pach's selection theorem does not admit a topological extension. Preprint at Arxiv. Discrete and Computational Geometry 60(2) (2018), 420-429.
J. Matousek, E. Sedgwick, M. Tancer, U. Wagner: Embeddability in the 3-sphere is decidable. Preprint at Arxiv. Journal of the ACM 65(1) (2018), art. no. 5.
X. Goaoc, I. Mabillard, P. Patak, Z. Patakova, M. Tancer, U. Wagner: On Generalized Heawood Inequalities for Manifolds: A Van Kampen-Flores-type Nonembeddability Result. Israel Journal of Mathematics 222(2) (2017), 841-866. Preprint at Arxiv.
X. Goaoc, P. Patak, Z. Patakova, M. Tancer, U. Wagner: Bounding Helly numbers via Betti numbers. Chapter in A Journey Through Discrete Mathematics, A Tribute to Jiří Matoušek, (2017, online), 407-447. Preprint at Arxiv.
E. Colin de Verdiere, V. Kaluza, P. Patak, Z. Patakova, M. Tancer: A Direct Proof of the Strong Hanani-Tutte Theorem on the Projective Plane. Journal of Graph Algorithms and Applications 21(5) (2017), 939-981. Preprint at Arxiv.
A. Hubard, V. Kaluza, A. de Mesmay, M. Tancer: Shortest Path Embeddings of Graphs on Surfaces. Discrete and Computational Geometry 58(4) (2017), 921-945. Preprint at Arxiv.
J. Matousek, E. Sedgwick, M. Tancer, U. Wagner: Untangling two systems of noncrossing curves. Israel Journal of Mathematics. 212(1) (2016), 37-79. Preprint at Arxiv.
M. Tancer: Recognition of collapsible complexes is NP-complete. Discrete and Computational Geometry. 55(1) (2016), 21-38. Preprint at Arxiv.
R. Karasev, J. Kyncl, P. Patak, Z. Patakova, M. Tancer: Bounds for Pach's selection theorem and for the minimum solid angle in a simplex. Discrete and Computational Geometry. 54(3) (2015), 610-636. Preprint at Arxiv.
X. Goaoc, J. Matousek, P. Patak, Z. Safernova, M. Tancer: Simplifying inclusion-exclusion formulas. Combinatorics, Probability and Computing. 24(2) (2015), 438-456. Preprint at Arxiv.
M. Tancer: Shellability of the higher pinched Veronese posets. Journal of Algebraic Combinatorics. 40(3) (2014), 711-742. Preprint at Arxiv.
M. Tancer, K. Vorwerk: Non-embeddability of geometric lattices and buildings. Discrete and Computational Geometry. 51(4) (2014), 779-801. Preprint at Arxiv.
M. Tancer, D. Tonkonog: Nerves of Good covers are algorithmically unrecognizable. SIAM Journal on Computing. 42(4) (2013), 1697-1719. Preprint at Arxiv.
J. Matousek, M. Tancer, U. Wagner: A geometric proof of the colored Tverberg theorem, Discrete and Computational Geometry. 47(2) (2012), 245-265. Preprint at Arxiv.
M. Tancer: A counterexample to Wegner's conjecture on good covers, Discrete and Computational Geometry. 47(2) (2012), 266-274. Preprint at Arxiv.
M. Tancer: d-representability of simplicial complexes of fixed dimension, Journal of Computational Geometry, 2(1) (2011), 183-188. Link to the journal (open access).
M. Tancer: Strong d-collapsibility, Contributions to Discrete Mathematics, 6(2) (2011), 32-35. Link to the journal (open access).
J. Matousek, M. Tancer, U. Wagner: Hardness of embedding simplicial complexes in R^d, Journal of the European Mathematical Society, 13(2) (2011), 259-295. Preprint at Arxiv.
M. Tancer: d-collapsibility is NP-complete for d greater or equal to 4. Chicago Journal of Theoretical Computer Science, 2010, Preprint at Arxiv.
M. Tancer: Non-representability of finite projective planes by convex sets, Proceedings of the American Mathematical Society 138(9) (2010), 3285-3291. Preprint at Arxiv.
J. Miskuf, R. Skrekovski, M. Tancer: Backbone Colorings of Graphs with Bounded Degree, Discrete Applied Mathematics 158(5) (2010), 534-542. Preprint in ITI series (unfortunately, the preprint contains some errors; use the journal version or email me for the recent version).
A. Bjorner, M. Tancer: Combinatorial Alexander Duality - a Short and Elementary Proof, Discrete and Computational Geometry 42(4) (2009), 586-593. Preprint at Arxiv.
J. Matousek, M. Tancer: Dimension Gaps Between Representability and Collapsibility, Discrete and Computational Geometry 42(4) (2009), 631-639. Preprint at Arxiv.
B. Luzar, R. Skrekovski, M. Tancer: Injective colorings of planar graphs with few colors, Discrete Mathematics 309(18) (2009), 5636-5649. Preprint in ITI series.
J. Miskuf, R. Skrekovski, M. Tancer: Backbone Colorings and Generalized Mycielski's Graphs, SIAM Journal on Discrete Mathematics 23 (2009), 1063-1070. Full version.
Z. Dvorak, R. Skrekovski, M. Tancer: List coloring squares of sparse subcubic graphs, SIAM Journal on Discrete Mathematics 22 (2008), 139-159. Preprint in ITI series.
J. Kyncl, M. Tancer: The maximum piercing number for some classes of convex sets with (4,3)-property, Electron. J. Combin. 15(1) (2008), R27. Link to the journal (open access).
J. Hladky, J. Novak, P. Pyrih, M. Sterzik, M. Tancer: An engine breaking ΩEP-property, Topology and its Applications 153(18) (2006), 3621-3626.
D. Kral, R. Skrekovski, M. Tancer: Construction of large graphs with no optimal surjective L(2,1)-labelings, SIAM Journal on Discrete Mathematics 20(2) (2006), 536-543. Preprint in ITI series.

A paper (at the moment single) in an international fully refereed conference without a journal version

O. Bilka, J. Jirasek, P. Klavik, M. Tancer, J. Volec: On the Complexity of Planar Covering of Small Graphs. In proceedings of WG 2011, Lecture Notes in Computer Science 6986 (2011), 83-94. Full version at Arxiv.

A survey paper (at the moment single)

M. Tancer: Intersection patterns of convex sets via simplicial complexes, a survey. In J. Pach, editor, Thirty Essays on Geometric Graph Theory, Springer New York (2013), 521-540. Preprint at Arxiv.

My PhD thesis

M. Tancer: Topological and geometrical combinatorics, Charles University in Prague. Download.

List of coauthors

Karim Adiprasito, Imre Bárány, Ondřej Bílka, Anders Björner, Éric Colin de Verdière, Zdeněk Dvořák, Xavier Goaoc, Jan Hladký, Alfredo Hubard, Vít Jelínek, Jozef Jirásek, Vojtěch Kaluža, Ida Kantor, Roman Karasev, Pavel Klavík, Daniel Kráľ, Jan Kynčl, Borut Lužar, Thomas Magnard, Jiří Matoušek, Roy Meshulam, Arnaud de Mesmay, Jozef Miškuf, Eran Nevo, Jan Novák, Pavel Paták, Zuzana Patáková (Safernová), Pavel Pyrih, Yo'av Rieck, Eric Sedgwick, Arkadiy Skopenkov, Michael Skotnica, Riste Škrekovski, Marek Sterzik, Dmitry Tonkonog, Jan Volec, Kathrin Vorwerk, Uli Wagner