Lecturers

Description

This activity will consist of 1-2 lectures per day, focusing on open problems on different topics, in relation to the subjects of Advanced Course II. The remaining of the day, attendees will have plenty of time to work and interacting with each other.

Contents

Karim Adiprasito: Title: The toric toolkit
I will present algebraic tools borrowed from toric geometry, focused on applications towards extremal problems in geometric combinatorics. The presentation will not require any knowledge of algebraic geometry.

Imre Bárány: Vector-sum theorems, their relatives and applications
About hundred years ago, answering a question of Riemann, Steinitz proved the following result. Let B  be the unit ball of the Euclidean norm in R d and assume that VB  is finite and the sum of the elements in V  is zero. Then there is an ordering v1,…,vn  of the vectors in V  such that all partial sums along this ordering have norm smaller than 2d.  I am going to talk about extensions, generalizations, and applications of this remarkable theorem.

Alexander Barvinok: Computational complexity and complex geometry
I will discuss a general principle: if a combinatorially defined polynomial (such as the permanent of a matrix or the independence polynomial of a graph) has no zeros in a certain complex domain, then it can be efficiently computed (approximated) in a slightly smaller domain. On one hand, this leads to a number of efficient approximation algorithms in various problems of combinatorial counting and, on the other hand, to a number of deceptively simple looking problems of combinatorial geometry.

Vida Dujmović: Layered separators/treewidth and their applications
Graph separators are a ubiquitous tool in graph theory and computer science. However, in some applications, their usefulness is limited by the fact that the separator size depends on the size of the graph. This is the case for planar graphs, and more generally, for proper minor-closed families which can have Omega(sqrt n) separators in graphs with n vertices.
I will talk about a special type of graph separator, called a “layered separator” and the closely-related notion of layered treewidth. These separators may have linear size in n, but have bounded size with respect to a different measure, called width. Planar graphs, graphs of bounded Euler genus, and k-planar graphs admit layered separators of bounded width. I show how (with simple proofs) they can be used to obtain logarithmic bounds for a variety of applications for which O(sqrt n) was the best known long-standing bound. These applications include, track layouts, queue layouts, stack layouts, nonrepetitive graph colourings and 3-dimensional grid drawings of graphs.

Fabrizio Frati: Morphing geometric representations of graphs
In this talk I will survey the state of the art on morphing geometric representations of graphs. Suppose that one is given two topologically-equivalent geometric representations of a graph. Can one representation be continuously transformed into the other one while preserving the graph topology during the transformation? This question has been studied for more than a century and yet answering it completely is still an elusive goal. The study of morphs of graph representations has proved to be intertwined with several areas of mathematics and computer science. I will talk about some of the most natural versions of the above question, related to morphing planar representations, non-planar representations, and three-dimensional representations. I will present the main methodologies currently used in this field, as well as a large number of open problems at various levels of difficulty.

Adam Sheffer: Using Additive Combinatorics in Combinatorial Geometry
Additive Combinatorics is an active research field combining combinatorics, number theory, and harmonic analysis. In recent years, a variety of results in Combinatorial Geometry have been obtained by using ideas from Additive Combinatorics. For example, the concept of additive energy turned out to be very useful for several types of geometric problems. In this talk we will introduce basic concepts from Additive Combinatorics, and then show how these are used to derive geometric results. No prior knowledge of the subject is necessary. The talk will also go over related natural problems that were not seriously studied yet (since these problems originate from very recent works). Moreover, there are likely to be various additional Combinatorial Geometry problems that can be studied using similar tools from Additive Combinatorics. This makes this topic well suited for collaborations without requiring a large amount of background.

Csaba Tóth: Transition Operations over Plane Graphs
Let S  be a finite set of points in general position in the plane, and G(S)  a family of planar straight-line graphs with vertex set S  (such as noncrossing matching, spanning trees, spanning cycles, triangulations). Combinatorial properties of G(S) are often rely on operations (moves) that transform one graph in G(S) into another by replacing some edges; such as edge exchange, edge flip, edge rotation, and edge slide (either as elementary moves that modify a constant number of edges, or simultaneous operations that perform one or more elementary moves simultaneously). In a transition graph, the vertices represent the graphs in G(S), and adjacency represents a valid transformation. This talk will review recent results on the extremal properties of transition graphs and pose open problems.

Organization

There will be one or two lectures every morning, each 1h 45min long. After that, attendees and lecturers will work in open problems.

Program

Monday, May 14

  • -

    Registration

  • -

    Vector-sum theorems, their relatives and applications

    Imre Bárány Imre Bárány

  • -

    Coffee break

  • -

    Layered separators/treewidth and their applications

    Vida Dujmović Vida Dujmović

  • -

    Lunch

  • -

    Working & interacting

Tuesday, May 15

  • -

    Morphing geometric representations of graphs

    Fabrizio Frati Fabrizio Frati

  • -

    Coffee break

  • -

    Working & interacting

  • -

    Lunch

  • -

    Working & interacting

  • -

    Dinner at restaurant La Camarga

Wednesday, May 16

  • -

    The toric toolkit

    Karim Adiprasito Karim Adiprasito

  • -

    Coffee break

  • -

    Transition Operations over Plane Graphs

    Csaba Tóth Csaba Tóth

  • -

    Lunch

  • -

    Working & interacting

Thursday, May 17

  • -

    Using Additive Combinatorics in Combinatorial Geometry

    Adam Sheffer Adam Sheffer

  • -

    Coffee break

  • -

    Working & interacting

  • -

    Lunch

  • -

    Working & interacting

Friday, May 18

  • -

    Computational complexity and complex geometry

    Alexander Barvinok Alexander Barvinok

  • -

    Coffee break

  • -

    Working & interacting

  • -

    Lunch

  • -

    Working & interacting

Note: Afternoon seminars will be announced in-place.