Virtual Seminar Series - Warwick Combinatorics

This is the webpage for the Warwick Combinatorics Seminar Series

The seminars occur weekly on a Wednesday at 2 pm (BST)

To participate in the seminars please use this Zoom link

https://us02web.zoom.us/j/83096898964?pwd=OXIySVh3M1l0K0tTR3VobkRhcmRTZz09

 

Future Seminars

Wednesday 27th May – 14:00 (BST)

Peleg Michaeli (Tel Aviv)

Title: Greedy maximal independent sets via local limits

Abstract: The random greedy algorithm for finding a maximal independent set in a graph has been studied extensively in various settings in combinatorics, probability, computer science — and even in chemistry. The algorithm builds a maximal independent set by inspecting the vertices of the graph one at a time according to a random order, adding the current vertex to the independent set if it is not connected to any previously added vertex by an edge. In this talk I will present a natural and general framework for calculating the asymptotics of the proportion of the yielded independent set for sequences of (possibly random) graphs, involving a useful notion of local convergence. We use this framework both to give short and simple proofs for results on previously studied families of graphs, such as paths and binomial random graphs, and to give new results for other models such as random trees. If time allows, I will discuss a more delicate result, according to which in expectation, the cardinality of a random greedy independent set in the path is no larger than that in any other tree of the same order. The talk is based on a joint work with Michael Krivelevich, Tamás Mészáros and Clara Shikhelman.

 

Wednesday 3rd June – 14:00 (BST)

Yifan Jing (UIUC)

 

Wednesday 10th June – 14:00 (BST)

Yahav Alon (Tel Aviv)

Title: Hitting time of disjoint Hamilton cycles in random subgraph processes

Abstract: Consider a random graph process, in which edges are added to an empty graph consecutively in a uniformly chosen random order. A classical result by Bollobás and Frieze state that at the first moment the graph no longer contains vertices of degree less than 2k, it also typically contains k edge disjoint Hamilton cycles.We extend this result to random subgraph processes, in which only edges of a given base graph are added, for certain families of dense base graphs.

Based on a joint work with Michael Krivelevich.

 

Wednesday 17th June – 14:00 (BST)

Andrzej Grzesik (Jagiellonian)

 

Wednesday 24th June – 14:00 (BST)

Bjarne Schülke (Hamburg)

Title: Extremal problems concerning the traces of sets


Previous Seminars

 

19th April, 2020

Robert Simon (LSE)

Title: Paradoxical Colouring Rules

 

6th May, 2020

Thomas Johnston (Oxford)

Title: Lipschitz bijections between boolean functions

 

13th May, 2020

Sergey Norin (McGill University)

Title:Breaking the degeneracy barrier for coloring graphs with no KtKt minor

 

20th May, 2020

Olof Sisask (Stockholm)

 

This seminar series is supported as part of the ICMS/INI Online Mathematical Sciences Seminars.