A collection of unit cubes with integer coordinates in ℝ³ is an animal if its union is homeomorphic to the 3-ball. Pach’s animal problem asks whether any animal can be transformed to a single cube by adding or removing cubes one by one in such a way that any intermediate step is an animal as well. Here we provide an example of an animal that cannot be transformed to a single cube this way within its bounding box.

Abstract. Deciding whether a diagram of a knot can be untangled with a given number of moves (as a part of the input) is known to be NP-complete. In this paper we determine the parameterized complexity of this problem with respect to a natural parameter called defect. Roughly speaking, it measures the efficiency of the moves used in the shortest untangling sequence of Reidemeister moves. We show that in a shortest untangling sequence the [Formula: see text] moves, that is, the moves removing two adjacent crossings, can be essentially performed greedily. Using that, we show that this problem belongs to W[P] when parameterized by the defect. We also show that this problem is W[P]-hard by a reduction from Minimum axiom set.

The main goal of this paper is to show that shellability is NP-hard for triangulated d-balls (this also gives hardness for triangulated d-manifolds/d-pseudomanifolds with boundary) as soon as d ≥ 3. This extends our earlier work with Goaoc, Patáková and Wagner on hardness of shellability of 2-complexes and answers some questions implicitly raised by Danaraj and Klee in 1978 and explicitly mentioned by Santamaría-Galvis and Woodroofe. Together with the main goal, we also prove that collapsibility is NP-hard for 3-complexes embeddable in 3-space, extending an earlier work of the second author and answering an open question mentioned by Cohen, Fasy, Miller, Nayyeri, Peng and Walkington; and that shellability is NP-hard for 2-complexes embeddable in 3-space, answering another question of Santamaría-Galvis and Woodroofe (in a slightly stronger form than what is given by the main result).

Abstract. The PL geometric category of a polyhedron [Formula: see text], denoted [Formula: see text], is a combinatorial notion which provides a natural upper bound for the Lusternik–Schnirelmann category, and it is defined as the minimum number of PL collapsible subpolyhedra of [Formula: see text] that cover [Formula: see text]. In dimension 2 the PL geometric category is at most 3. It is easy to characterize/recognize 2-polyhedra [Formula: see text] with [Formula: see text]. Borghini provided a partial characterization of 2-polyhedra with [Formula: see text]. We complement his result by showing that it is NP-hard to decide whether [Formula: see text]. Therefore, we should not expect much more than a partial characterization, at least in an algorithmic sense. Our reduction is based on the observation that 2-dimensional polyhedra [Formula: see text] admitting a shellable subdivision satisfy [Formula: see text] and a (nontrivial) modification of the reduction of Goaoc, Paták, Patáková, Tancer and Wagner showing that shellability of 2-complexes is NP-hard.

Deciding whether a diagram of a knot can be untangled with a given number of moves (as a part of the input) is known to be NP-complete. In this paper we determine the parameterized complexity of this problem with respect to a natural parameter called defect. Roughly speaking, it measures the efficiency of the moves used in the shortest untangling sequence of Reidemeister moves. We show that the II- moves in a shortest untangling sequence can be essentially performed greedily. Using that, we show that this problem belongs to W[P] when parameterized by the defect. We also show that this problem is W[P]-hard by a reduction from Minimum axiom set.

Let K be a convex body in $$\mathbb {R}^n$$ (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of $$K \cap h$$ . In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least $$n+1$$ distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if $$p=p_0$$ is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for $$n \ge 2$$ , there are always at least three distinct barycentric cuts through the point $$p_0 \in K$$ of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through $$p_0$$ are guaranteed if $$n \ge 3$$ .

The well known fractional Helly theorem and colorful Helly theorem can be merged into the so called colorful fractional Helly theorem. It states: For every $α\in (0, 1]$ and every non-negative integer $d$, there is $β_{col} = β_{col}(α, d) \in (0, 1]$ with the following property. Let $\mathcal{F}_1, \dots, \mathcal{F}_{d+1}$ be finite nonempty families of convex sets in $\mathbb{R}^d$ of sizes $n_1, \dots, n_{d+1}$ respectively. If at least $αn_1 n_2 \cdots n_{d+1}$ of the colorful $(d+1)$-tuples have a nonempty intersection, then there is $i \in [d+1]$ such that $\mathcal{F}_i$ contains a subfamily of size at least $β_{col} n_i$ with a nonempty intersection. (A colorful $(d+1)$-tuple is a $(d+1)$-tuple $(F_1, \dots , F_{d+1})$ such that $F_i$ belongs to $\mathcal{F}_i$ for every $i$.) The colorful fractional Helly theorem was first stated and proved by Bárány, Fodor, Montejano, Oliveros, and Pór in 2014 with $β_{col} = α/(d+1)$. In 2017 Kim proved the theorem with better function $β_{col}$, which in particular tends to $1$ when $α$ tends to $1$. Kim also conjectured what is the optimal bound for $β_{col}(α, d)$ and provided the upper bound example for the optimal bound. The conjectured bound coincides with the optimal bounds for the (non-colorful) fractional Helly theorem proved independently by Eckhoff and Kalai around 1984. We verify Kim's conjecture by extending Kalai's approach to the colorful scenario. Moreover, we obtain optimal bounds also in more general setting when we allow several sets of the same color.

We say that a pure simplicial complex ${\mathbf K}$ of dimension $d$ satisfies the removal-collapsibility condition if ${\mathbf K}$ is either empty or ${\mathbf K}$ becomes collapsible after removing $\tilde \beta_d ({\mathbf K}; {\mathbb Z}_2)$ facets, where $\tilde \beta_d ({\mathbf K}; {\mathbb Z}_2)$ denotes the $d$th reduced Betti number. In this paper, we show that if the link of each face of a pure simplicial complex ${\mathbf K}$ (including the link of the empty face which is the whole ${\mathbf K}$) satisfies the removal-collapsibility condition, then the second barycentric subdivision of ${\mathbf K}$ is vertex decomposable and in particular shellable. This is a higher-dimensional generalization of a result of Hachimori, who proved that if the link of each vertex of a pure 2-dimensional simplicial complex ${\mathbf K}$ is connected and ${\mathbf K}$ becomes simplicially collapsible after removing $\tilde{\chi}({\mathbf K})$ facets, where $\tilde \chi ({\mathbf K})$ denotes the reduced Euler characteristic, then the second barycentric subdivision of ${\mathbf K}$ is shellable. For the proof, we introduce a new variant of decomposability of a simplicial complex, stronger than vertex decomposability, which we call star decomposability. This notion may be of independent interest.

Van der Holst and Pendavingh introduced a graph parameter σ, which coincides with the more famous Colin de Verdière graph parameter µ for small values. However, the definition of σ is much more geometric/topological directly reflecting embeddability properties of the graph. They proved µ(G) ≤ σ(G) + 2 and conjectured µ(G) ≤ σ(G) for any graph G. We confirm this conjecture. As far as we know, this is the first topological upper bound on µ(G) which is, in general, tight. Equality between µ and σ does not hold in general as van der Holst and Pendavingh showed that there is a graph G with µ(G) ≤ 18 and σ(G) ≥ 20. We show that the gap appears on much smaller values, namely, we exhibit a graph H for which µ(H) ≤ 7 and σ(H) ≥ 8. We also prove that, in general, the gap can be large: The incidence graphs Hq of finite projective planes of order q satisfy µ(Hq) ϵ O(q3/2) and σ(Hq) ≥ q2.

International audience

We prove that for every d ≥ 2, deciding if a pure, d -dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, d -dimensional, simplicial complex is k -decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d -dimensional complexes. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable.

We prove that the problem of deciding whether a 2- or 3-dimensional simplicial complex embeds into ℝ3 is NP-hard. This stands in contrast with the lower dimensional cases which can be solved in linear time, and a variety of computational problems in ℝ3 like unknot or 3-sphere recognition which are in NP ∩ co-NP (assuming the generalized Riemann hypothesis). Our reduction encodes a satisfiability instance into the embeddability problem of a 3-manifold with boundary tori, and relies extensively on techniques from low-dimensional topology, most importantly Dehn fillings on link complements.

We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in R 3 ? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere S 3 . The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S 3 , then there is also an embedding in which X has a short meridian , that is, an essential curve in the boundary of X bounding a disk in S 3 \ X with length bounded by a computable function of the number of tetrahedra of X .

The classical theorem of Fáry states that every planar graph can be represented by an embedding in which every edge is represented by a straight line segment. We consider generalizations of Fáry’s theorem to surfaces equipped with Riemannian metrics. In this setting, we require that every edge is drawn as a shortest path between its two endpoints and we call an embedding with this property a shortest path embedding . The main question addressed in this paper is whether given a closed surface S , there exists a Riemannian metric for which every topologically embeddable graph admits a shortest path embedding. This question is also motivated by various problems regarding crossing numbers on surfaces. We observe that the round metrics on the sphere and the projective plane have this property. We provide flat metrics on the torus and the Klein bottle which also have this property. Then we show that for the unit square flat metric on the Klein bottle there exists a graph without shortest path embeddings. We show, moreover, that for large g , there exist graphs G embeddable into the orientable surface of genus g , such that with large probability a random hyperbolic metric does not admit a shortest path embedding of G , where the probability measure is proportional to the Weil–Petersson volume on moduli space. Finally, we construct a hyperbolic metric on every orientable surface S of genus g , such that every graph embeddable into S can be embedded so that every edge is a concatenation of at most O ( g ) shortest paths.

The fact that the complete graph K_5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph K_n embeds in a closed surface M if and only if (n-3)(n-4) is at most 6b_1(M), where b_1(M) is the first Z_2-Betti number of M. On the other hand, Van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of K_{n+1}) embeds in R^{2k} if and only if n is less or equal to 2k+2. Two decades ago, Kuhnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k-1)-connected 2k-manifold with kth Z_2-Betti number b_k only if the following generalized Heawood inequality holds: binom{n-k-1}{k+1} is at most binom{2k+1}{k+1} b_k. This is a common generalization of the case of graphs on surfaces as well as the Van Kampen--Flores theorem. In the spirit of Kuhnel's conjecture, we prove that if the k-skeleton of the n-simplex embeds in a 2k-manifold with kth Z_2-Betti number b_k, then n is at most 2b_k binom{2k+2}{k} + 2k + 5. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k-1)-connected. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.

We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in R3? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S3, then there is also an embedding in which X has a short meridian, i.e., an essential curve in the boundary of X bounding a disk in S3 \ X with length bounded by a computable function of the number of tetrahedra of X.

A good cover in $\mathbb{R}^d$ is a collection of open contractible sets in $\mathbb{R}^d$ such that the intersection of any subcollection is either contractible or empty. Motivated by an analogy with convex sets, intersection patterns of good covers were studied intensively. Our main result is that intersection patterns of good covers are algorithmically unrecognizable. More precisely, the intersection pattern of a good cover can be stored in a simplicial complex called a nerve which records which subfamilies of the good cover intersect. A simplicial complex is topologically $d$-representable if it is isomorphic to the nerve of a good cover in $\mathbb{R}^d$. We prove that it is undecidable whether a given simplicial complex is topologically $d$-representable for any fixed $d \geq 5$. The result remains valid if we replace good covers with acyclic covers or with covers by open $d$-balls. As an auxiliary result we prove that if a simplicial complex is piecewise-linearly embeddable into $\mathbb{R}^d$, then it is topologically $d$-representable. We also supply this result with showing that if a “sufficiently fine” subdivision of a $k$-dimensional complex is $d$-representable and $k \leq \frac{2d-3}3$, then the complex is piecewise-linearly embeddable into $\mathbb{R}^d$.

Let EMBEDk→d be the following algorithmic problem: Given a finite simplicial complex K of dimension at most k, does there exist a (piecewise linear) embedding of K into ℝd? Known results easily imply polynomiality of EMBEDk→2 (k = 1,2; the case k = 1, d = 2 is graph planarity) and of EMBEDk→2k for all k ≥ 3 (even if k is not considered fixed). We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that EMBEDd→d and EMBED(d−1)→d are undecidable for each d ≥ 5. Our main result is NP-hardness of EMBED2→4 and, more generally, of EMBEDk→d for all k, d with d ≥ 4 and d ≥ k ≥ (2d − 2)/3.

For a graph G and its spanning tree T the backbone chromatic number, $\mathrm{BBC}(G,T)$, is defined as the minimum k such that there exists a coloring $c\colon V(G)\rightarrow\{1,2,\dots,k\}$ satisfying $|c(u)-c(v)|\geq1$ if $uv\in E(G)$ and $|c(u)-c(v)|\geq2$ if $uv\in E(T)$. Broersma et al. [J. Graph Theory, 55 (2007), pp. 137–152] asked whether there exists a constant c such that for every triangle-free graph G with an arbitrary spanning tree T the inequality $\mathrm{BBC}(G,T)\leq\chi(G)+c$ holds. We answer this question negatively by showing the existence of triangle-free graphs $R_n$ and their spanning trees $T_n$ such that $\mathrm{BBC}(R_n,T_n)=2\chi(R_n)-1=2n-1$. In order to answer the question, we obtain a result of independent interest. We modify the well-known Mycielski construction and construct triangle-free graphs $J_n$ for every integer n, with chromatic number n and 2-tuple chromatic number $2n$ (here 2 can be replaced by any integer t).

The problem of coloring the square of a graph naturally arises in connection with the distance labelings, which have been studied intensively. We consider this problem for sparse subcubic graphs. We show that the choosability $\chi_\ell(G^2)$ of the square of a subcubic graph G of maximum average degree d is at most four if $d<24/11$ and G does not contain a 5-cycle, at most five if $d<7/3$, and at most six if $d<5/2$. Wegner's conjecture claims that the chromatic number of the square of a subcubic planar graph is at most seven. Let G be a planar subcubic graph of girth g. Our result implies that $\chi_\ell(G^2)$ is at most four if $g\ge 24$, at most 5 if $g\ge 14$, and at most 6 if $g\ge 10$. For lower bounds, we find a planar subcubic graph $G_1$ of girth 9 such that $\chi(G_1^2)=5$ and a planar subcubic graph $G_2$ of girth 5 such that $\chi(G_2^2)=6$. As a consequence, we show that the problem of 4-coloring of the square of a subcubic planar graph of girth $g=9$ is NP-complete. We conclude the paper by posing a few conjectures.

An L(2,1)-labeling of a graph G is a mapping c : V(G) \to {0,...,K} such that the labels of two adjacent vertices differ by at least two and the labels of vertices at distance two differ by at least one. A hole of c is an integer h \in {0,...,K} that is not used as a label for any vertex of G. The smallest integer K for which an L(2,1)-labeling of G exists is denoted by lambda(G). The minimum number of holes in an optimal labeling, i.e., a labeling with K = lambda(G), is denoted by rho(G). Georges and Mauro [SIAM J. Discrete Math., 19 (2005), pp. 208-223] showed that rho(G) \le Delta, where Delta is the maximum degree of G, and conjectured that if rho(G) = Delta and G is connected, then the order of G is at most Delta(Delta + 1). We disprove this conjecture by constructing graphs G with rho(G) = Delta and order \lfloor (Delta + 1) 2 /4 \rfloor (Delta + 1) \approx Delta 3 /4.