University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Subgraphs in Semi-random Graphs (and Hypergraphs)

## 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. |
## Other listsPostgraduate Seminars in the School of Computer Science 'Roles' Postgraduate Gender and Sexuality Network Discussion Cargo## Other talksWave turbulence in the Schrödinger-Helmholtz equation Hunt for an Earth-twin Counting cycles in planar graphs Ultrafast Spectroscopy and Microscopy as probes of Energy Materials Life : it’s out there, but what and why ? The tragic destiny of Mileva Marić Einstein |