PCC and BCC Logos BCC Logo

Postgraduate Combinatorial Conference 2019


Click on a talk to see the abstract.




00:00 10:00 11:00 12:00 13:00 14:00 15:00 16:00 17:00 18:00 19:00 20:00
11:00 - 11:30 Registration

11:30 - 12:30 Partitioning the vertices of a torus into isomorphic subgraphs Natasha Morrison (University of Cambridge and IMPA)

Let $H$ be an induced subgraph of the torus $C_k^n$. We discuss results concerning when the vertices or edges of $C_k^n$ can be decomposed into induced copies of $H$. In particular, we disprove a conjecture of Gruslys, showing that when k is odd and not a prime power, then there exists $H$ such that $|V(H)|$ divides some power of $k$, but there is no n such that the vertices of $C_k^n$ can be decomposed into copies of $H$. We also disprove a conjecture of Gruslys, Leader and Tan on edge decomposing $C_k^n$. Joint work with Marthe Bonamy and Alex Scott.

12:30 - 13:30 Lunch

13:30 - 14:00 Distinct distances in finite fields Sophie Stevens (University of Bristol)

The Erdős distance problem is to find a bound on the minimum number of distinct distances that a point set can determine in the real plane. This was resolved (up to a logarithmic factor and to much acclaim) by Guth and Katz over the real plane. One can also ask this question over other fields, in particular finite fields. Here, not all of the techniques used by Guth and Katz are applicable. Indeed, we do ask this question: in joint work with Brendan Murphy, we show how to employ incidence bounds to obtain a new result on the Erdős distance problem over $\mathbb{F}_p$.

14:00 - 14:30 Sums of linear transformations in higher dimensions Akshat Mudgal (University of Bristol)

Given a finite subset $A$ of integers and co-prime natural numbers $q,s$, we consider the set $q\cdot A + s\cdot A$, that is, the sum of dilates of $A$. In recent years, finding suitable lower bounds for the cardinality of such sets in terms of $|A|, q$ and $s$ has seen considerable activity. In 2014, Balog and Shakan found sharp estimates for the same, that were tight in both the main term as well as the error term. Subsequently, they considered this problem in higher dimensional integer lattices. In this talk, we present a short survey of these results including our own improvement in the higher dimensional setting.

14:30 - 15:00 A combinatorial approach to triangulations of products of simplices Ben Smith (QMUL)

Products of simplices are important polytopes that have multiple applications to game theory, optimisation and algebraic geometry. Moreover, their structure and subdivisions lay the groundwork for the theory of products of more general polytopes, and so a great deal of study has gone into them. A beautiful fact is that their subdivisions may be encoded via a set of bipartite graphs satisfying certain compatibility conditions, and so we can remove all geometry and work strictly in the realm of combinatorics. In this talk we shall demonstrate how this graphical characterisation is possible. Furthermore, we shall consider a secondary description in terms of pairs of compositions, and as a corollary derive the first bounds on the number of triangulations of a product of simplices. This is joint work with Georg Loho.

15:00 - 15:15 Break

15:15 - 15:45 Burn, baby, burn: Mathematical firefighting to control disease spread Cat Wedderburn (University of Edinburgh)

The Firefighter game offers a simple, discrete time model for the spread of a perfectly infectious disease and the effect of vaccination. A fire breaks out on a graph at time $0$ on a set $F$ of $f$ vertices. At most $d$ non-burning vertices are then defended and can not burn in future. Vertices, once either burning or defended remain so for the rest of the game. At each subsequent time step, the fire spreads deterministically to all neighbouring undefended vertices and then at most $d$ more vertices can be defended. The game ends when the fire can spread no further. Determining whether $k$ vertices can be saved is NP-complete. I focus on finding maximal minimal damage (mmd) graphs - graphs which have the least burning if the fire starts in the worst place and the defenders defend optimally. I shall present some new and old results linking mmd graphs to optimal graphs for the Resistance Network Problem of finding graphs where all $F$-sets of vertices have limited neighbourhoods.

15:45 - 16:15 Resilience of random graphs with respect to Hamiltonicity Alberto Espuny Díaz (University of Birmingham)

The local resilience of a graph $G$ with respect to a property $\mathcal{P}$ measures how much one has to change $G$ locally in order to destroy $\mathcal{P}$. We prove 'resilience' versions of several classical results for the graph models $G_{n,p}$ and $G_{n,d}$.
For example, we prove a resilience version of Dirac's theorem in the setting of random regular graphs. More precisely, we show that, whenever $d$ is sufficiently large compared to $\varepsilon>0$, a.a.s. the following holds: any subgraph of the random $n$-vertex $d$-regular graph $G_{n,d}$ with minimum degree at least $(1/2+\varepsilon)d$ is Hamiltonian. This proves a conjecture of Ben-Shimon, Krivelevich and Sudakov.
We also prove a resilience version of Pósa’s Hamiltonicity condition for the binomial random graph $G_{n,p}$ and show that a natural guess for a resilient version of Chvátal’s theorem for $G_{n,p}$ fails to be true.
This is joint work with Padraig Condon, António Girão, Jaehoon Kim, Daniela Kühn and Deryk Osthus.

16:15 - 16:45 An Online Graph Atlas Srinibas Swain (Monash University)

In this talk we introduce a new research tool, an online interactive repository of graphs called the Online Graph Atlas (OLGA). The repository is designed to enable efficient retrieval of information about graphs and to enable queries based on combinations of standard graph parameters. Parameters include chromatic number, chromatic index, domination number, independence number, clique number, matching number, vertex cover number, size of automorphism group, vertex connectivity, edge connectivity, eigenvalues, treewidth, and genus.
Inspired by Read and Wilson's book, An Atlas of Graphs (OUP, 1998), Barnes, Bonnington and Farr developed the first prototype of OLGA in 2009, which was extended by Sio, Farr and Bonnington in 2010 by adding more parameters. We change its design to make it more flexible and extendable. We also introduce new parameters such as chromatic index, chromatic number, degeneracy, eigenvalues, size of automorphism group, treewidth and Tutte polynomial. OLGA now stores over 20 standard parameters for each graph of up to 10 vertices. We used recursive algorithms and exact algorithms for parameter computation. OLGA is not limited to the role of a search engine for graphs. We demonstrate how to use OLGA as a tool to explore conjectures and theorems involving the parameters.
This is joint work with Graham Farr, Paul Bonnington, and Kerri Morgan.