The preprints are divided into 3 Focus Areas. If you only want to see articles from a specific focus area just search for "Focus Area i" using the search bar below.



28 publications

Dual-to-kernel learning with ideals

Franz Király, Martin Kreuzer, Louis Theran

- Focus Area 1: High-complexity Geometry - In this paper, we propose a theory which unifies kernel learning and symbolic algebraic methods. We show that both worlds are inherently dual to each other, and we use this duality to combine the structure-awareness of algebraic methods with the efficiency and generality of kernels. The main idea lies in relating polynomial rings to feature space, and ideals to manifolds, then exploiting this generative-discriminative duality on kernel matrices. We illustrate this by proposing two algorithms, IPCA and AVICA, for simultaneous manifold and feature learning, and test their accuracy on synthetic and real world data.

Tverberg plus constraints

Pavle Blagojević, Florian Frick, Günter M. Ziegler

Focus Area 3: Topological connectivity and diameter of Discrete Structures Many of the strengthenings and extensions of the topological Tverberg theorem can be derived with surprising ease directly from the original theorem: For this we introduce a proof technique that combines a concept of "Tverberg unavoidable subcomplexes" with the observation that Tverberg points that equalize the distance from such a subcomplex can be obtained from maps to an extended target space. Thus we obtain simple proofs for many variants of the topological Tverberg theorem, such as the colored Tverberg theorem of Zivaljevic and Vrecica (1992). We also get a new strengthened version of the generalized van Kampen-Flores theorem by Sarkaria (1991) and Volovikov (1996), an affine version of their "j-wise disjoint" Tverberg theorem, and a topological version of Soberon's (2013) result on Tverberg points with equal barycentric coordinates.

Coherence and sufficient sampling densities for reconstruction in compressed sensing

Franz J. Király, Louis Theran

-Focus Area 1: High-complexity Geometry - We give a new, very general, formulation of the compressed sensing problem in terms of coordinate projections of an analytic variety, and derive sufficient sampling rates for signal reconstruction. Our bounds are linear in the coherence of the signal space, a geometric parameter independent of the specific signal and measurement, and logarithmic in the ambient dimension where the signal is presented. We exemplify our approach by deriving sufficient sampling densities for low-rank matrix completion and distance matrix completion which are independent of the true matrix.

Algebraic matroids with graph symmetry

Franz J. Király, Zvi Rosen, Louis Theran

- Focus Area 1: High-complexity Geometry - This paper studies the properties of two kinds of matroids: (a) algebraic matroids and (b) finite and infinite matroids whose ground set have some canonical symmetry, for example row and column symmetry and transposition symmetry. For (a) algebraic matroids, we expose cryptomorphisms making them accessible to techniques from commutative algebra. This allows us to introduce for each circuit in an algebraic matroid an invariant called circuit polynomial, generalizing the minimal poly- nomial in classical Galois theory, and studying the matroid structure with multivariate methods. For (b) matroids with symmetries we introduce combinatorial invariants capturing structural properties of the rank function and its limit behavior, and obtain proofs which are purely combinatorial and do not assume algebraicity of the matroid; these imply and generalize known results in some specific cases where the matroid is also algebraic. These results are motivated by, and readily applicable to framework rigidity, low-rank matrix completion and determinantal varieties, which lie in the intersection of (a) and (b) where additional results can be derived. We study the corresponding matroids and their associated invariants, and for selected cases, we characterize the matroidal structure and the circuit polynomials completely.

Derived subdivisions make every PL sphere polytopal.

Ivan Izmestiev, Karim Adiprasito

Focus Area 2: Delaunay Geometry We give a simple proof that some iterated derived subdivision of every PL sphere is combinatorially equivalent to the boundary of a simplicial polytope, thereby resolving a problem of Billera (personal communication).

Shapes of polyhedra, mixed volumes, and hyperbolic geometry.

Ivan Izmestiev, François Fillastre

Focus Area 2: Delaunay Geometry We are generalizing to higher dimensions the Bavard-Ghys construction of the hyperbolic metric on the space of polygons with fixed directions of edges. The space of convex d-dimensional polyhedra with fixed directions of facet normals has a decomposition into type cones that correspond to different combinatorial types of polyhedra. This decomposition is a subfan of the secondary fan of a vector configuration and can be analyzed with the help of Gale diagrams. We construct a family of quadratic forms on each of the type cones using the theory of mixed volumes. The Alexandrov-Fenchel inequalities ensure that these forms have exactly one positive eigenvalue. This introduces a piecewise hyperbolic structure on the space of similarity classes of polyhedra with fixed directions of facet normals. We show that some of the dihedral angles on the boundary of the resulting cone-manifold are equal to \pi/2.

Extremal edge polytopes

Tran Manh Tuan, Günter M. Ziegler

Focus Area 2: Delaunay Geometry The "edge polytope" of a finite graph G is the convex hull of the columns of its vertex-edge incidence matrix. We study extremal problems for this class of polytopes. For k < 4 we determine the maximum number of vertices of k-neighborly edge polytopes up to a sublinear term. We also construct a family of edge polytopes with exponentially-many facets.

Special positions of body-and-cad frameworks

James Farre, Audrey Lee-St.John, Jessica Sidman, Louis Theran

- Focus Area 1: High-complexity Geometry - A recent result provides a combinatorial characterization of the generic rigidity for the majority of Computer Aided Design (CAD) structures. However, an algorithm based on this result will incorrectly classify a design as well-constrained if it is in a special (non-generic) position allowing an internal motion. Since, in practice, CAD users often rely on highly organized structural elements and design patterns which may exhibit this non-generic behavior, we seek an approach to determine whether a design is in a special position. We present a combinatorial approach for finding the factors of the polynomial whose vanishing indicates a special position. For certain structures, we further find geometric properties determining when factors of the polynomial vanish by using the Grassmann-Cayley algebra and present case studies demonstrating our approach.

Highly symmetric fundamental cells for lattices in R^2 and R^3

Focus Area 1: High-complexity Geometry The fundamental cell of a lattice {\Gamma} in d-dimensional Euclidean space E(d) is the fundamental domain E(d)/{\Gamma}, viewed as a compact subset of E(d). It is shown that most lattices {\Gamma} in two- and in three-dimensional Euclidean space possess fundamental cells F having more symmetries than the point group P({\Gamma}), i.e., the subgroup P({\Gamma}) of O(d) fixing {\Gamma}. In particular, P({\Gamma}) is a subgroup of the symmetry group S(F) of F of index 2 in these cases. The exceptions are rhombic lattices in the plane case and cubic lattices in the three-dimensional case

On Highly regular embeddings

Pavle Blagojević, Wolfgang Lück, Günter M. Ziegler

Focus Area 3: Topological connectivity and diameter of Discrete Structures Given parameters k, l, and d, we give new lower bounds on the dimensions N such that there are maps from R^d to R^N that are k-regular, l-skew embeddings, or k-regular-l-skew embeddings. This extends and sharpens results due to Chisholm (1979) and Ghomi-Tabachnikov (2008).

Unimodular triangulations of dilated 3-polytopes

Francisco Santos, Günter M. Ziegler

Focus Area 2: Delaunay Geometry A seminal result in the theory of toric varieties, due to Knudsen, Mumford and Waterman (1973), asserts that for every lattice polytope P there is a positive integer k such that the dilated polytope kP has a unimodular triangulation. In dimension 3, Kantor and Sarkaria (2003) have shown that k=4 works for every polytope. But this does not imply that every k>4 works as well. We here study the values of k for which the result holds showing that: 1. It contains all composite numbers. 2. It is an additive semigroup. These two properties imply that the only values of k that may not work (besides 1 and 2, which are known not to work) are k∈{3,5,7,11}. With an ad-hoc construction we show that k=7 and k=11 also work, except in this case the triangulation cannot be guaranteed to be "standard" in the boundary. All in all, the only open cases are k=3 and k=5.

Frameworks with forced symmetry I: Reflections and rotations

Justin Malestein, Louis Theran

- Focus Area 1: High-complexity Geometry - We give a combinatorial characterization of generic frameworks that are minimally rigid under the additional constraint of maintaining symmetry with respect to a finite order rotation or a reflection. To establish these results we develop a new technique for deriving linear representations of sparsity matroids on colored graphs and extend the direction network method of proving rigidity characterizations to handle reflections.

Laplacian ideals, arrangements, and resolutions

Anton Dochtermann, Raman Sanyal

Appeared In: Journal of Algebraic Combinatorics, accepted for publication

Focus Area 1: High-complexity Geometry The Laplacian matrix of a graph G describes the combinatorial dynamics of the Abelian Sandpile Model and the more general Riemann-Roch theory of G. The lattice ideal associated to the lattice generated by the columns of the Laplacian provides an algebraic perspective on this recently (re)emerging field. This ideal I_G has a distinguished monomial initial ideal M_G, characterized by the property that the standard monomials are in bijection with the G-parking functions of the graph G. The ideal M_G was also introduced by Postnikov and Shapiro (2004) in the context of monotone monomial ideals. We study resolutions of M_G and show that a minimal free cellular resolution is supported on the bounded subcomplex of a section of the graphical arrangement of G. This generalizes constructions from Postnikov and Shapiro (for the case of the complete graph) and connects to work of Manjunath and Sturmfels, and of Perkinson et al. on the commutative algebra of Sandpiles. As a corollary we verify a conjecture of Perkinson et al. regarding the Betti numbers of M_G, and in the process provide a combinatorial characterization in terms of acyclic orientations.

Many polytopes with low-dimensional realization space

Karim Adiprasito, Günter M. Ziegler

Focus Area 1: High-complexity Geometry We construct an infinite family of 4-polytopes whose realization spaces have dimension smaller or equal to 96. This in particular settles a problem going back to Legendre and Steinitz: To bound the dimension of the realization space of a polytope in terms of its f-vector. Moreover, we derive an infinite family of combinatorially distinct 69-dimensional polytopes whose realization is unique up to projective transformation. This answers a problem posed by Perles and Shephard in the sixties.

The algebraic combinatorial approach for low-rank matrix completion

Franz Kiraly, Louis Theran, Ryota Tomioka, Takeaki Uno

Focus Area 1: High-complexity Geometry We propose an algebraic combinatorial framework for the problem of completing partially observed low-rank matrices. We show that the intrinsic properties of the problem, including which entries can be reconstructed, and the degrees of freedom in the reconstruction, do not depend on the values of the observed entries, but only on their position. We associate combinatorial and algebraic objects, differen- tials and matroids, which are descriptors of the particular reconstruction task, to the set of observed entries, and apply them to obtain reconstruction bounds. We show how similar techniques can be used to obtain reconstruction bounds on general compressed sensing problems with algebraic compression constraints. Using the new theory, we develop several algorithms for low-rank matrix completion, which allow to determine which set of entries can be potentially reconstructed and which not, and how, and we present algorithms which apply algebraic combinatorial methods in order to reconstruct the missing entries.

Smooth hyperbolicity cones are spectrahedral shadows

Tim Netzer, Raman Sanyal

Appeared In: Math. Prog. B, special issue `Lifts of Convex Sets in Optimization', accepted for publication

Focus Area 1: High-complexity Geometry Hyperbolicity cones are convex algebraic cones arising from hyperbolic polynomials. A well-understood subclass of hyperbolicity cones is that of spectrahedral cones and it is conjectured that every hyperbolicity cone is spectrahedral. In this paper we prove a weaker version of this conjecture by showing that every smooth hyperbolicity cone is the linear projection of a spectrahedral cone, that is, a spectrahedral shadow.

Equivariant topology of configuration spaces

Pavle V. M. Blagojević, Wolfgang Lück, Günter M. Ziegler

Focus Area 3: Topological connectivity and diameter of Discrete Structures We study the Fadell-Husseini index of the configuration space F(R^d,n) with respect to different subgroups of the symmetric group S_n. For p prime and d>0, we completely determine Index_{Z/p}(F(R^d,p);F_p) and partially describe Index{(Z/p)^k}(F(R^d,p^k);F_p). In this process we obtain results of independent interest, including: (1) an extended equivariant Goresky-MacPherson formula, (2) a complete description of the top homology of the partition lattice Pi_p as an F_p[Z_p]-module, and (3) a generalized Dold theorem for elementary abelian groups. The results on the Fadell-Husseini index yield a new proof of the Nandakumar & Ramana Rao conjecture for a prime. For n=p^k a prime power, we compute the Lusternik-Schnirelmann category cat(F(R^d,n)/S_n)=(d-1)(n-1), and for spheres obtain the bounds (d-1)(n-1)\le cat(F(S^d,n)/S_n)\le (d-1)(n-1)+1. Moreover, we extend coincidence results related to the Borsuk-Ulam theorem, as obtained by Cohen & Connett, Cohen & Lusk, and Karasev & Volovikov.

Arithmetic of marked poset polytopes, monotone triangle reciprocity,and partial colorings

Katharina Jochemko, Raman Sanyal

Focus Area 1: High-complexity Geometry For a poset P, a subposet A, and an order preserving map F from A into the real numbers, the marked order polytope parametrizes the order preserving extensions of F to P. We show that the function counting integral-valued extensions is a piecewise polynomial in F and we prove a reciprocity statement in terms of order-reversing maps. We apply our results to give a geometric proof of a combinatorial reciprocity for monotone triangles due to Fischer and Riegler (2011) and we consider the enumerative problem of counting extensions of partial graph colorings of Herzberg and Murty (2007).

Henneberg constructions and covers of cone-Laman graphs

Focus Area 1: High-complexity Geometry We give Henneberg-type constructions for three families of sparse colored graphs arising in the rigidity theory of periodic and other forced symmetric frameworks. The proof method, which works with Laman-sparse finite covers of colored graphs highlights the connection between these sparse colored families and the well-studied matroidal (k, l)-sparse families.

Generic rigidity of reflection frameworks

Justin Malestein, Louis Theran

Focus Area 1: High-complexity Geometry We review some recent results in the generic rigidity theory of planar frameworks with forced symmetry, giving a uniform treatment to the topic. We also give new combinatorial characterizations of minimally rigid periodic frameworks with fixed-area fundamental domain and fixed-angle fundamental domain.

Generic rigidity with forced symmetry and sparse colored graphs

Justin Malestein, Louis Theran

Focus Area 1: High-complexity Geometry We give a combinatorial characterization of generic minimally rigid reflection frameworks. The main new idea is to study a pair of direction networks on the same graph such that one admits faithful realizations and the other has only collapsed realizations. In terms of infinitesimal rigidity, realizations of the former produce a framework and the latter certifies that this framework is infinitesimally rigid.

Tight complexes in 3-space admit perfect discrete Morse functions

Karim Adiprasito, Bruno Benedetti

Focus Area 3: Topological connectivity and diameter of Discrete Structures In 1967, Chillingworth proved that all convex simplicial 3-balls are collapsible. Using the classical notion of tightness, we generalize this to arbitrary manifolds: We show that all tight simplicial 3-manifolds admit some perfect discrete Morse function. We also strengthen Chillingworth's theorem by proving that all convex simplicial 3-balls are non-evasive. In contrast, we show that many non-evasive 3-balls are not convex.

Face numbers of centrally symmetric polytopes from split graphs

Ragnar Freij, Matthias Henze, Moritz W. Schmitt, Günter M. Ziegler

Focus Area 1: High-complexity Geometry We analyze a remarkable class of centrally symmetric polytopes, the Hansen polytopes of split graphs. We confirm Kalai's 3^d-conjecture for such polytopes (they all have at least 3^d nonempty faces) and show that the Hanner polytopes among them (which have exactly 3^d nonempty faces) correspond to threshold graphs. Our study produces a new family of Hansen polytopes that have only 3^d+16 nonempty faces.

Many non-equivalent realizations of the associahedron

Cesar Ceballos, Francisco Santos, Günter M. Ziegler

Focus Area 1: High-complexity Geometry We show that three systematic construction methods for the $n$-dimensional associahedron, - as the secondary polytope of a convex $(n+3)$-gon (by Gelfand-Kapranov-Zelevinsky), - via cluster complexes of the root system $A_n$ (by Chapoton-Fomin-Zelevinsky), and - as Minkowski sums of simplices (by Postnikov) produce substantially different realizations, independent of the choice of the parameters for the constructions. The cluster complex and the Minkowski sum realizations were generalized by Hohlweg-Lange to produce exponentionally many distinct realizations, all of them with normal vectors in $\{0,\pm1\}^n$. We present another, even larger, exponential family, generalizing the cluster complex construction -- and verify that this family is again disjoint from the previous ones, with one single exception: The Chapoton-Fomin-Zelevinsky associahedron appears in both exponential families.

Generic rigidity of frameworks with orientation-preserving crystallographic symmetry (results appeared as part of "Frameworks with forced symmetry II", 2013)

Justin Malestein, Louis Theran

Focus Area 1: High-complexity Geometry We extend our generic rigidity theory for periodic frameworks in the plane to frameworks with a broader class of crystallographic symmetry. Along the way we introduce a new class of combinatorial matroids and associated linear representation results that may be interesting in their own right. The same techniques immediately yield a Maxwell-Laman-type combinatorial characterization for frameworks embedded in 2-dimensional cones that arise as quotients of the plane by a finite order rotation.

Metric Geometry, Convexity and Collapsibility

Karim Adiprasito, Bruno Benedetti

Collapsibility is a classical notion introduced by Whitehead as part of his simple homotopy theory. We provide several results relating it to metric geometry and convexity. (1) Every complex that is CAT(0) with a metric for which all vertex stars are convex is collapsible. Focus Area 3: Topological connectivity and diameter of Discrete Structures (2) Any linear subdivision of any polytope is simplicially collapsible after one barycentric subdivision. This solves up to one derived subdivision a classical question by Lickorish. (3) Any linear subdivision of any star-shaped polyhedron in R^s is simplicially collapsible after d-2 barycentric subdivisions at most. This presents progress on an old question by Goodrick. We furthermore provide the following applications: (1) Any simplicial complex admits a CAT(0) metric if and only if it admits collapsible triangulations. (2) All contractible manifolds (except for some 4-dimensional ones) admit collapsible CAT(0) triangulations. This provides a polyhedral version of a classical result of Ancel and Guilbault. (3) There are exponentially many geometric triangulations of S^d. This interpolates between the known result that boundaries of simplicial (d+1)-polytopes are exponentially many, and the conjecture that d-spheres are more than exponentially many. (4) In terms of the number of facets, there are only exponentially many geometric triangulations of space forms with bounded geometry. This establishes a discrete version of Cheeger's finiteness theorem.

Discrete Morse Theory is at least as perfect as Morse Theory

Focus Area 3: Topological connectivity and diameter of Discrete Structures In bounding the homology of a manifold, Forman’s Discrete Morse theory recovers the full precision of classical Morse theory: Given a PL triangulation of a manifold that admits a Morse function with ci critical points of index i, we show that some subdivision of the triangulation admits a boundary-critical discrete Morse function with ci interior critical cells of dimension d − i. This dualizes and extends a recent result by Gallais. Further consequences of our work are: (1) Every simply connected smooth d-manifold (d 6= 4) admits a locally constructible triangulation. (This solves a problem by Zivaljevi´c.) ˇ (2) Up to refining the subdivision, the classical notion of geometric connectivity can be translated combinatorially via the notion of collapse depth

Optimal bounds for the colored Tverberg problem

Pavle V. M. Blagojević, Benjamin Matschke, Günter M. Ziegler

Focus Area 3: Topological connectivity and diameter of Discrete Structures We prove a "Tverberg type" multiple intersection theorem. It strengthens the prime case of the original Tverberg theorem from 1966, as well as the topological Tverberg theorem of Barany et al. (1980), by adding color constraints. It also provides an improved bound for the (topological) colored Tverberg problem of Barany & Larman (1992) that is tight in the prime case and asymptotically optimal in the general case. The proof is based on relative equivariant obstruction theory.