"Eigenvalue bounds for sets avoiding norm 1 in ℝd"
How large can be a subset A of ℝd such that |x-y| ≠1 for all x,y∈A? We will discuss the links between this question and classical problems in geometry, then present a bound for the density of such sets that resembles eigenvalue bounds for the independence number of a graph, then discuss sharpness and computational issues regarding this bound. This is based on joint work with Evan Decorte, Fernando Mario de Oliveira Filho, Didier Henrion, Sinai Robins, Frank Vallentin.
Keith Ball:
"Noise sensitivity and Gaussian surface area"
The sensitivity to noise of Boolean functions is a problem that has attracted a fair amount of attention from theoretical computer scientists. This talk will describe the problems and their Gaussian analogues which serve as a model for what one expects in the Boolean case.
Alexander Barvinok:
"The symmetric moment curve and centrally symmetric polytopes with many faces"
I plan to review what is known about the facial structure of the convex hull of the symmetric moment curve t --> (cos t, sin t, cos 3t, sin 3t, ..., cos(2k-1)t, sin(2k-1)t) and how to use the curve to construct centrally symmetric polytopes with many faces.
The talk is based on a joint work with Isabella Novik and Seung Jin Lee.
Ivan Izmestiev:
"Shapes of euclidean polyhedra and hyperbolic geometry"
Inspired by the previous works of Thurston and Bavard and Ghys, we equip the space of convex polytopes with given facet normals with a natural piecewise hyperbolic metric. In dimension 3, the metric comes from the surface area of the polytope, which turns out to be a quadratic form of exactly the right signature. In higher dimensions, the quadratic form comes from the so called second intrinsic volume, and its signature is ensured by the Alexandrov-Fenchel inequalities. In general, the set of facet normals doesn't determine the combinatorics of the polytope, thus on different "type cones" of the space of shapes the quadratic forms are different. Thus the whole space of shapes becomes a polyhedral complex glued from hyperbolic polytopes. Combinatorially this complex is dual to a subset of the boundary of the secondary polyhedron of the set of facet normals.
Based on a joint work with Francois Fillastre.
Wolfgang Mulzer:
"Planar Delaunay Triangulations and Proximity Structures"
Let P be a planar point set. A proximity structure on P encodes useful information about the interpoint distances in P. Prominent examples are nearest-neighbor graphs, well-separated pair decompositions, quadtrees, Gabriel graphs, and, of course, Delaunay triangulations.
It is well known that these structures are intimately related; e.g., the nearest-neighbor graph is a subgraph of the Delaunay triangulation, quadtrees are used to construct well-separated pair decompositions; etc. I will survey several of these results, and I will present some new ones. Most notably,I will show that quadtrees and Delaunay triangulations are linear time equivalent: given one structure, one can find the other in deterministic linear time on a pointer machine.
This equivalence leads to several new algorithmic results, such as deterministic splitting of planar Delaunay triangulations, preprocessing imprecise points for faster Delaunay computation, and transdichotomous algorithms for planar Delaunay triangulations that run in the sorting bound.
Based on joint work with Kevin Buchin and Maarten Löffler.
Eran Nevo:
"Balanced rigidity"
We start developing a bipartite rigidity theory for bipartite graphs, parallel to the classical rigidity theory for general graphs. Specifically, we establish bipartite analogues of the cone, contraction, deletion and gluing lemmas. We apply this theory to prove a criterion for planarity of bipartite graphs, discuss a potential application to Jockusch's cubical lower bound conjecture,and relate to Laman type results by Whiteley. Extension to higher dimensional balanced complexes will be discussed as well, in particular a balanced analogue of the g-conjecture and Heawood type inequalities.
Reflects joint work with Gil Kalai and Isabella Novik
Jürgen Richter-Gebert:
"What is a Point?"
It is a well known fact that certain collections of algebraic curves share similar incidence properties as collections of lines in the projective plane. For instance if one considers the set of all circles that pass through a fixed point P these circles behave very similar to ordinary lines. In this case two points different from P determine exactly one such circle, two such circles in general have one additional point besides P in common and even incidence theorems like Pappus's or Desargues' Theorem hold. This talk deals with the general phenomenon behind this effect. It turns out that if one considers the elements of a linear pencil of algebraic curves as "lines" then the role of "points" is played by equivalence classes of ordinary points of the projective plane. The talk shows how this concept has interesting relations to concepts like circle inversion, the double covering of the projective plane by a sphere, the Cayley Bacharach theorem for cubics and many more. It also opens an interesting way to generalize the concept of circle inversion to some other algebraic curves that play the role of reflection lines.
Francisco Santos:
"The number of facets of three-dimensional Dirichlet stereohedra"
A stereohedron is a polytope that tiles Euclidean space by the action of a discrete group of isometries, necessarily a crystallographic group. Delone (1961) showed that a stereohedron of dimension d for a group with a translational cosets (so-called "aspects") cannot have more than 2d(a+1)-2 facets. In dimension three Delone's bound allows up to 390 facets, for groups having as aspects all the 48 symmetries of a regular cube. In contrast, the stereohedron with the maximum number of facets known (found by Engel, 1981) has only 38 facets.
In this talk I will report on joint work with D. Bochis (2001, 2006) and P. Sabariego (2008, 2011) in which we show that Dirichlet stereohedra cannot have more than 92 facets. Here, a Dirichlet (or Voronoi) stereohedron is the Voronoi region in an orbit of points under the action of a crystallographic group. Our bound uses the classification of three-dimensional crystallographic groups and combines general principles with some case-by-case study.
Achill Schürmann:
"Delaunay Tessellations of Point Lattices -- Theory, Algorithms and Applications"
In this talk we review Voronois classical reduction theory for positive definite quadratic forms that is based on Delaunay tessellations of point lattices. We consider practical algorithmic questions, in particular for the special case of an additional involved symmetry group G. We describe a G-invariant generalization Voronoi's theory and report on some applications.
Louis Theran
"Combinatorial rigidity with symmetry"
Bar-joint frameworks are structures made of fixed-length bars connected by universal joints with full rotational freedom. The allowed motions preserve the length and connectivity of the bars, and a framework is rigid if all the allowed motions extend to rigid body motions. For finite frameworks with generic geometry, rigidity is known to depend only on the graph that has as its edges the bars, and, in dimension 2, the generically rigid graphs are known exactly. In recent years, the question of extending this kind of combinatorial theory to infinite frameworks or finite frameworks with special geometry such as symmetry has received a lot of attention, motivated, in part, by applications in crystallography.
I will review some combinatorial characterizations of rigidity for 2-dimensional "crystallographic" bar-joint frameworks which are infinite, symmetric with respect to a crystallographic group Γ, and constrained to move in a way that preserves Γ-symmetry. Then I will discuss a new, finite algebraic characterization of so-called "ultrarigid" frameworks that are symmetric with respect to a full-rank translation lattice Λ, but allowed to move symmetrically with respect to any finite-index sub-lattice Λ' < Λ.
This is joint work with Justin Malestein.
Frank Vallentin:
"Computing upper bounds for densest packings with congruent copies of a convex body (Part 2)"
At the last ERC workshop "High-Complexity Discrete Geometry" two years ago I discussed a theorem and some computational strategies that can be used to find upper bounds for the maximum density of a packing of congruent copies of any given convex body. There I also promised that numerical results will come soon. In this talk I will present some of the numerical results and some extensions of the theory we obtained so far.
