Subgraphs in Semi-random Graphs (and Hypergraphs)

Add to your list(s) Download to your calendar using vCal

• Natalie Behague, University of Victoria
• Thursday 28 April 2022, 16:00-17:00
• Via Zoom, but Poynting Large Lecture Theatre is also booked. Zoom link: https://bham-ac-uk.zoom.us/j/88168768618.

If you have a question about this talk, please contact Eoin Long.

The semi-random graph process can be thought of as a one player game. Starting with an empty graph on n vertices, in each round a random vertex u is presented to the player, who chooses a vertex v and adds the edge uv to the graph. Given a graph property, the objective of the player is to force the graph to satisfy this property in as few rounds as possible. We will consider the property of constructing a fixed graph G as a subgraph of the semi-random graph. Ben-Eliezer, Gishboliner, Hefetz and Krivelevich proved that the player can asymptotically almost surely construct G given n^{1 – 1/d}w rounds, where w is any function tending to infinity with n and d is the degeneracy of the graph G. We have proved a matching lower bound. I will talk about this result, and also discuss a generalisation of our approach to semi-random hypergraphs. I will finish with some open questions.

This is joint work with Trent Marbach, Pawel Pralat and Andrzej Rucinski.

This talk is part of the Combinatorics and Probability seminar series.

This talk is included in these lists:

• Combinatorics and Probability seminar
• School of Mathematics events
• Via Zoom, but Poynting Large Lecture Theatre is also booked. Zoom link: https://bham-ac-uk.zoom.us/j/88168768618

Note that ex-directory lists are not shown.