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.
M. Tancer:
Simpler algorithmically unrecognizable 4-manifolds.
Preprint at Arxiv.
P. Patak, M. Tancer:
Shellability is hard even for balls.
Preprint at Arxiv.
C. Legrand-Duchesne, A. Rai., M. Tancer:
Parameterized complexity of untangling knots.
Preprint at Arxiv.
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