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.

There will be a dinner at a Gusto Italian restaurant 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.

Funding for Students

We have some limited funding for students. If you are a UK based PhD student with little funding and wish to attend then please email the organisers outlining your funding situation and we may be able to help, however this is on a first-come first-served basis.

We urge all students to keep receipts for expenses as, additionally, we may be able to refund some expenses after the conference.

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 - Frame matroids with a distinguished frame element

A matroid is frame if it may be extended such that it possesses a basis $B$ (a frame) such that every element is spanned by at most two elements of $B$. Frame matroids extend the class of graphic matroids and also have natural graphical representations. We characterise the inequivalent graphical representations of $3$-connected frame matroids that have a fixed element $\ell$ in their frame $B$. One consequence is a polynomial time recognition algorithm for frame matroids with a distinguished frame element.

Joint work with Jim Geelen and Cynthia Rodríquez.

Natasha Blitvic - Probabilistic Aspects of Permutation Patterns

Permutation patterns form an intriguing class of combinatorial problems, being very simple to formulate, outstandingly difficult (outside of a handful of special cases) to solve, and seemingly lacking unifying structure that is not pattern-dependent. I will discuss several recent approaches to permutation patterns that propose and seek to exploit different types of interplay between probability and combinatorics. We will find this to be a rich interface, leading to surprising new facts and many open problems.

The talk is partly based on ongoing joint works with Slim Kammoun and Einar Steingrimsson.

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.

John Haslegrave - Two-type annihilation and other reactions on graphs

Suppose equal numbers of two types of particles move randomly on a finite graph, perhaps at different speeds, with collisions between opposite types resulting in annihilation. How many movements will it take for all particles to be eliminated? This model, introduced by Cristali et al., is surprisingly difficult to analyse, with even the case of the complete graph being previously unknown.

We obtain exact asymptotics for the complete graph and up-to-constant bounds for exapander graphs. In the latter case, upper and lower bounds are both non-trivial and use different techniques. I shall discuss how the methods apply to a general class of dissipative particle system, but the specific setup described above creates additional difficulties.

This is joint work with Peter Keevash (Oxford).

Barkla Lecture

This is a one hour lecture given by the renowned theoretical physicist Ignacio Cirac. The lecture is organised by the Mathematics department and is taking place in the Rotblat Lecture Theatre of the Chadwick Building.

We stress that this lecture not formally associated with the LDMC, however we advertise it here as it may be of interest. If you are interested in attending this lecture you must register: Further details & registration here.

Organisers

John Sylvester

Linglong Yuan

Viktor Zamaraev

Supported by