Mini-course by Gábor Tardos “Extremal theory of vertex- and edge-ordered graphs”

November 26-28, 2019
Dolgoprudny
MIPT

Mini-course by Gábor Tardos "Extremal theory of vertex- and edge-ordered graphs"

At the invitation of the Laboratory of Combinatorial and Geometric Structures and the PhysTech School of Applied Mathematics and Computer Science, Gábor Tardos will visit the Moscow Institute of Physics and Technology. He will give 3 lectures. Two of them will be part of the "Combinatorics and Geometry Days I" conference on November 26-27. On November 28 there will be the final lecture of the course from 17.00 to 18.00. All the lectures will take place in the lecture auditorium on the 4th floor of the Arctic building.

November 26 16.00 - 17.00 Room: Lecture Hall 4th floor Arctica
November 27 16.00 - 17.00 Room: Lecture Hall 4th floor Arctica
November 28 17.00 - 18.00 Room: Lecture Hall 4th floor Arctica

"The basic question of Turan type extremal graph theory is the maximum number of edges in a simple graph on n vertices that does not contain a specified "forbidden" subgraph (or any one of several forbidden subgraphs). This is a classical topic of combinatorics with many deep results and lot of questions that are still open.

In my survey talk I will focus on extensions of this theory to simple graphs with an additional structure, namely a linear order on the set of vertices or edges. A single simple graph has several vertex order and by forbidding just one of them we obtain different extremal questions. Introducing either a vertex- or an edge-order makes the theory richer and more suitable to (mostly geometric) applications.

I will highlight several specific open problems about both vertex- and edge-ordered graphs. I will mention results from numerous researchers, among them Balazs Keszegh, Daniel Korandi, Jesse Geneson, Daniel Gerbner, Adam Marcus, Abhishek Methuku, Daniel Nagy, Janos Pach, Seth Pettie, Domotor Palvolgyi, Istvan Tomon, Mate Vizer, Creig Weidert, etc."

Everyone is invited to attend the lecture course. The language of the lectures is English. The course is aimed at master and graduate students, as well as researchers in the field of combinatorics.