Seminar
Parent Program:  

Location:  SLMath: Eisenbud Auditorium, Online/Virtual 
On the Price of Anarchy of the Probabilistic Serial Mechanism
SemiRandom Process
"SemiRandom Process"  Pawel Pralat
Abstract: The semirandom graph process is a singleplayer 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 constructing perfect matchings but Hamilton cycles and constructing a subgraph isomorphic to an arbitrary fixed graph G will be briefly discussed. We will also consider a natural generalization of the process to suniform hypergraphs.
"On the Price of Anarchy of the Probabilistic Serial Mechanism"  Adrian Vetta
"SemiRandom Process"
