math_groups_discgeom

Abstracts

Karim Adiprasito

"Rigidity theory, propagation phenomena and applications"

I will discuss some relations between minimal rigidity and the propagation phenomenon in commutative algebra, and in particular show how rigidity theory can be used to rederive and generalize, in a beautiful geometric way, some classical propagation results due to Novik--Swartz, Green and others. I will then apply this to the study of polytopes and regularity of triangulations, solving some questions of Kalai and McMullen. Finally, I will speculate on some further developments.

Phan Thanh An

"Straightest Geodesics for Finding Shortest Paths inside a Triangle Sequence in 3D"

We present an efficient algorithm for finding the exact shortest path between two points inside a triangle sequence in three-dimensional space. Firstly, the concept of "funnels" inside a sequence of faces in 3D that is a generalization of funnels in 2D is introduced. Secondly, the method of orienting straightest geodesics for determining funnels is presented. It includes the concepts of "final straightest geodesics" and "orienting straightest geodesics" (the special cases of straightest geodesics) inside a so-called extended funnel. Consequently, the exact shortest path is determined by paths of orienting straightest geodesics of the funnels and a final straightest geodesic of the final funnel. It takes O(n2) time without planar unfolding and is visualized by JavaView software. Related work: Xin & Wang's method (Computer-Aided Design, V.39, 2007) takes O(n2) complexity, but using planar unfolding for the triangle sequence.

Authors: P.T. An (Hanoi), D.T. Giang (Lisbon), T.V. Hoai (HCM City), H. X. Phu (Hanoi), K. Polthier (Berlin).

Federico Ardila

"Positroids, non-crossing partitions, and positively oriented matroids"

We investigate the role that non-crossing partitions play in the study of positroids, a class of matroids introduced by Postnikov. We prove that every positroid can be constructed uniquely by choosing a non-crossing partition on the ground set, and then freely placing the structure of a connected positroid on each of the blocks of the partition. We use this to enumerate connected positroids, and we prove that the probability that a positroid on [n] is connected equals 1/e2 asymptotically. We also prove da Silva’s 1987 conjecture that any positively oriented matroid is a positroid; that is, it can be realized by a set of vectors in a real vector space. It follows from this result that the positive matroid Grassmannian (or positive MacPhersonian) is homeomorphic to a closed ball. This is joint work with Felipe Rincón (Warwick) and Lauren Williams (Berkeley).

Ulrich Bauer

"The Morse theory of Čech and Delaunay complexes."

Given a finite set of points in ℝⁿ and a positive radius, we consider the Čech, Delaunay–Čech, Delaunay (alpha shape), and wrap complexes as examples of a generalized discrete Morse theory. We prove that the four complexes are simple-homotopy equivalent by a sequence of simplicial collapses, and the same is true for their weighted versions. Our results have applications in topological data analysis and in the reconstruction of shapes from sampled data. Joint work with Herbert Edelsbrunner.

 

Louis J. Billera

"Even more intriguing, if rather less plausible..."

The title is how Peter McMullen described his own conjectured characterization of the f-vectors of simplicial polytopes in his 1971 lecture notes on the upper bound conjecture written with Geoffrey Shephard. Yet by the end of that decade, the so-called g-conjecture would become the g-theorem, and algebraic combinatorics (as practiced at MIT) would have attracted the attention of mainstream mathematics. I will briefly describe some of the events leading to this proof and some of its still developing consequences.

 

Pavle Blagojević

"Topology of the Grünbaum-Hadwiger-Ramos hyperplane mass partition problem"

In 1960 Grünbaum asked whether for any finite mass in ℝd there are d hyperplanes that cut it into 2d equal parts. This was proved by Hadwiger (1966) for d≤3, but disproved by Avis (1984) for d≥5, while the case d=4 remained open. More generally, Ramos (1996) asked for the smallest dimension Δ(j,k) in which for any j masses there are k affine hyperplanes that simultaneously cut each of the masses into 2k equal parts. At present the best lower bounds on Δ(j,k) are provided by Avis (1984) and Ramos (1996), the best upper bounds by Mani-Levitska, Vrećica & Živaljević (2006). The problem has been an active testing ground for advanced machinery from equivariant topology. 
In this talk, using the relative equivariant obstruction theory on the join CS/TM scheme, we prove that Δ(j,2)= ceil((3j)/2) in the cases when j-1, or j, or j+1 is a power of 2, j≥1.

This is joint work with Florian Frick, Albert Haase and Günter M. Ziegler

 

Michael Farber

"Topology of large random simplicial complexes"

The combinatorics of acyclic complexes, chromatic numbers and the topology of the independent complex of a graph, repeating the boundary operator, and balanced shifting and rigidity.

 

Vissarion Fisikopoulos

"The Newton polytope of the Sparse Resultant"

The Newton polytope of a polynomial characterizes the polynomial more precisely than total degree, thus offering the main representation in sparse elimination theory. The (sparse) resultant is a fundamental object in computational algebraic geometry and is important in applications such as polynomial system solving and Computer Aided Design.

This talk is about the combinatorics of Newton polytopes of (sparse) resultants. These are known in the classical (or Sylvester) case and up to dimension 3. The results are by Gelfand, Kapranov, Zelevinsky and Sturmfels. We will discuss an extension of this work by studying the combinatorial characterization of 4-dimensional resultant polytopes, which show a greater diversity and involve computational and combinatorial challenges. This is a joint work with Alicia Dickenstein and Ioannis Emiris.

Florian Frick

"Counterexamples to the topological Tverberg conjecture"

The "topological Tverberg conjecture'' (Tverberg, 1978) states that any continuous map of a simplex of dimension (r-1)(d+1)→ℝd maps points from r disjoint faces of the simplex to the same point in ℝd. This was established for affine maps by Tverberg (1966), for the case when r is a prime by Bárány, Shlosman and Szűcs (1981), and for prime power r by Özaydιn (1987). We combine the generalized van Kampen theorem announced by Mabillard and Wagner (2014) with the constraint method (joint work with P. Blagojević and G. M. Ziegler (2014)), and thus prove the existence of counterexamples to the topological Tverberg conjecture for any number r of faces that is not a prime power. However, these counterexamples require that the dimension d of the codomain is sufficiently high: the smallest counterexample we obtain is for a map of the 100-dimensional simplex to ℝ19, for r=6.

Christian Haase

"Update on unimodular triangulations"

A lattice polytope is a polytope with integer vertices. A lattice simplex is unimodular if every integer point is an integral affine combination of its vertices. A triangulation is unimodular if all its simplices are.

Popular belief has it that the average lattice polytope you pick up on the street will not have a unimodular triangulation. Yet, many "interesting" polytopes do, in each case yielding a theorem - ranging from Enumerative Combinatorics, to Integer Programming, to Algebraic Geometry.

In this talk I will present several instances of interesting polytopes admitting a unimodular triangulation. The latest addition to the family being the `lecture hall simplex' arising in partition analysis.

This is joint work with Andreas Paffenholz (Darmstadt), Lindsay Piechnik (High Point), and Francisco Santos (Santander).

Gil Kalai

"Some questions and results in topological combinatorics"

I will describe some old and new results and problems in topological combinatorics. Topics include, topological Helly-type theorems, the combinatorics of acyclic complexes, chromatic numbers and the topology of the independent complex of a graph, repeating the boundary operator, and balanced shifting and rigidity.

Roman Karasev

"Symplectic ideas in convex geometry."

I will survey recent works where the techniques of symplectic geometry helped to prove some results, or at least provide the valuable intuition, in some problems of convex and discrete geometry. This started from the work of Artstein-Avidan and Ostrover relating the mysterious invariants called "symplectic capacities'' to much more elementary invariants of billiards in convex bodies. After that, in subsequent works with my participation the billiards were studied more deeply and the famous conjectures of Mahler and Bang in convex geometry were related to certain conjectures in symplectic geometry. We do not always find the necessary symplectic machinery for our convexity problems; but we benefit from the general point of view provided by symplectic geometry and see the "right questions'' to ask in convex and discrete geometry.

Roy Meshulam

"Uncertainty principles and homology"


Uncertainty type inequalities reflect quantitative aspects of the general principle that a nonzero function and its Fourier transform cannot both be sharply localized. In this talk we'll describe a link between discrete uncertainty inequalities on the cyclic group and the topology of certain arithmetically defined simplicial complexes called sum complexes. The main ingredient in the proofs is the determination of the homology of sum complexes with arbitrary field coefficients. The computation depends on some properties of generalized Vandermonde determinants over modular group algebras and involves Schur functions.

Igor Pak

"Tiling spaces with congruent polyhedra"

A classical open problem going back to Fёdorov and Voronoy asks whether a polytope which tiles ℝ3 can have an unbounded number of faces. Hilbert's 18th problem asks (in part) what polytopes arise as fundamental regions of group actions. I will give a selective survey of over a hundred years worth of progress on these problems and their variations, emphasizing tiling constructions in the spherical and the hyperbolic spaces. I will then present our new tiling constructions, notably of the neighborly spherical tilings. Joint work with Danny Nguyen.

Raman Sanyal

"Translation-invariant valuations and combinatorial positivity"

In this talk, I will discuss combinatorial and geometric properties of translation-invariant valuations on polytopes. The starting point for our work is Stanley's nonnegativity/monotonicity theorems for Ehrhart polynomials: The h*-vector of a lattice polytope is nonnegative and monotone with respect to inclusion. Every translation-invariant valuation furnishes the notion of an h*-vector. We give a simple characterization of valuations with a nonnegative h*-vector. For general polytopes, this highlights the role played by the volume. For lattice polytopes, this yields an interesting interplay of geometry and combinatorics. This is joint work with Katharina Jochemko.

Louis Theran

"Learning with cross kernel matrices and Ideal-PCA"

The dimension reduction problem asks for a description of a manifold M in ℝn, given a point set P sampled from M with noise. I’ll describe an approach for the case when M is algebraic that makes a connection between approximate vanishing ideals and polynomial kernels. The same idea can be used to speed up a variety of algorithms that make use of dense kernel matrices.

Joint work with Franz Király and Martin Kreuzer.

Mimi Tsuruga

"Heuristics for Sphere Recognition"

Given a d-dimensional simplicial complex K, can we determine whether K is a PL-sphere? On the theoretical side, for d=3 the problem is in NP, for d≥5 it is undecidable, and in the case of d=4 the complexity of this decision problem is still unknown. In practice, however, there are heuristic algorithms that can recognize a given complex to be a sphere (easily) in many situations. We will outline the heuristics implemented in polymake and discuss its limitations as well as some topologically interesting observations that we encountered in our experiments.

Joint work with Michael Joswig and Frank H. Lutz.

Uli Wagner

"Eliminating Multiple Intersections and Tverberg Points"

Motivated by topological Tverberg-type problems and by classical results aboutembeddings (maps without double points), we study conditions under which a finite simplicial complex K can be mapped into d-dimensional Euclidean space without r-fold points (image points with at least r distinct preimages), for a given multiplicity r≥3. In particular, we are interested in maps that have no r-Tverberg points, i.e., no r-fold points with premiages in r pairwise disjoint simplices, and we seek necessary and sufficient conditions for the existence of such maps.

We present higher-multiplicity analogues of several classical results on embeddings, in particular the Whitney trick, the  Van Kampen-Shapiro-Wu Theorem and, more generally, the Haefliger-Weber Theorem, which guarantee that under suitable codimension restrictions, a well-known deleted product criterion is not only necessary but also sufficient for the existence of maps without r-Tverberg points. More specifically, if dim K=m and d ≥(k+3)(r+1)/m , then K admits a map into d-space without r-Tverberg point if and only if the r-fold deleted product of K admits an equivariant map into a sphere of dimension d(r-1)-1 (with respect to a suitable action of the symmetric group).

Özaydin showed that if r is not a prime power then the equivariant map in question exists in many interesting cases, including the case that K is the N-simplex,N=(d+1)(r-1). Inspired by this, an important motivation for our work was that sufficiency of the deleted product criterion might thus yield an approach to constructing counterexamples to the topological Tverberg conjecture for these values of r. Unfortunately, our results are not directly applicable to the N-simplex, because of the codimension restrictions they require.

In a recent breakthrough, Frick found an extremely elegant way of sidestepping this difficulty, by using the constraint method of Blagojevic-Frick-Ziegler to reduce the construction of counterexamples to a suitable lower-dimensional skeleton, for which the required codimension retrictions are satisfied and both Özaydin’s and our results apply.

This is joint work with Isaac Mabillard.