Pawel Pralat "Semi-random process" | Big Seminar
VoteIt 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 - http://combgeo.org/en/events/big-seminar.
About Combgeo Lab
We are the Laboratory of Combinatorial and Geometric Structures at MIPT. The lab aims to initiate collaboration and exchange between researchers who work on different topics in the fields of Combinatorics, Discrete and Computational Geometry, and Theoretical Сomputer Science.
0 Comments