Pawel Pralat "Semi-random process"
Pawel Pralat from Ryerson University will give the talk "Semi-random process" on the labs' Big Seminar.
Password: first 6 decimal places of $\pi$ after the decimal point
You can also write to Alexander Polyanskii (alexander.polyanskii@yandex.ru) or to Maksim Zhukovskii (zhukmax@gmail.com) if you want to be added to mailing list.
Abstract:
The semi-random graph process is a single-player game that begins with an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible.
During the talk, we will focus on the following problems: a) perfect matchings, b) Hamilton cycles, c) constructing a subgraph isomorphic to an arbitrary fixed graph G. We will also consider a natural generalization of the process to s-uniform hypergraphs.
Watch the video:
Everyone is invited to attend. The language of the lecture is English. The event is aimed at master and graduate students, as well as researchers in the field of combinatorics.