math_groups_discgeom

2nd ERC Workshop - Abstracts

Christine Bachoc:

"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.

I will not assume anything from Part 1, but in any case, the slides can be found here:  http://www.mi.fu-berlin.de/math/groups/discgeom/media/Slides/Slides/Vallentin.pdf

(based on joint work with David de Laat and Fernando de Oliveira Filho; http://arxiv.org/abs/1206.2608 and http://arxiv.org/abs/1308.4893)