UVictoria Dynamics and Probability Seminar: Peleg Michaeli

We introduce a model of a controlled random process. In this model, the vertices of a hypergraph are ordered randomly and then revealed, one by one, to an algorithm. The algorithm must decide, immediately and irrevocably, whether to keep each observed vertex. Given the total number of observed vertices ("time"), the algorithm's goal is to succeed - asymptotically almost surely - in completing a hyperedge by keeping ("purchasing") the smallest possible number of vertices.

We analyse this model in the context of random graph processes, where the corresponding hypergraph defines a natural graph property, such as minimum degree, connectivity, Hamiltonicity and the containment of fixed-size subgraphs.

Joint work with Alan Frieze and Michael Krivelevich.