Mary Cryan (University of Edinburgh)
Euler-tours of low-height toroidal grids
The problem of exactly counting the Euler tours (ETs) of an (undirected) 4-regular graph is known to be #P-complete, and to date no fpras exists for approximate counting. The natural “Kotzig moves” Markov chain converges to the uniform distribution on Euler tours of the given graph, but attempts to show rapid mixing (even for restricted classes of graphs) have been unsuccessful.
For the specific case of a toroidal grid with a constant number of rows k, a transfer matrix” can be defined and used to exactly count Euler tours of that grid. We show that we can use some of that same structure to prove rapid mixing of the Kotzig moves chain on 2-rowed toroidal grids, and discuss the issues for higher number of rows.
(Joint work with Sophia Jones. I will touch on the details of the transfer matrix method for ETs, which was joint with Creed, Astefanoaei, and Marinov).
Felix Fischer (Queen Mary University of London)
Optimal Impartial Selection
I will look at selection rules that map any directed graph (without loops) to a subset of its vertices. A selection rule
is impartial if the selection of a vertex is independent of its outgoing edges, and an optimal impartial rule is one that
in any graph selects vertices with large indegrees. The idea is that vertices and edges represent individuals and
nominations among individuals, and that we want to select highly nominated individuals without individuals having an
influence on their own selection. I will discuss what is know about impartial selection and point to some open problems.
The talk is based on joint work with Noga Alon, Antje Bjelde, Javier Cembrano, David Hannon, Max Klimm, Ariel Procaccia,
and Moshe Tennenholtz.
Nora Frankl (The Open University)
Monochromatic infinite sets in Minkowski spaces
By a result of Erdős, Graham, Montgomery, Rothschild, Spencer, and Straus it is possible to colour the points of the d-dimensional Euclidean space with two colours such that there is no monochromatic isometric copy of a given infinite set.
We prove several related results in other normed spaces. We show that the same is true in 2-dimensional l_p spaces.
We also prove that if the unit ball of a normed plane is a polygon, then two colours are not enough.
Further, we also show an example of an infinite set for which we need to colour with an arbitrarily large number of colours to avoid its monochromatic isometric copies in a space with the max norm of sufficiently large dimension.
Joint work with Panna Gehér, Andrey Kupavskii, Arsenii Sagdeev and Géza Tóth.
Sergey Kitaev (University of Strathclyde)
Singleton mesh patterns in multidimensional permutations
Permutation patterns is a popular area of research introduced in 1968, but with roots going to the work of Leonhard Euler in 1749.
In this talk, I will present a brand-new notion of a singleton mesh pattern (SMP), which is a multidimensional mesh pattern of length 1. It turns out that avoidance of this pattern in arbitrary large multi-dimensional permutations can be characterised using an invariant of a pattern called its rank. This allows to determine avoidability for an SMP P efficiently, even though determining rank of P is an NP-complete problem. Moreover, using the notion of a minus-antipodal pattern, one can characterise SMPs which occur at most once in any d-dimensional permutation.
I will also discuss a number of enumerative results regarding the distributions of certain general projective, plus-antipodal, minus-antipodal and hyperplane SMPs.
This is joint work with Sergey Avgustinovich, Jeffrey Liese, Vladimir Potapov and Anna Taranenko.
Kitty Meeks (University of Glasgow)
The search for useful temporal graph parameters
A highly successful approach for tackling NP-hard problems on graphs is the paradigm of parameterised complexity: the running time of algorithms is analysed in terms of a secondary measure, or parameter, in addition to the total input size, and the goal is to restrict the combinatorial explosion to the parameter (which is hopefully, in instances of interest, much smaller than the total input size). Many widely used parameters capture structural properties of the input graph, for example the edit distance to some class on which the problem is tractable, or the ease with which the graph can be decomposed according to specific rules. In recent years, there have been numerous attempts to apply the parameterised approach to algorithmic problems on temporal graphs, in which the edge-set changes over time. However, this has led to efficient parameterised algorithms in only a few cases: for many natural problems (including some that are polynomial-time solvable on static graphs) the additional complexity introduced by encoding temporal information in the graph renders the temporal versions intractable even when the underlying graph has very simple structure (e.g. when it is a tree or even a path). This motivates the search for new parameters, specifically designed for temporal graphs, which capture properties of the temporal information in addition to the structure of the underlying graph. In this talk I will survey recent progress in the development of such parameters and highlight a large number of remaining challenges; in the process I will describe joint work involving Benjamin Bumpus (U Florida), Jessica Enright (University of Glasgow), Laura Larios-Jones (University of Glasgow) and Samuel Hand (University of Glasgow).
Siaw-Lynn Ng (Royal Holloway University of London)
Some connections between finite geometry and applications in information security
Finite geometry and combinatorics has been very useful in modelling and benchmarking many problems arising from digital communications, information security and cryptography, by facilitating the study of the essential structures and their interactions. While using existing combinatorial objects to provide constructions and benchmarks for various applications has been productive, more in-depth consideration of whether the properties of these objects are strictly what is required in the applications can also yield interesting insights, and some applications can also provide inspirations and results in other areas.
I would like to talk about some structures in finite geometry arising from some applications in information security, with the aim that we might come to a better understanding of their properties and their relationships to existing structures, and that this might give us further avenues of research
John Sheekey (University College Dublin)
Finite semifields and their combinatorial applications
Finite semifields are non-associative division algebras. They have been studied since the early 1900s for a variety of reasons, including connections to finite geometry and combinatorics. A classical example of this is through their use in constructing projective planes, where one directly replaces the use of a field with a semifield. However they also lead to interesting geometric and combinatorial objects in more surprising ways. In this talk we will give an introduction to the topic, and highlight a few of these unconventional applications through some recent results.
Jason Smith (Nottingham Trent University)
Linear Extensions of Posets and an application to Neuroscience
Pairs of neurons that both send and receive information from each other are conjectured to play an important role in the reliability of the brain. The brain can be modelled as a directed graph, where neurons are vertices and edges are synapses, so such connections are bidirectional edges. Computations indicate that that these bidirectional edges occur more frequently within cliques in brain networks. However, bidirectional edges naturally create more cliques. So to understand whether this prevalence of bidirectional edges in cliques is expected or abnormal we must understand how many cliques we would expect from some given bidirectional edges. We show that this problem is equivalent to counting the number of linear extensions of a poset, and counting the number of permutations with a given inversions set. And we present some new formulas for the number of linear extensions for particular classes of posets using modular decomposition.