31 citations · 127 across the 16 of their papers we have counts for
10 papers · 1 filter
Barycentric cuts through a convex body
Zuzana Patáková, Martin Tancer, Uli Wagner
Let be a convex body in (i.e., a compact convex set with nonempty interior). Given a point in the interior of , a hyperplane passing through is ca…
Shellability is NP-complete
Xavier Goaoc, Pavel Paták, Zuzana Patáková +2
We prove that for every , deciding if a pure, -dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Dan…
On Generalized Heawood Inequalities for Manifolds: a van Kampen--Flores-type Nonembeddability Result
Xavier Goaoc, and Isaac Mabillard, Pavel Paták +3
The fact that the complete graph does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood proble…
On Eigenvalues of Random Complexes
Anna Gundert, Uli Wagner
We consider higher-dimensional generalizations of the normalized Laplacian and the adjacency matrix of graphs and study their eigenvalues for the Linial-Meshulam model o…
On Topological Minors in Random Simplicial Complexes
Anna Gundert, Uli Wagner
For random graphs, the containment problem considers the probability that a binomial random graph contains a given graph as a substructure. When asking for the graph as a…
Bounding Helly numbers via Betti numbers
Xavier Goaoc, Pavel Paták, Zuzana Patáková +2
We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers and th…