Lecturers
 Karim Adiprasito (Hebrew University of Jerusalem & University of Leipzig)
 Imre Bárány (Hungarian Academy of Sciences & University College London)
 Alexander Barvinok (University of Michigan)
 Vida Dujmović (University of Ottawa)
 Fabrizio Frati (Università Roma Tre)
 Adam Sheffer (California Institute of Technology)
 Csaba D. Tóth (California State University Northridge)
Description
This activity will consist of 12 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: Vectorsum 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 V⊂B is finite and the sum of the elements in V is zero. Then there is an ordering v_{1},…,v_{n} 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 minorclosed 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 closelyrelated 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 kplanar 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 longstanding bound. These applications include, track layouts, queue layouts, stack layouts, nonrepetitive graph colourings and 3dimensional 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 topologicallyequivalent 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, nonplanar representations, and threedimensional 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 straightline 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


Vectorsum theorems, their relatives and applications
Imre Bárány


Coffee break


Layered separators/treewidth and their applications
Vida Dujmović


Lunch


Working & interacting
Tuesday, May 15


Morphing geometric representations of graphs
Fabrizio Frati


Coffee break


Working & interacting


Lunch


Working & interacting


Dinner at restaurant La Camarga
Wednesday, May 16


The toric toolkit
Karim Adiprasito


Coffee break


Transition Operations over Plane Graphs
Csaba Tóth


Lunch


Working & interacting
Thursday, May 17


Using Additive Combinatorics in Combinatorial Geometry
Adam Sheffer


Coffee break


Working & interacting


Lunch


Working & interacting
Friday, May 18


Computational complexity and complex geometry
Alexander Barvinok


Coffee break


Working & interacting


Lunch


Working & interacting
Note: Afternoon seminars will be announced inplace.