12 papers
On the size of k-irreducible triangulations
Vincent Delecroix, Oscar Fontaine, Arnaud de Mesmay
A triangulation of a surface is k-irreducible if every non-contractible curve has length at least k and any edge contraction breaks this property. Equivalently, every edge belongs…
Devil's Games and : Continuous Games complete for the First-Order Theory of the Reals
Lucas Meijer, Arnaud de Mesmay, Tillmann Miltzow +2
We introduce the complexity class Quantified Reals (). Let FOTR be the set of true sentences in the first-order theory of the reals. A language is in $\text…
Crossing numbers of dense graphs on surfaces
Alfredo Hubard, Arnaud de Mesmay, Hugo Parlier
In this paper, we provide upper and lower bounds on the crossing numbers of dense graphs on surfaces, which match up to constant factors. First, we prove that if is a dense eno…
Hard diagrams of split links
Corentin Lunel, Arnaud de Mesmay, Jonathan Spreer
Deformations of knots and links in ambient space can be studied combinatorially on their diagrams via local modifications called Reidemeister moves. While it is well-known that, in…
Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries
Erin Wolf Chambers, Francis Lazarus, Arnaud de Mesmay +1
In this paper we prove that the problem of deciding contractibility of an arbitrary closed curve on the boundary of a 3-manifold is in NP. We emphasize that the manifold and the cu…
Link Crossing Number is NP-hard
Arnaud de Mesmay, Marcus Schaefer, Eric Sedgwick
We show that determining the crossing number of a link is NP-hard. For some weaker notions of link equivalence, we also show NP-completeness.