Martin Tancer - publications

My research interests:

Computational topology, geometric and topological combinatorics, 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)

M. Tancer: Pach's animal problem within the bounding box. Preprint at Arxiv. (To appear at SoCG 2024.)
M. Tancer: Simpler algorithmically unrecognizable 4-manifolds. Preprint at Arxiv.
P. Patak, M. Tancer: Shellability is hard even for balls. Preprint at Arxiv. (Appeared at STOC 2023.)
C. Legrand-Duchesne, A. Rai., M. Tancer: Parameterized complexity of untangling knots. Preprint at Arxiv. (Appeared at ICALP 2022.)

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

P. Patak, M. Tancer: Embeddings of k-complexes into 2k-manifolds. Preprint at Arxiv. Discrete and Computational Geometry 71 (2024), 960--991.
D. Bulavka, M. Tancer, M. Tyomkyn: Weak saturation of multipartite hypergraphs. Preprint at Arxiv. Combinatorica 43 (2023), 1081--1102.
M. Skotnica, M. Tancer: NP-hardness of computing PL geometric category in dimension 2. Preprint at Arxiv. SIAM Journal on Discrete Mathematics 37(3) (2023), 2016--2029.
V. Kaluza, M. Tancer: Even maps, the Colin de Verdière number and representations of graphs. Preprint at Arxiv. Combinatorica 42 (2022), 1317--1345.
the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), 2642--2657.
Z. Patakova, M. Tancer, U. Wagner: Barycentric cuts through a convex body. Preprint at Arxiv. Discrete and Computational Geometry 68 (2022), 1133--1154.
36th International Symposium on Computational Geometry (SoCG 2020), Leibniz International Proceedings in Informatics (LIPIcs), 164 (2020), 62:1-62:16.
T. Magnard, M. Skotnica, M. Tancer: Shellings and sheddings induced by collapses. Preprint at Arxiv. SIAM Journal on Discrete Mathematics 35(3) (2021), 1978--2002.
A. de Mesmay, Y. Rieck, E. Sedgwick, M. Tancer: The unbearable hardness of unknotting. Preprint at Arxiv. Advances in Mathematics 381 (2021), art. no. 107648.
35th International Symposium on Computational Geometry (SoCG 2019), Leibniz International Proceedings in Informatics (LIPIcs), 129 (2019), 49:1-49:19.
A. de Mesmay, Y. Rieck, E. Sedgwick, M. Tancer: Embeddability in R^3 is NP-hard. Preprint at Arxiv. Journal of the ACM 67(4) (2020), art. no. 20.
the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 1316--1329.
K. Adiprasito, E. Nevo, M. Tancer: On Betti numbers of flag complexes with forbidden induced subgraphs. Preprint at Arxiv. Mathematical Proceedings of the Cambridge Philosophical Society 168(3) (2020), 567-600.
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.
34th International Symposium on Computational Geometry (SoCG 2018), Leibniz International Proceedings in Informatics (LIPIcs), 99 (2018), 41:1-41:15.
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.
the thirtieth annual symposium on Computational geometry, (SoCG 2014), 78-84.
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.
31st International Symposium on Computational Geometry (SoCG 2015), Leibniz International Proceedings in Informatics (LIPIcs), 34 (2015), 476-490.
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.
31st International Symposium on Computational Geometry (SoCG 2015), Leibniz International Proceedings in Informatics (LIPIcs), 34 (2015), 507-521.
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.
the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016), Lecture Notes in Computer Science, 9801 (2016), 454-467.
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.
32nd International Symposium on Computational Geometry (SoCG 2016), Leibniz International Proceedings in Informatics (LIPIcs), 51 (2016), 43:1-43:16.
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.
International Symposium on Graph Drawing (GD 2013), Lecture notes in Computer Science, 8242 (2013), 472-483.
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.
European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2013), 559-565.
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.
the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), 855-864.
M. Tancer: d-collapsibility is NP-complete for d greater or equal to 4. Chicago Journal of Theoretical Computer Science, 2010, Preprint at Arxiv.
European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), Electronic Notes in Discrete Mathematics, 34 (2009), 53-57.
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.

Papers in international fully refereed conferences without a journal version

D. Bulavka, A. Goodarzi, M. Tancer: Optimal bounds for the colorful fractional Helly theorem. In proceedings of 37th Symposium on Computational Geometry (SoCG 2021), Leibniz International Proceedings in Informatics (LIPIcs) 189 (2021), 19:1-19:14. Full version at Arxiv.
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, Denys Bulavka, Éric Colin de Verdière, Zdeněk Dvořák, Xavier Goaoc, Afshin Goodarzi, 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, Clément Legrand-Duchesne, 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, Ashutosh Rai, Yo'av Rieck, Eric Sedgwick, Arkadiy Skopenkov, Michael Skotnica, Riste Škrekovski, Marek Sterzik, Dmitry Tonkonog, Mykhaylo Tyomkyn, Jan Volec, Kathrin Vorwerk, Uli Wagner