Martin Tancer - publications

My research interests:

Geometrical and topological combinatorics, graph colorings

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)

A. de Mesmay, Y. Rieck, E. Sedgwick, M. Tancer: Embeddability in R^3 is NP-hard. Preprint at Arxiv. (To appear at SODA 2018.)
A. Skopenkov, M. Tancer: Hardness of almost embedding simplicial complexes in R^d. Preprint at Arxiv.
I. Barany, R. Meshulam, E. Nevo, M. Tancer: Pach's selection theorem does not admit a topological extension. Preprint at Arxiv.
K. Adiprasito, E. Nevo, M. Tancer: On Betti numbers of flag complexes with forbidden induced subgraphs. Preprint at Arxiv.

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

28. J. Matousek, E. Sedgwick, M. Tancer, U. Wagner: Embeddability in the 3-sphere is decidable. Preprint at Arxiv. To appear in Journal of the ACM (Extended abstract appeared at SoCG 2014.)
27. 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.
26. 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.
25. 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.
24. 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.
23. 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.
22. M. Tancer: Recognition of collapsible complexes is NP-complete. Discrete and Computational Geometry. 55(1) (2016), 21-38. Preprint at Arxiv.
21. 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.
20. 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.
19. M. Tancer: Shellability of the higher pinched Veronese posets. Journal of Algebraic Combinatorics. 40(3) (2014), 711-742. Preprint at Arxiv.
18. M. Tancer, K. Vorwerk: Non-embeddability of geometric lattices and buildings. Discrete and Computational Geometry. 51(4) (2014), 779-801. Preprint at Arxiv.
17. M. Tancer, D. Tonkonog: Nerves of Good covers are algorithmically unrecognizable. SIAM Journal on Computing. 42(4) (2013), 1697-1719. Preprint at Arxiv.
16. 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.
15. M. Tancer: A counterexample to Wegner's conjecture on good covers, Discrete and Computational Geometry. 47(2) (2012), 266-274. Preprint at Arxiv.
14. 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).
13. M. Tancer: Strong d-collapsibility, Contributions to Discrete Mathematics, 6(2) (2011), 32-35. Link to the journal (open access).
12. 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.
11. M. Tancer: d-collapsibility is NP-complete for d greater or equal to 4. Chicago Journal of Theoretical Computer Science, 2010, Preprint at Arxiv.
10. 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.
9. 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).
8. A. Bjorner, M. Tancer: Combinatorial Alexander Duality - a Short and Elementary Proof, Discrete and Computational Geometry 42(4) (2009), 586-593. Preprint at Arxiv.
7. J. Matousek, M. Tancer: Dimension Gaps Between Representability and Collapsibility, Discrete and Computational Geometry 42(4) (2009), 631-639. Preprint at Arxiv.
6. 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.
5. J. Miskuf, R. Skrekovski, M. Tancer: Backbone Colorings and Generalized Mycielski's Graphs, SIAM Journal on Discrete Mathematics 23 (2009), 1063-1070. Full version.
4. 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.
3. 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).
2. J. Hladky, J. Novak, P. Pyrih, M. Sterzik, M. Tancer: An engine breaking ΩEP-property, Topology and its Applications 153(18) (2006), 3621-3626.
1. 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

29. 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)

30. 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, Jozef Jirásek, Vojtěch Kaluža, Roman Karasev, Pavel Klavík, Daniel Kráľ, Jan Kynčl, Borut Lužar, 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, Riste Škrekovski, Marek Sterzik, Dmitry Tonkonog, Jan Volec, Kathrin Vorwerk, Uli Wagner