Liverpool Discrete Mathematics Colloquium

About

This two day Colloquium aims to bring together researchers in discrete mathematics, from structural and algorithmic graph theory to probabilistic and extremal combinatorics.

For the benefit of junior researchers, there is a tutorial given by Maksim Zhukovskii on Thresholds in random graphs, and a session with contributed one slide pitches by junior researchers.

Venue

All talks will be held in the Elizabeth Gidney Room which is on the Second floor of the Liverpool Guild of Students, 160 Mount Pleasant, Liverpool, L3 5TR

The venue is wheelchair accessable, and a 15 minute walk from Liverpool Lime street (main train station).

Catering

There are tea/coffee breaks provided. Lunches are not provided, however there is the University of Liverpool refectory and plenty of local cafes and restaurants nearby (more details to follow).

There will be a dinner at a local restaurant (tbc) on the evening of the first day. All participants are welcome to attend, however participants will have to cover the cost of their own meal.

Registration

Attendance at the Liverpool Discrete Mathematics Colloquium is free of charge. However, registration is required (deadline 1st Novemeber 2024) to help us with logisics, and to ensure adequate arrangements for the coffee/tea breaks.

Click here for Registration Form

Speakers

Natalie Behague (Warwick)

Natasha Blitvic (Queen Mary)

James Davies (Cambridge)

Sergey Foss (Heriot Watt)

John Haslegrave (Lancaster)

Sandra Kiefer (Oxford)

Laura Larios-Jones (Glasgow)

Vadim Lozin (Warwick)

Maksim Zhukovskii (Sheffield)

Schedule

Abstracts

Maksim Zhukovskii - Thresholds in random graphs

Nearly 40 years ago, Bollobás and Thomason demonstrated that every non-trivial monotone property of subsets has a threshold probability. Since then, various techniques have been developed to determine the exact threshold values for monotone properties in random graphs. The recently resolved Kahn-Kalai conjecture asserts that, up to a logarithmic factor, thresholds can be easily estimated by calculating the expectation. In this tutorial, we will discuss several techniques for finding thresholds, with a particular focus on the key components of the proof of the Kahn-Kalai conjecture.

Sandra Kiefer - Combinatorial Approaches to the Graph isomorphism Problem

The graph isomorphism problem is one of the most fundamental computational problems whose complexity is still open. All competitive approaches to it make use of the Weisfeiler—Leman algorithm, which works by computing, counting, and comparing colour occurrences in the graphs.

The algorithm has links to numerous other areas. For example, via its connection to logics and games, we can draw conclusions about the descriptive complexity of the input graph and we can find canonical decompositions of the structures at hand. Still, after decades of research and with all the cross-links that have been found, we lack a precise understanding of the expressiveness of the algorithm.

In my talk, I will shed light on the power of the algorithm to detect graph structure. I will analyse its central parameters, the dimension and the number of iterations, in the context of logics and games and illustrate how this connection yields new proof techniques.

Laura Larios-Jones - Structural Parameters for Dense Temporal Graphs

A temporal graph consists of a static graph $G$ and a function that dictates when the edges are active. This allows us to model networks where the time at which connections occur is important. Unfortunately, many temporal problems are more computationally complex than their static counterparts. We look for temporal parameters such that, when these are small for the input of a temporal problem, we can efficiently solve the problem at hand. Many temporal parameters currently in use rely on some notion of sparsity in either the graph or function. We introduce three parameters that are small for dense and highly structured temporal graphs. These parameters are temporal cliquewidth, temporal modular-width, and temporal neighbourhood diversity. We also give examples of temporal problems which are tractable with respect to these parameters.

Vadim Lozin - Graph problems and monotone classes

We study properties of graph classes that are closed under taking subclasses, such as boundedness of graph parameters or polynomial-time solvability of algorithmic problems. In the universe of minor-closed classes of graphs, any such property can be described by a set of minimal classes that do not possess the property, because the minor relation is a well-quasi-order. This, however, is not the case for the subgraph relation, implying that in the universe of monotone classes, which extends the family of minor-closed classes, the existence of minimal classes is not guaranteed. To overcome this difficulty, we employ the notion of boundary classes. Together with minimal classes they play a critical role for classes defined by finitely many forbidden subgraphs. In this talk, we identify several levels in the hierarchy of monotone classes and describe respective critical classes.

James Davies - Colourings of the plane

We discuss recent progress in Euclidean Ramsey theory on determining which monochromatic distances appear or do not appear in finite colourings of the plane.

Includes joint work with Rose McCarty and Michał Pilipczuk, and with Rutger Campbell.

Sergey Foss - Barak-Erdos directed random graphs and related models

In the talk, I will introduce Barak-Erdos graphs and infinite-bin models, and discuss their limit properties, as well as convergence rates and `perfect' simulation of their characteristics. The talk will be mainly based on papers written jointly with Prof Takis Konstantopoulos (U of Liverpool), but contain a few new results, too.

Natalie Behague - Ramsey multiplicity and Common pairs of graphs

Ramsey's theorem tells us that for any fixed graph $H$, in any red/blue edge colouring of a sufficiently large complete graph there is a monochromatic copy of $H$. The closely related Ramsey multiplicity problem asks instead what is the minimum number of monochromatic copies of H over all red/blue edge colourings?

A beautiful result of Goodman shows that the number of monochromatic copies of the triangle is minimised (asymptotically) by an unbiased random edge colouring. A graph is called `common' if it has this property, that an unbiased random edge colouring gives the minimum number of monochromatic copies (asymptotically), and the question of which graphs (other than the triangle) are `common' has been well studied. I will discuss this history and introduce a natural extension of this notion to an asymmetric setting, where we wish to minimize a linear combination of the number of red copies of $H_1$ and blue copies of $H_2$. I will briefly outline some of our new results in the asymmetric setting and finish with several open questions.

This is joint work with Natasha Morrison and Jonathan Noel.

Organisers

John Sylvester

Linglong Yuan

Viktor Zamaraev

Supported by