Pawel Pralat “Semi-random process“ | Big Seminar

It is our pleasure to share the Big Seminar talk “Semi-random process“ by Pawel Pralat. 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. Seminars schedule and archive are available here -