There is an obvious productfree subset of the symmetric group of density 1/2, but what about the alternating group? An argument of Gowers shows that a productfree subset of the alternating group can have density at most n^(1/3), but we only know examples of density n^(1/2 + o(1)). We'll talk about why in fact n^(1/2 + o(1)) is the right answer, why Gowers's argument can't prove that, and how this all fits in with a more general 'product mixing' phenomenon. Our tools include some nonabelian Fourier analysis and a BrascampLiebtype inequality for the symmetric group due to Carlen, Lieb, and Loss.
Combinatorics Study Group
The Combinatorics Study Group normally meets at 2pm on Fridays in the Maths Seminar Room. Do check this page in advance of the meeting in case there are any changes.
The current seminar organisers are Felix Fischer, Mark Jerrum, and Viresh Patel.

DateRoomSpeakerTitle

02/10/2009 5:30 PMM103Diane Donovan (Queensland)The importance of latin trades in the study of completing partial latin squaresSeminar series:In this talk I will begin by discussing early problems concerning the comple tion of partial latin squares. By reviewing this early work I will highlight the importance of the study of latin trades. Given two latin squares L and M, of the same order, the differences between the squares give rise to a latin trade. That is, the partial latin squares L/M and M/L are said to form latin trades. Throughout this talk I will present a number of open problems in the study of latin squares and latin trades.

16/10/2009 5:30 PMM103John Talbot (UCL)Triangles in tripartite graphsSeminar series:Mantel's theorem (1907) says that a graph with n vertices and more than n^{2} /4 edges must contain a triangle. Over a century later Razborov gave a quantitative version of this result. He determined the minimal proportion of triangles present in a graph of given density. I will talk about the analogues of these results for tripartite graphs. This is joint work with Rahil Baber and Robert Johnson.

23/10/2009 5:30 PMM103Aidan RoyOptimal designs in complex projective space, 1

06/11/2009 4:30 PMM103Aidan RoyOptimal designs in complex projective space, 2

13/11/2009 4:30 PMM103Thomas PrellbergCounting areaweighted Dyckpaths in a slitSeminar series:

27/11/2009 4:30 PMM103Olof SisaskFourier analysis and approximate structure in additive combinatorics, 1Seminar series:Given a somewhat large subset A of F_{p}^{n}, an ndimensional vector space over A of F, must the sumset A+A+A contain a large subspace? Can we say anything interesting about A itself, based solely on its size? In this twopart talk I shall introduce Fourier analysis on finite abelian groups and show how this can be used to deal with questions such as these. This will involve a version of the notion of almostperiodicity, which we shall be able to translate into tangible combinatorial results. I plan to assume very few prerequisites.

04/12/2009 4:30 PMM103Olof SisaskFourier analysis and approximate structure in additive combinatorics, 2Seminar series:Given a somewhat large subset A of F_{p}^{n}, an ndimensional vector space over A of F, must the sumset A+A+A contain a large subspace? Can we say anything interesting about A itself, based solely on its size? In this twopart talk I shall introduce Fourier analysis on finite abelian groups and show how this can be used to deal with questions such as these. This will involve a version of the notion of almostperiodicity, which we shall be able to translate into tangible combinatorial results. I plan to assume very few prerequisites.

11/12/2009 4:30 PMM103Raul MondragonTwo problems on connectivity of networks

01/01/2014 4:30 PMM103Viresh Patel (QMUL)A domination algorithm for {0,1}instances of the travelling salesman problemSeminar series:
The development of approximation algorithms for NPhard combinatorial optimization problems is a very active field of study. One usually measures the performance of an approximation algorithm with the approximation ratio. In this talk, I will begin by introducing a less wellknown measure called the domination ratio.
I will discuss an approximation algorithm for $\{0,1}$instances of the travelling salesman problem which performs well with respect to domination ratio. More precisely, given a $\{0,1\}$edgeweighting of the complete graph $K_n$ on $n$ vertices, our algorithm outputs a Hamilton cycle $H$ of $K_n$ with the following property: the proportion of Hamilton cycles of $K_n$ whose weight is smaller than that of $H$ is at most $n^{1/29} = o(1)$. We use a combination of probabilistic and algorithmic techniques together with some results from extremal graph theory. Previously, the best result in this direction was a polynomialtime algorithm for general TSP that outputs a Hamilton cycle H such that at most 1/2 of all Hamilton cycles of K_n have weight smaller than H.
On the hardness side we can show that, if the Exponential Time Hypothesis holds, there exists a constant $C$ such that $n^{1/29}$ cannot be replaced by $\exp((\log n)^C)$ in our result above.
(Joint work with Daniela Kühn and Deryk Osthus)

07/02/2014 4:30 PMM103Mark Walters (QMUL)Fast wins in ninarow gamesSeminar series:
Consider the following two player game: players take turns to pick
points of R^2. A player wins if he has n points on a line containing
none of his opponents points. Standard game theoretic techniques show
that this game is a first player win.We consider a variant where a player is allowed to play t points on his
t'th move. Again this is a first player win and it is clear that the
first player can win by the nth move (play all n points in a line
somewhere).We prove that it is not possible for the first player to win (much) more
quickly than this.Joint work with Joshua Erde (Cambridge).

14/02/2017 4:30 PMM103Trevor Pinto (QMUL)Saturated subgraphs of the hypercubeSeminar series:

28/02/2016 4:30 PMM103Kitty Meeks (QMUL)The parameterised complexity of subgraph counting problemsSeminar series:

07/03/2014 4:30 PMM103Neville Ball (QMUL)Cops and Robbers on Geometric GraphsSeminar series:
Cops and robbers is a graph game in which a set of cops C try to catch a robber R by taking it in turns to move along the edges of a graph G. The cop number of a graph, c(G), is defined to be the minimum number of cops required to always catch the robber when the game is played on G. I will outline some general results about the cop number of graphs before looking in detail at the cop number of random geometric graphs.

14/03/2014 4:30 PMM103Tony Guttmann (Melbourne)Calculation of the spanning tree constant for threedimensional latticesSeminar series:
The number of spanning trees on a regular lattice of N sites increases as \lambda^N, where \lambda depends on the lattice. The value of \lambda has been known for 2d lattices since the 1970s, but only now can we calculate, exactly, the corresponding results for 3d lattices (and, in some cases, higher dimension). (The calculation is the evaluation of a 3d integral, much like the Watson integrals for Greens functions). In 3d the b.c.c. was known (it's trivial), but the other results are new. The techniques depend on concepts from number theory, in particular logarithmic Mahler measures.

21/03/2014 4:30 PMM103Donovan Young (QMUL, Physics)The distribution of dominoes in the game of memorySeminar series:
When all the elements of the set {1,1,2,2,3,3,...,n,n} are placed randomly in an m x k rectangular array of cells (one element per cell, with mk=2n), what is the probability that exactly p of the pairs are found with their matching partner directly beside them in a row or column  thus forming a 1 x 2 domino? For the case p=n this is just the domino tiling problem solved by Kastelyn. This talk will investigate the case for the remaining values of p.

13/06/2014 5:30 PMM103Paul Renteln (California State University)Reflection Group NumerologySeminar series:

22/08/2014 4:30 PMMaths 103Dillon Mayhew (Victoria University of Wellington)Characterising representable matroids in two different waysSeminar series:
Matroids are abstract objects that lie behind various notions of dependence (linear, geometric, algebraic), in the same way that topologies lie behind various notions of continuity. More specifically, a matroid consists of a finite collection of points, and a distinguished family of dependent subsets. If we take a finite collection of vectors from a vector space, and distinguish the linearly dependent subsets, then the result is a matroid, and we say that such a matroid is representable. The original motivating problem in matroid theory involves deciding which matroids are representable and which are not. A large fraction of the research in the area has been driven by this problem.
This talk will be an introduction to matroid theory, and an examination of two different methods for characterizing representable matroids. The first method involves excludedminors. Matroid minors are exact analogues of graph minors: we can remove an element from a matroid by deleting or contracting it, and any matroid produced by a sequence of these operations is called a minor. The class of matroids representable over a field is closed under the operations of deletion and contraction, and therefore can be characterised by listing the minorminimal matroids not in the class. The second approach to characterising representable matroids involves the use of formal languages – can we add axioms to the list of matroid axioms in such a way that we exactly capture the class of representable matroids? This approach has not received nearly as much study, but there have been some recent developments.
No knowledge of matroids will be assumed.

26/09/2014 4:30 PMM103Eoin Long (University of OxfordFranklRödl type theorems for codes and permutationsSeminar series:
How large can a family $\cal{A} \subset $P[n]$ be if $A \cap B \neq t$ for
all $A,B \in \cal{A}$? The FranklRödl theorem shows that if
$0 < \epsilon n< t < (1/2\epsilon)n$, then ${\cal A} \leq (2\delta)^n$, where
$\delta = \delta (\epsilon )> 0$. In this talk I will describe a new
proof of this theorem. Our method extends to codes with forbidden distances, where over
large alphabets our bound is significantly better than that obtained by Frankl and Rödl.
One consequence of this result is a FranklRödl type theorem for permutations with a
forbidden distance. Joint work with Peter Keevash. 
03/10/2014 5:30 PMM103Simon Griffiths (University of Oxford)Random Graph ProcessesSeminar series:
A \emph{random graph process} consists of a sequence of random graphs
$G_0,G_1,G_2,\dots\,$, where $G_{m+1}$ is obtained from $G_m$ by adding a
single randomly selected edge. The most famous such model  in which the
selections are independent  was introduced by Erd\H{o}s and R\'enyi in
1959. In this talk we discuss a number of random graph processes, with a
particular emphasis on the trianglefree process. We shall give a broad
overview of the methods used to analyse such processes and say something
about the recent result that the final graph $G_{n,\triangle}$ has strong
quasirandomness properties and has (with high probability)\[e(G_{n,\triangle}) = \left(\frac{1}{2\sqrt{2}}+o(1)\right)n^{3/2}\sqrt{\log{n}}.\]
Furthermore, by bounding the size of independent sets in
$G_{n,\triangle}$, we give an improved lower bound on the Ramsey number
$R(3,k)$ (the upper bound is due to Shearer):\[\left(\frac{1}{4}  o(1) \right) \frac{k^2}{\log k} \le R(3,k) \le (1 + o(1)) \frac{k^2}{\log k}\]
These results are based on joint work with Gonzalo Fiz Pontiveros and
Robert Morris. Similar results have been proved independently by Tom
Bohman and Peter Keevash. 
10/10/2014 5:30 PMM103Dan Kral (University of Warwick)Combinatorial limits and their relation to extremal combinatorics and property testing.Seminar series:
The recent theory of combinatorial limits has opened new links between analysis, combinatorics,
computer science, group theory and probability theory. The talk will be focused on limits of
two particular types of discrete objects  permutations and graphs. Motivated by applications
in extremal combinatorics, Lovasz and Szegedy (2011) conjectured that every finitely forcibly
graph limit must be wellstructured, which we will disprove using a new method for constructing
finitely forcible combinatorial limits we developed. Another area of applications of combinatorial
limits is related to algorithms for large inputs called property and parameter testing algorithms.
We will explain the general framework and provide new specific results in relation to such algorithms
for permutations in the analogy to the existing results for graphs.The talk will be selfcontained and no previous knowledge of the area is needed.

17/10/2013 5:30 PMM103Nick Day (QMUL)Saturated graphs of prescribed minimum degreeSeminar series:
A graph G is Hsaturated if it contains no copy of H as a subgraph, but the addition of any new edge to G creates a copy of H. Let K_p denote the complete graph on p vertices. Suppose G is a K_psaturated graph on n vertices with minimum degree at least t. How few edges can G have? In this talk we will consider this question and show, for fixed t and p, that G must have at least tn  O(1) edges.

24/10/2014 5:30 PMM103Robert Johnson (QMUL)Strategy Stealing in Avoidance gamesSeminar series:
Let H be a hypergraph. In the maker game on H, two players take it in turns to colour vertices of H in their own colour. The player who first achieves an edge of H in their colour wins. The well known strategy stealing argument shows that for any H this game is either a first player win or a draw.
We consider the avoidance (or misere) version of this game in which the first player to achieve an edge of H in their colour loses. A plausible hope (implicit in a remark of Beck) is that when H is transitive, the avoidance game is either a second player win or a draw. We show that this is false and investigate what possible extra conditions on H may make it true.
Joint work with Imre Leader and Mark Walters.

31/10/2014 4:30 PMM103Olivier Henard (QMUL)The random graph near the critical window: a probabilistic review.Seminar series:Combinatorics Study Group
In the Erd\"osRenyi random graph process, the edges of the complete graph on n vertices are added one by one, at random and without replacement.
The size of the largest component is a random variable of order log(n), order n^{2/3}, or order n, when t.n edges have been added, and t<1/2, t=1/2, t>1/2 respectively. This random variable is nonconcentrated in the critical t=1/2 case. This property is conserved at times n/2+s for s=O(n^{2/3}): this defines the critical window (Bollob\'as; \Luczak). Near, but outside the critical window, the largest component is again concentrated, and may be precisely described.
We shall review this material, with an emphasis on the recent probabilistic proofs that have emerged in the last years (Nachmias, Peres; Bollob\'as, Riordan). Time permitting, we will also discuss the specific challenges raised by considering graphs with geometry in place of the complete graph.

04/11/2014 5:00 PM4.01, Bancroft Road Teaching Rooms, Mile End Campus, QMUL.Peter Cameron (St Andrews)Regular PolytopesSeminar series:
Polytopes are beautiful objects whose study has geometric and combinatorial
features. The most symmetric polytopes are the regular ones, whose
automorphism group acts transitively (and in fact regularly) on maximal flags.
These generalise the familiar regular polygons and polyhedra of 2 and
3dimensional spaces.It is known that the existence of a regular polytope with a given
automorphism group $G$ is equivalent to a presentation of $G$ as a
\emph{string Cgroup}, a group generated by $r$ involutions (where $r$ is
the rank) such that involutions which are not consecutive in the list commute,
and an intersection property holds (implying that the Boolean lattice of
rank $r$ is embedded in the subgroup lattice of $G$).Dimitri Leemans in Auckland and his collaborators Maria Elisa Fernandes and
Mark Mixer have proved some remarkable results
on regular polytopes whose automorphism group is a symmetric or alternating
group. For example, if $n\ge 2k+3$, then the number of such polytopes of
rank $nk$ with automorphism group $S_n$ is $1,1,7,9$ for $k=1,2,3,4$, and
probably $35$ for $k=5$.I will say a bit about how these results work, and describe a theorem we
proved recently and how it might help extend them. 
11/11/2014 4:30 PMM103Iain Moffat (RHUL)From embedded graphs to deltamatroids.Seminar series:
Matroid theory is often thought of as a generalisation of graph theory. Many results in graph theory turn out to be special cases of results in matroid theory. This is beneficial in two ways. Firstly, graph theory can serve as an excellent guide for studying matroids. Secondly, matroid theory can lead to new, and more general, results about graphs. Thus graph theory and matroid theory are mutually enriching.
In this talk I will be interested in embedded graphs (i.e., graphs in surfaces), rather than abstract graphs. By moving from an embedded graph to a matroid we generally loose all of its topological information. Thus matroids do not appear to provide a `correct' generalisation of embedded graphs. If matroids don't, what do? In this talk I will propose that deltamatroids play the role of matroids in topological graph theory. Deltamatroids were introduced by Bouchet, and arise by relaxing one of the axioms of a matroid. I will show that results about embedded graphs can be understood as results about deltamatroids, and that embedded graphs provide an excellent guide for studying deltamatroids. Throughout this talk I will emphasise a direct analogy with the classical matroidgraph connection. I will not assume any familiarity with matroids.
This is joint work with Carolyn Chun, Steven Noble and Ralf Rueckriemen.

14/11/2014 4:30 PMM103Sam Alexander (UCL)Biologically Unavoidable SequencesSeminar series:
A 'biologically unavoidable sequence' is an infinite sequence of colours from {1,2,…,n} that occurs in every infinite ncoloured directed acyclic graph satisfying some mild biologicallymotivated axioms. We sketch: 1. that eventuallyperiodic implies biologically unavoidable, and 2. that biologically avoidable sequences exist. (1. generalizes Konig's Lemma. 2. involves unexpected counting arguments.)
Based on:
"Biologically unavoidable sequences", Electr. J. Comb. 20 (2013),
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p31 
28/11/2014 4:30 PMM103Alex Fink (QMUL)The Tutte polynomial via algebraic geometry via splines
The Tutte polynomial of a matroid has a formula arising from algebraic
geometry; surprisingly given the context, it also works for
nonrealisable matroids. The formula reveals its close kinship with
some other invariants: the Ehrhart polynomial and an invariant of
Speyer notionally counting the pieces in a decomposition into
seriesparallel matroids. In fact the algebraic geometry needed can
be worked with in a wholly combinatorial fashion, using splines and
lattice point enumeration in cones. I'll explain this, beginning from
a review of the matroid notions.This work is joint with David Speyer.

05/12/2014 4:30 PMM103Richard Montgomery (University of Cambridge)Spanning Trees in Random Graphs
Given a tree T with n vertices, how large does p need to be for it to be likely that a copy of T appears in the binomial random graph G(n,p)? I will discuss this question, including recent work confirming a conjecture which gives a good answer to this question for trees with bounded maximum degree.

12/12/2014 4:30 PMM103Bill Jackson (QMUL)Generic rigidity of pointline frameworks
A pointline framework is a collection of points and lines in the Euclidean plane which are linked by constraints which fix the angles between some pairs of lines, and the distances between some pairs of points and between some pairs of points and lines. It is rigid if the only continuous motion of the points and lines which preserve the constraints are translations or rotations of the whole plane. The rigidity of a framework depends only on its underlying `pointline graph' when the framework is generic i.e there are no algebraic dependencies between the coordinates of its points and lines. We characterize when a generic pointline framework is rigid. This is joint work with John Owen.

23/01/2015 4:30 PMM103Sean Eberhard (Oxford)Commuting probabilities of finite groups
The commuting probability of a finite group is defined to be the probability that two randomly chosen group elements commute. Not all rationals between 0 and 1 occur as commuting probabilities. In fact Keith Joseph conjectured in 1977 that all limit points of the set of commuting probabilities are rational, and moreover that these limit points can only be approached from above. In this talk we'll discuss a structure theorem for commuting probabilities which roughly asserts that commuting probabilities are nearly Egyptian fractions of bounded complexity. Joseph's conjectures are corollaries.

30/01/2015 4:30 PMM103Marcin Pilipczuk (Warwick)Graph Isomorphism in graphs of bounded treewidth.
Graph Isomorphism is one of the classical combinatorial problems whose complexity status is wide open. In my talk, I will focus on graphs of bounded treewidth, and present known approaches to tackle this problem in these graph classes. In particular, I will present the recent fixedparameter tractable algorithm for Graph Isomorphism parameterized by the treewidth that relies on an isomorphicinvariant modification of the wellknown RobertsonSeymour approximation algorithm for treewidth. The talk is mostly based on http://arxiv.org/abs/1404.0818(link is external), presented at FOCS 2014.

06/02/2015 4:30 AMAdthasit Sinna (QMUL)Tutte trails in plane graphs
Let G be a multigraph without loops. A Tutte trail of G is defined to be a trail H in G such that each component of G\V(H) has at most three edges connecting it to H. In this talk, I will show that a 2edgeconnected plane graph has a Tutte trail. I will also discuss the relationship between Tutte trails and the conjecture of Carsten Thomassen that every 4connected line graph is Hamiltonian.

13/02/2015 4:30 PMM103Akihiro Higashitani (Kyoto, visiting Imperial)Ehrhart polynomials of lattice polytopes
The Ehrhart polynomial of a lattice polytope P is the enumerative function counting the number of lattice points contained in the dilated polytope nP for any positive integer n. In this talk, after introducing the fundamental facts on Ehrhart polynomials of lattice polytopes, I'll present some characterizing results on them.

27/02/2015 4:30 PMM103Bernd Schulze (Lancaster)Rigidity of frameworks on expanding spheres
In this talk we will discuss the rigidity and flexibility of barjoint frameworks in (d+1)dimensional space whose vertices are constrained to lie on concentric dspheres with independently variable radii. In particular, we present combinatorial characterisations of generic rigid frameworks for d=1 with an arbitrary number of independently variable radii, and for d=2 with at most two variable radii. This includes a characterisation of the rigidity or flexibility of uniformly expanding spherical frameworks in 3space.
Due to the equivalence of the generic rigidity between Euclidean space and spherical space, these results interpolate between rigidity in 1D and 2D and to some extent between rigidity in 2D and 3D.
Our initial motivation for this work was to understand the spherical mechanisms of mathematical toys inspired by popular structures like the Hoberman sphere (such as Juno's spinners, for example). Since many of these structures exhibit nontrivial symmetries, we also briefly discuss the impact of symmetry on the flexibility of frameworks on variable spheres.
This is joint work with Anthony Nixon, Shinichi Tanigawa and Walter Whiteley.

06/03/2015 4:30 PMM103Trevor Pinto (QMUL)Directed Paths in the Cube
In 1997, Bollobás and Leader gave tight lower bounds for the number of edgedisjoint paths between disjoint subsets A and B of the hypercube, Q_n, in terms of A and B. They conjectured that this bound holds even when A is a downset, B is an upset and the paths are required to be directed (that is, the vertices in the path form a chain). I will sketch a novel compressiontype argument that proves a stronger version of this conjecture.

13/03/2015 10:13 AMM103Alan Sokal (New York)Coefficientwise total positivity (via continued fractions) for some Hankel matrices of combinatorial polynomials
A matrix $M$ of real numbers is called totally positive if every
minor of $M$ is nonnegative; I will call a matrix $M$ of polynomials
(in some set of indeterminates) coefficientwise totally positive if
every minor of $M$ is a polynomial with nonnegative coefficients.
I will call a sequence $(a_k)_{k \ge 0}$ of real numbers (or polynomials)
(coefficientwise) Hankeltotally positive if the Hankel matrix
$H = (a_{i+j})_{i,j \ge 0}$ associated to $(a_k)$ is (coefficientwise)
totally positive. The (coefficientwise) Hankeltotal positivity of a
sequence $(a_k)$ implies its (coefficientwise) logconvexity, but is
much stronger. (For sequences of real numbers, Hankeltotal positivity
is equivalent to being a Stieltjes moment sequence.)I will point out a simple sufficient condition for the (coefficientwise)
total positivity of a Hankel matrix, based on expanding the power series
$\sum_{k=0}^\infty a_k t^k$ into a Stieltjestype (or Jacobitype)
continued fraction. As a consequence I can show that a number of
sequences of polynomials arising in enumerative combinatorics are
coefficientwise Hankeltotally positive; this approach also gives
combinatorial interpretations of all the Hankel minors, and explicit
formulae for the first few leading principal minors.I conclude by giving some examples of sequences of combinatorial
polynomials that appear empirically to be Hankeltotally positive
but which cannot be handled by this continuedfraction approach.
Foremost among these are the inversion enumerator for trees, $I_n(y)$,
which is related to the generating polynomials $C_n(v)$ of connected
graphs.Attachment Size Slides from the talk [PDF 194KB] 194.28 KB 
20/03/2015 4:30 PMM103Bhargav Narayanan (Cambridge)Coalescence on the real line
Given two probability distributions P_R and P_B on the positive reals with finite means, colour the real line alternately with red and blue intervals so that the lengths of the red intervals have distribution P_R, the lengths of the blue intervals have distribution P_B, and distinct intervals have independent lengths. Now iteratively update this colouring of the line by coalescing intervals: change the colour of any interval that is surrounded by longer intervals so that these three consecutive intervals subsequently form a single monochromatic interval. Say that a colour (either red or blue) `wins' if every point of the line is eventually of that colour. This talk will attempt to answer the following question: under what natural conditions on the distributions is one of the colours almost surely guaranteed to win?

27/03/2015 4:30 PMM103Shabnam Beheshti (QMUL)Hydrodynamical Solitons, a Combinatorial Perspective
Recent works of Kodama et. al. (Chakravarty and Kodama 2009, Kodama and Williams 2013) have demonstrated deep connections between soliton solutions of the KadomtsevPetviashvili (KP) Equation and wellknown combinatorial structures, including generating polynomials, Grassmann necklaces, Young diagrams, and matroids.
Joint work with A. Redlich (Bowdoin Univ.) provides a simple extension to the class of KP solitons which may be considered in this context. More recently, progress has also been made with A. Hamm (Winthrop Univ.) in understanding some of these structures for the JimboMiwa equation. In light of this "modern combinatorics toolkit", we present several open questions on what may make a Wronskianintegrable PDE admit (or exclude) certain combinatorial structures.

10/04/2015 5:30 PMM103Benjamin Schröter (Berlin)Matroidal Subdivisions, Dressians and Tropical Grassmannians
AttachmentSizeAbstract [PDF 135KB]135.88 KB

24/04/2015 5:30 PMM103Ivan IzmestievImpossible Triangulations
If a triangulation of the sphere has only two vertices of odd degree, then these cannot be adjacent. We prove this curious fact by studying the colouring monodromy, an obstruction to the existence of a vertex colouring. The monodromy also leads to a construction of equivelar surfaces of high genus.
Similar in the spirit is the following theorem. There is no triangulation of the torus with all vertex degrees 6, except for one of degree 5 and one of degree 7. This is proved by studying the rotation monodromy of the geometric structure obtained by making each triangle of the triangulation to an equilateral euclidean triangle.
The second result is a joint work with Kusner, Rote, Springborn, and Sullivan. 
08/05/2015 5:30 PMM103David Ellis (QMUL)The structure of graphs which are locally indistinguishable from a lattice
We study the properties of finite graphs in which the ball of radius r around each vertex induces a graph isomorphic to some fixed graph F. (Such a graph is said to be rlocallyF.) This is a natural extension of the study of regular graphs, and of the study of graphs of constant link. We focus on the case where F is L^d, the ddimensional integer lattice. We obtain a characterisation of all the finite graphs in which the ball of radius 3 around each vertex is
isomorphic to the ball of radius 3 in L^d, for each integer d. These graphs have a very rigidly proscribed global structure, much more so than that of (2d)regular graphs. (They can be viewed as quotient lattices in certain 'flat orbifolds'.) Our results are best possible in the sense that '3' cannot be replaced with '2'. Our proofs use a mixture of techniques and results from combinatorics, algebraic topology and group theory. Joint work with Itai Benjamini (Weizmann Institute of Science). 
15/05/2015 5:30 PMM103Abhishek Methuku (Budapest)Forbidden subposets, forbidden matrices, and their connection.
We prove that for every poset P, there is a constant C_P such that the size of any family of subsets of [n] that does not contain P as an induced subposet is at most C_P (n \choose n/2), proving a conjecture of Katona, and Lu and Milans. We obtain this bound by establishing a connection to the theory of forbidden submatrices and then applying a higher dimensional variant of the MarcusTardos theorem, proved by Klazar and Marcus.

22/05/2015 5:30 PMM103Katharine Clinch (QMUL)Global Rigidity of DirectionLength Frameworks
A twodimensional directionlength framework (G, p) consists of a multigraph G = (V ; D, L) whose edge set is partitioned into “direction” edges D (which fix the gradient of the line through both endvertices), and “length” edges L (which specify the distance between their endvertices); together with a realisation p of this graph in the plane.
Given a directionlength framework (G, p), we want to know whether there are other realisations of G which satisfy the same direction and length constraints. Any such framework (G, q) is said to be equivalent to (G, p)
We can easily obtain frameworks which are equivalent to (G,p) by either translating (G, p) in the plane or rotating it by 180 degrees, but are these the only equivalent frameworks? If so we say that (G,p) is globally rigid.Characterisations of global rigidity exist for two classes of generic frameworks, but we do not yet have a full characterisation. In this talk I will explain the methods used to obtain these two characterisations, and describe to what extent these methods might be helpful in tackling the remaining cases.

05/06/2015 5:30 PMM103Anthony Hilton (Reading and QMUL)Some theorems and conjectures about extremal finite set structures
(See pdf file attached.)
Attachment Size hiltonbccabstract [PDF 124KB].pdf 124.24 KB 
02/10/2015 5:00 PMM103 (Mathematical Sciences)Madhusudan Manjunath (QMUL)Explicit Deformations of Lattice Ideals via Chip Firing Games
We start with a brief introduction to chip firing games. We then discuss an application of chip firing games to a problem in combinatorial commutative algebra, namely explicit deformations of lattice ideals. This talk is based on joint work with Spencer Backman.

09/10/2015 5:00 PMM103 (Mathematical Sciences)Natasha Morrison (University of Oxford)Bootstrap percolation in the hypercube
The \emph{$r$neighbour bootstrap process} on a graph $G$ starts with an initial set of ``infected'' vertices and, at each step of the process, a healthy vertex becomes infected if it has at least $r$ infected neighbours (once a vertex becomes infected, it remains infected forever). If every vertex of $G$ becomes infected during the process, then we say that the initial set \emph{percolates}.
In this talk I will discuss the proof of a conjecture of Balogh and Bollob\'{a}s: for fixed $r$ and $d\to\infty$, the minimum cardinality of a percolating set in the $d$dimensional hypercube is $\frac{1+o(1)}{r}\binom{d}{r1}$. One of the key ideas behind the proof exploits a connection between bootstrap percolation and weak saturation. This is joint work with Jonathan Noel.

16/10/2015 5:00 PMM103 (Mathematical Sciences)Vytautas Gruslys (University of Cambridge)Tiling with copies of an arbitrary tile
Let $T$ be a tile in say $\mathbb{Z}^2$, meaning a finite subset of
$\mathbb{Z}^2$. It may or may not be the case that $T$ tiles
$\mathbb{Z}^2$, in the sense that $\mathbb{Z}^2$ can be partitioned
into copies of $T$. But is there always some higher dimension $d$ such
that $T$ tiles $\mathbb{Z}^d$? We prove that this is the case: for any
tile in $\mathbb{Z}^2$ (or in $\mathbb{Z}^n$, any $n$) there is a $d$
such that $\mathbb{Z}^d$ can be tiled with copies of it. This proves a
conjecture of Chalcraft. Joint work with Imre Leader and Ta Sheng Tan. 
23/10/2015 5:30 PMM103 (Mathematical Sciences)Ben Barber (University of Bristol)Edge decompositions of graphs
An Fdecomposition of a graph G is a partition of E(G) into copies of F. Determining whether a graph has an Fdecomposition is NPcomplete, but it is much easier to find 'fractional' decompositions. I'll explain the connection between these ideas and how it can be exploited to attack NashWilliams' conjecture that every large graph on n vertices with minimum degree at least 3n/4, e(G) divisible by 3 and every degree even, has a triangledecomposition. I'll also mention an application to completion of partial mutually orthogonal latin squares.

30/10/2015 4:00 PMM103 (Mathematical Sciences)Agelos Georgakopoulos (University of Warwick)Group Walk Random Graphs
I will discuss a construction of finite 'geometric' random
graphs motivated by the study of random walks on infinite groups. This
construction has connections to other topics, including the Poisson
boundary and Sznitman's random interlacements (which I will try to
introduce in a gentle way). 
06/11/2015 4:00 PMM103Shoham Letzter (University of Cambridge)Eigenvalues of subgraphs of the cube
Given a graph $G$, we define $\lambda_1(G)$ to be the largest eigenvalue of the adjacency matrix of $G$. We consider the following isoperimetric question: among subgraphs of the cube $Q_d = \{0, 1\}^d$ of prescribed order, which graphs maximise $\lambda_1$?
We believe that in most cases Hamming balls are maximisers and our result support this: we prove that Hamming balls are asymptotically best when the radius is $o(d)$; furthermore, when the radius is fixed, Hamming balls are maximisers for large $d$. Compressions play an important role in our proofs.
This is joint work with Jonathan Lee and B\'ela Bollob\'as.

13/11/2015 4:00 PM(No seminar – LMS AGM)
Bill Cook's lecture In pursuit of the traveling salesman: mathematics at the limits of computation is liable to be of interest to the CSG audience.

20/11/2015 4:00 PMM103Luka Milicevic (University of Cambridge)Points in almost general position
Erdos asked the following question: given a positive integer n, what is the largest integer k such that any set of n points in a plane, with no 4 on a line, contains k points no 3 of which are collinear? Furedi proved that k = o(n). Cardinal, Tooth and Wood extended this result to R^3, finding sets of n points with no 5 on a plane whose subsets with no 4 points on a plane have size o(n), and asked the question for the higher dimensions. For given n, let k be largest integer such that any set of n points in R^d with no more than d + 1 cohyperplanar points, has k points with no d + 1 on a hyperplane. Is k = o(n)? We prove that k = o(n) for any fixed d \geq 3.

27/11/2015 4:00 PMM103David Conlon (University of Oxford)Rational exponents in extremal graph theory
Given a family of graphs $\mathcal{H}$, the extremal number $\textrm{ex}(n, \mathcal{H})$ is the largest $m$ for which there exists a graph with $n$ vertices and $m$ edges containing no graph from the family $\mathcal{H}$ as a subgraph. We show that for every rational number $r$ between $1$ and $2$, there is a family of graphs $\mH_r$ such that $\textrm{ex}(n, \mH_r) = \Theta(n^r)$. This solves a longstanding problem in the area of extremal graph theory.
Joint work with Boris Bukh.

30/11/2015 5:00 PMM203 (Mathematical Sciences)Benny Sudakov (ETH Zurich)Two Short Stories in Extremal Combinatorics
In this talk we present variants of two classical extremal problems:
estimating Ramsey numbers for cliques and Tur\'an numbers for complete
bipartite graphs. Our results (obtained jointly with Conlon and Fox)
are proved by basic probabilistic arguments and answer questions of
Bollob\'as, Erd\H{o}s, Foucaud, Hajnal, Krivelevich and Perarnau. 
04/12/2015 10:59 AMM103Susama Agarwala (Nottingham)Wilson Loop Diagrams and Positroids
In this talk, I will present a family of graphs that represent
particle interactions in a field theory. They also represent
Grassmannians. Using matroid technology, I answered the physically
interesting question of which diagrams correspond to positive
Grassmannians. I also discuss open questions regarding defining a
differential operator, combinatorially, on this family of graphs. 
11/12/2015 4:00 PMM103Mark Walters (QMUL)Dense Random Geometric Graphs
Rado showed that the random graph with a countable vertex set
and each chosen independently with probability $1/2$ is, almost surely,
unique up to isomorphism. Bonato and Janssen showed that there are some
countable random geometric graphs with the same property, but that this
depended on the underlying geometry (i.e., the norm on the underlying
normed space). They also gave a partial classification of which norms in
two dimensions do give a unique graph.We give a complete classification of all norms in all (finite)
dimensions. The proof mixes combinatorics, probability and the geometry
of finite dimensional lattices.This is joint work with Paul Balister, B\'ela Bollob\'as, Karen
Gunderson and Imre Leader. 
15/01/2016 4:00 PMM103Mark Jerrum (QMUL)A switch Markov chain for perfect matchings
Motivated by a sampling problem arising in statistics, Diaconis, Graham and Holmes
introduced a simple Markov chain, the switch chain, on the set of all perfect
matchings in a bipartite graph G. Two basic questions about this Markov chain are:
for which class of graphs is the switch chain ergodic, and for which is it rapidly
mixing? (I.e., does the switch chain have a limiting distribution and, if so,
what is its rate of convergence?) I'll present a precise answer to the ergodicity
question and close bounds on the mixing question. In particular, I'll give some
rough indications of a proof that the mixing time of the switch chain is polynomial
in the size of the graph G in the case that G is monotone (a.k.a. a bipartite
permutation graph). The class of monotone graphs includes examples of interest
in the statistical setting. 
29/01/2016 4:00 PMM103Arès Méroueh (Cambridge)A LYM inequality for induced posets
Let A and B be two partially ordered sets. We say that B contains A
strongly (or: "inducedly") if there exists an injective map f from A to
B such that f(x) < f(y) if and only if x < y for every x, y in A. In
this talk, I will prove that for every (finite) partially ordered set P,
there exists a constant c(P) such that if a subset F of the hypercube
(ordered by inclusion) does not contain P strongly, then the LYM density
of F is at most c(P), where the LYM density of F is defined to be the
sum of the densities of F within each level of the hypercube. This
proves a conjecture of Lu and Milans, and strengthens a result of
Methuku and Pálvölgyi. 
12/02/2016 4:00 PMM103Ben Fairbairn (Birkbeck)What lies South of Southend: games and groupoids
Recently there has been a lot of chatter from various parties about
generalising Conway's extraordinary construction of the small Mathieu
groups from projective planes. For some reason several of these people
seem to think I should put my oar in and so here are some thoughts on
these recent constructions along these lines and potential avenues for
generalisations. 
19/02/2016 4:00 PMM103 (Mathematical Sciences)Jan van den Heuvel (LSE)Generalised Colouring Numbers of Graphs
The wellknown colouring number of a graph is one more than the smallest
k for which there exists an ordering of the vertices in which each
vertex has at most k neighbours that come earlier in the order. The
colouring number is a trivial upper bound for the chromatic number of
the graph. But it also contains structural information of the graph, for
instance regarding the edge density of any subgraph.
When instead of neighbours that are earlier in the order we consider
vertices that are earlier and can be reached by a path of length at most
r, we get the generalised colouring numbers. Depending on where we want
the internal vertices of such paths to appear in the order, we actually
can define different types of those generalised colouring numbers.
Generalised colouring numbers were introduced by Kierstead and Yang in
2003, to study specific types of graph colourings. In the last couple of
years it has been realised that the generalised colouring numbers are
closely related to many structural properties of graphs (such as
treedepth and treewidth).
In this talk we give an overview of the relations between the
generalised colouring numbers and specific types of colourings of
graphs; we discuss relations between those numbers and structural
properties of graphs; and we discuss some new bounds on these numbers
for specific classes of graphs (such as planar and minorclosed graphs).Joint work with Patrice Ossona de Mendez, Daniel Quiroz, Roman
Rabinovich, and Sebastian Siebertz. 
26/02/2016 4:00 PMM103 (Mathematical Sciences)Alex Fink (QMUL)Rigidity of matroid realisations
A theorem of Lafforgue asserts that a matroid whose polytope cannot be
dissected into smaller matroid polytopes can have only finitely many
representations over any field, and in particular no continuously
deformable representation. We explain a proof using the machinery of
valuated matroids, which we present by way of hyperfields following
Matt Baker's recent work. 
04/03/2016 4:00 PMM103Gary Greaves (Tohoku University)Equiangular lines in Euclidean spaces
Given some dimension $d$, what is the maximum number of lines in $\mathbb{R}^d$ such that the angle between any pair of lines is constant? This classical problem has recently enjoyed a renewed interest due to the current attention the quantum information community is giving to its complex analogue. I will report on some new developments of the theory of equiangular lines in Euclidean spaces. Among other things, I will present a new construction using real mutually unbiased bases and improvements to two long standing upper bounds for equiangular lines in dimensions 14 and 16.

11/03/2016 4:00 PMM103Roger Behrend (Cardiff)Diagonally and antidiagonally symmetric alternating sign matrices of odd order
An alternating sign matrix (ASM) is a square matrix in which each entry is 1, 0 or 1, and along each row and column the nonzero entries alternate in sign, starting and ending with a 1. It was conjectured by Mills, Robbins and Rumsey in 1982 that the number of ASMs of fixed size is given by a certain simple product formula. A relatively short proof of this conjecture was obtained by Kuperberg in 1996, using connections with the sixvertex model of statistical mechanics. It was also conjectured by Robbins in the mid 1980's that the number of ASMs of fixed odd size which are invariant under diagonal and antidiagonal reflection is given by a simple product formula. This conjecture has only recently been proved, again using connections with the sixvertex model, in my joint work with Ilse Fischer and Matjaz Konvalinka (see arXiv:1512.06030). In the first part of this talk, I'll introduce ASMs, and review Kuperberg's proof of the ASM enumeration formula. In the second part, I'll outline the proof of the enumeration formula for diagonally and antidiagonally symmetric ASMs of odd order.

18/03/2016 4:00 PMM103 (Mathematical Sciences)Sean Eberhard (Oxford)Productfree subsets of the alternating group

01/04/2016 4:00 PMM103 (Mathematcal Sciences)Hakan Guler (QMUL)Rigidity of BodyBar Frameworks
Informally, a bodybar framework consists of some rigid bodies and some bars each connecting two different rigid bodies. We can use multigraphs to illustrate bodybar frameworks by adding a vertex for each rigid body
and adding k edges between two vertices if there are k bars connecting the rigid bodies corresponding to these vertices.Tay showed that a generic bodybar framework is rigid if and only if the underlying multigraph contains the union of six edgedisjoint spanning trees, where a framework is generic if the endpoints of the bars are algebraically independent over the rationals. We will summarise Tay's result and then introduce some classes of nongeneric
bodybar frameworks that have the same characterisation as the generic ones. 
29/04/2016 4:15 PMM103Paul Balister (University of Memphis)The sharp threshold for making squares.
Many of the fastest known algorithms for factoring large integers rely on finding subsequences of randomly generated sequences of integers whose product is a perfect square. Motivated by this, in 1994 Pomerance posed the problem of determining the threshold of the event that a random sequence of $N$ integers, each chosen uniformly from the set $\{1,\dots,x\}$, contains a subsequence, the product of whose elements is a perfect square. In 1996, Pomerance gave good bounds on this threshold and also conjectured that it is {\em sharp}.
In a paper published in Annals of Mathematics in 2012, Croot, Granville, Pemantle and Tetali significantly improved these bounds, and stated a conjecture as to the location of this sharp threshold. In recent work, we have confirmed this conjecture. In my talk, I shall give a brief overview of some of the ideas used in the proof, which relies on techniques from number theory, combinatorics and stochastic processes. Joint work with B\'ela Bollob\'as and Robert Morris.

30/09/2016 4:00 PMM203Georg Loho (Berlin)Feasibility of tropical linear inequality systems and applications
Classical linear inequality systems can be examined well by linear programming. The tropical counterpart is more difficult to handle.
We examine the problem from a combinatorial point of view related to tropical oriented matroids. Furthermore, we show connections to scheduling and games.

07/10/2016 4:00 PMM203Alina Vdovina (Newcastle)Expanders, buildings and surfaces
We'll present buildings as universal covers of certain CAT(0) complexes. Fundamental groups of these complexes will be used for expander constructions and for generating an infinite families of tessellated compact hyperbolic surfaces with large isometry groups.

14/10/2016 4:00 PMM203Heng Guo (QMUL)Random cluster dynamics at q = 2 is rapidly mixing
We show that the mixing time of Glauber (single edge update) dynamics for the random cluster model at q = 2 is bounded by a polynomial in the size of the underlying graph. As a consequence the SwendsenWang algorithm for the ferromagnetic Ising model at any temperature has the same polynomial mixing time bound.
Joint work with Mark Jerrum.

21/10/2016 4:00 PMM203Bhargav Narayanan (Cambridge)Symmetric Intersecting Families
A family of sets is said to be intersecting if any two sets in the family have nonempty intersection. Families of sets subject to various intersection conditions have been studied over the last fifty years and a common feature of many of the results in the area is that the extremal families are often quite asymmetric. Motivated by this, Peter Frankl conjectured in 1981 that symmetric intersecting families must generally be very small; more precisely, Frankl conjectured that if a family of subsets of {1, 2, . . . , n} with the property that any three sets in the family intersect has a transitive automorphism group, then the family must have size o(2^n). In this talk, I shall prove this conjecture.
Joint work with David Ellis.

28/10/2016 4:00 PMM203Eoin Long (Oxford)Counting Hamilton decompositions of oriented graphs
A Hamilton cycle in a directed graph G is a cycle that passes through every vertex of G. A Hamiltonian decomposition of G is a partition of its edge set into disjoint Hamilton cycles. In the late 60s Kelly
conjectured that every regular tournament has a Hamilton decomposition. This conjecture was
recently settled by Kühn and Osthus, who proved more generally that every rregular nvertex oriented graph G (without antiparallel edges) with r=cn for some fixed c>3/8 has a Hamiltonian decomposition, provided
n=n(c) is sufficiently large.In this talk I will address the natural question of estimating the number of such decompositions of G. Our main result shows that this number is n^{(1o(1))cn^2}. As a by product, we also obtain a new and much simpler proof for the approximate version of Kelly's conjecture.
Joint work with Asaf Ferber and Benny Sudakov.

28/10/2016 4:00 PMM203Eoin Long (Oxford)Counting Hamilton decompositions of oriented graphs
A Hamilton cycle in a directed graph G is a cycle that passes through every vertex of G. A Hamiltonian decomposition of G is a partition of its edge set into disjoint Hamilton cycles. In the late 60s Kelly
conjectured that every regular tournament has a Hamilton decomposition. This conjecture was
recently settled by Kühn and Osthus, who proved more generally that every rregular nvertex oriented graph G (without antiparallel edges) with r=cn for some fixed c>3/8 has a Hamiltonian decomposition, provided
n=n(c) is sufficiently large.In this talk I will address the natural question of estimating the number of such decompositions of G. Our main result shows that this number is n^{(1o(1))cn^2}. As a by product, we also obtain a new and much simpler proof for the approximate version of Kelly's conjecture.
Joint work with Asaf Ferber and Benny Sudakov.

11/11/2016 4:00 PMM203Jason Long (Cambridge)Increasing Sequences of Integer Triples
We will consider a deceptively simple question formulated by PoShen Loh concerning sequences of integer triples. We shall discuss some recent developments following joint work with Tim Gowers, and mention a collection of generalisations and open problems.

18/11/2016 12:26 PMM203Enzo Nicosia (QMUL)Random Functional Geometric Graphs: Elementary properties and open problems
This is a workinprogress talk. I will introduce a class of random geometric graphs where each node is associated to a real (scalar or vectorial) value, and the linking probability depends on a
generalised visibility criterion. We will discuss a few basic properties of such graphs in the specific case of uniform point distribution with uniformly sampled node values, and we will provide a review of several interesting open problems and potential applications. 
25/11/2016 12:27 PMM203Tony Nixon (Lancaster)Global rigidity of generic frameworks on surfaces
A ddimensional barandjoint framework is said to be globally rigid if every ddimensional framework with the same underlying graph and with the same edge lengths is congruent to it. In dimensions 1 and 2 global rigidity for generic frameworks can be characterised purely by properties of the underlying graph. In this talk I will describe these characterisations and discuss extensions to frameworks in 3dimensions whose vertices are restricted to move on a fixed surface. In particular when the surface is a generic family of concentric cylinders I will give a complete description of the graphs whose frameworks are generically globally rigid.

02/12/2016 12:28 PMM203Luka Milicevic (Cambridge)Decomposing Complete Hypergraphs
AttachmentSizeAbstract [PDF 80KB]80.06 KB

09/12/2016 12:30 PMM203Andrew McDowell (KCL)Target sets in degree proportional percolation
We consider a degree proportional percolation model in which an infection spreads through a graph by infecting any vertex which has a fixed proportion of its neighbours already infected. This talk will present the background and solution to the problem of identifying the size of a minimal initial target set which will spread the infection to the entire graph.
Joint work with Richard Mycroft and Frederik Garbe.

13/01/2017 4:00 PMM203David Ellis (QMUL)Subsets of the discrete cube with very small edge boundary
If S is a subset of {0,1}^n, i.e. S is a set of vertices of the discrete n
dimensional cube, the 'edge boundary' of S is the set of edges of the cube
which join a vertex in S to a vertex outside S. The edgeisoperimetric inequality
of Harper, Bernstein, Lindsay and Hart specifies, for each integer k, the smallest
possible size g_n(k) of the edgeboundary of a set of k vertices in {0,1}^n; the
extremal sets are initial segments of the lexicographic ordering on {0,1}^n (up
to automorphisms of the discrete cube), e.g. subcubes, when k is a power of 2.
There are several 'stability results' describing the structure of subsets of the
discrete cube with 'small' edgeboundary; some, such as Friedgut's Junta
theorem, have found many applications. We discuss a new stability result,
showing that if a subset of {0,1}^n of size k has edgeboundary of
size at g_n(k) + m, then it can be changed into an extremal set by at most O(m) additions and deletions.
We conjecture that O(m) could be replaced by 2m. Joint work with
Nathan Keller (BIU) and Noam Lifshitz (BIU). 
20/01/2017 12:47 PMM203Arran Hamm (Winthrop)On the triangle space of random graphs
The clique complex of a graph $G$, denoted $X(G)$, is the (abstract) simplicial complex where the vertex set of each clique of size $k$ corresponds to a $(k1)$face. For $G=G_{n,p}$, M. Kahle conjectured a precise threshold value $p_0$ so that if $p>p_0$, then a.s. the $k^{\textrm{th}}$ homology group of $X(G)$ over a field $\Gamma$ vanishes. In this talk I will discuss our proof that Kahle's conjecture holds for $k=1$ and $\Gamma=\mathbb{Z}_2$. By regarding $E(G)$ as a $\mathbb{Z}_2$vector space in the obvious way, the problem reduces to showing that a.s. the triangle space equals the cycle space for $p$ bigger than the conjectured $p_0$ . If time permits, generalizations to higher homology groups will be discussed. Joint work with B. DeMarco and J. Kahn.

27/01/2017 4:00 PMM203Will Perkins (Birmingham)An occupancy approach to bounding graph polynomials

03/02/2017 4:00 PMM203Mark Jerrum (QMUL)Counting list Hcolourings in hereditary graph classes
Suppose H is a fixed graph. Hcolourings of a graph G (a.k.a. homomorphisms from G
to H) generalise familiar proper vertex colourings of G. More than 15 years ago, Dyer
and Greenhill considered the computational complexity of counting Hcolourings,
and demonstrated a dichotomy, in terms of the graph H, between polynomial time
and #Pcomplete.That result was for exact counting, and, even now, there is only a partial complexity
classification for approximate counting. However, the classification problem becomes
tractable if we look instead at _list_ Hcolourings. In this talk, I’ll present a classification
(in fact a trichotomy) for the problem of approximately counting list Hcolourings of
a graph. It turns out that some interesting hereditary graph classes come into play
in describing and proving the trichotomy result.This is joint work with Andreas Galanis and Leslie Ann Goldberg (Oxford).

10/02/2017 4:00 PMM203Jack Bartley (QMUL)The emergence of the square of a Hamilton cycle in random geometric graphs
We define a random geometric graph by choosing n points in a square and joining pairs of points if they are close to each other. It is natural to ask when standard graph properties (such as connectedness, Hamiltonicity, et cetera) typically occur in this model. We consider the property of containing the square of a Hamilton cycle. Our main result is that for a typical point set the graph contains the square of a Hamilton cycle exactly when a simple local condition is satisfied at every vertex. Perhaps surprisingly, this property exhibits quite different behaviour in the binomial random graph. Furthermore, unlike in the case of connectedness and Hamiltonicity, the local condition is not simply a minimum degree condition.

17/02/2017 1:05 PMBancroft Road 3.01Leo Liberti (Paris)New formulationbased methods in distance geometry
The fundamental problem of distance geometry asks to find a realization of a finite, but partially specified, metric space in a Euclidean space of given dimension. Unless some structure is known about the structure of the instance, it is notoriously difficult to solve these problems computationally, and most methods will either not scale up to useful sizes, or will be unlikely to identify good solutions. We propose a new heuristic algorithm based on a semidefinite programming formulation, a diagonallydominant inner approximation of Ahmadi and Hall's, a randomizedtype rank reduction method of Barvinok's, and a call to a local nonlinear programming solver.
Short Bio:
Leo Liberti obtained his Ph.D. in Global Optimization at Imperial College London, held postdoctoral fellowships at Politecnico di Milano and Ecole Polytechnique in France, where he became a professor and vicepresident of his department. After two years as a Research Staff Member at IBM Research in New York, he moved back to Europe as a Research Director at CNRS and parttime professor at Ecole Polytechnique. His main research interests are mixedinteger nonlinear programming and distance geometry. 
24/02/2017 4:00 PMQueen's building W316Queen's building W316Record breaking Condorcet domains
The theory of rankings and voting is riddled with curious “paradoxes” related to nontransitivity. I will introduce a few new results on nontransitive dice games (joint work with Mike Paterson) and relate this to the area of Condorcet domains.
A Condorcet domain (CD) consists of a collection of linear orderings of a fixed finite set that satisfies a particular type of constraint for each 3element subset.
One fundamental problem is to construct large CDs for a given finite set of size n. Already in the 1950s some constructions of CD domains were known, and these were then improved in the mid1980s. Until recently only optimal values (9 and 20) for n=4 and n=5 were known. Recently, we showed (by heavy use of computer calculations) that the optimal values for n=6 and n=7 are 45 and 100 respectively (joint work with AkelloEgwel, Leedhamgreen, Litterrick, Markstrom). This result was already conjectured in the early 1990s. In the talk, I will present a new class of schemes for constructing large Condorcet domains that beat the 20+yearold records. I will conclude with a list of open questions for further research. 
03/03/2017 4:00 PMQueen's building W316Anthony Hilton (QMUL)Unions and intersections of finite sets
In the early 70's Daykin conjectured that a family of subsets of
{1,2,...,n} which has the intersection property (i.e. any two subsets have
a nonempty intersection) and the nonunion property (i.e the union of any
two subsets is not equal to {1,2,...,n}) contains at most 2^(n2) members.
Different solutions of this conjecture were found within the next two of
three years by Schonheim, Seymour, (Daykin and Lovasz), and Hilton.
I will discuss various applications of the proofs and some
generalizations of the result. 
10/03/2017 4:00 PMQueen's building W316Rhiannon Hall (Brunel)On the Characteristic Polynomial for the Spike Matroids
For $n\geq 3$, an {$n$spike is a matroid whose groundset can be partitioned into $n$ pairs called legs, such that the union of any two legs is both a circuit and a cocircuit. A spike may be extended by an element called a tip and/or coextended by an element called a cotip such that the union of the tip with each leg forms a triangle, and the union of the cotip with each leg forms a triad.
Spikes have arisen in many areas of matroid theory, sometimes notoriously, such as when Oxley, Vertigan & Whittle [1] used them to disprove Kahn's conjecture that the number of inequivalent representations of $3$connected matroids over any finite field $GF(q)$ would be bounded above by some value $n(q)$.I will aim this talk at a general combinatorial audience, spending some time on the widelyused geometrical representation of matroids and some of their properties. I will then present the characteristic polynomials, $\chi(M;\lambda)$, for the spike matroids (where the characteristic polynomial is a matroidal counterpart to the chromatic polynomial of a graph). I will also outline a proof that the zeros of these characteristic polynomials are bounded above by $\lambda=4$.
References
[1] Oxley, J., Vertigan, D., Whittle, G., On Inequivalent Representations of Matroids over Finite Fields. Journal of Combinatorial Theory, Series B 67, 325{343 (1996). 
17/03/2017 4:00 PMQueen's building W316Alan Sokal (NYU and UCL)Positivity of some multivariate formal power series arising from fractional powers of determinants
We prove the coefficientwise positivity for a class of multivariate formal power series that arise as fractional powers of determinants. More precisely, we show that the formal power series $1  \det(I_n  tA_n)^{1/n}$ is coefficientwise nonnegative when $A_n$ is an $n \times n$ matrix built in a suitable way out of $n^2$ independent indeterminates.
This is joint work with Alex Scott.

24/03/2017 1:16 PMQueen's building W316Farbod Shokrieh (Cornell)Graphs, potential theory, and algebraic geometry
A graph can be viewed, in many respects, as an analogue of an
algebraic curve. For example, there is a notion of "Jacobian" for
graphs.
More classically, graphs can be viewed as electrical networks.
I will discuss the interplay between these two points of view, as well
as some recent applications to problems in algebraic geometry. 
31/03/2017 4:00 PMQueen's building W316Tony Guttmann, MelbournePatternavoiding permutations and their applications
In the 1960s and 1970s computer scientists attempted to classify the most prominent data structures in terms of the permutations they could sort. That is, how many of the n! permutations of length n could be sorted, within that data structure, to give as output the identity permutation? This study then gave rise to the broader study of questions such as "how many permutations avoid a given pattern of length 3, or 4 or 5?" We review the field, and present some solutions and conjectures for previously open problems. (Joint work with Andrew Conway and Andrew ElveyPrice).

29/09/2017 4:00 PMW316, Queen's BuildingEoin Long (University of Oxford)Forbidden vectorvalued intersections
We solve a generalised form of a conjecture of Kalai motivated by attempts to improve the bounds for Borsuk’s problem. The conjecture can be roughly understood as asking for an analogue of the FranklRödl forbidden intersection theorem in which set intersections are vectorvalued. We discover that the vector world is richer in surprising ways: in particular, Kalai’s conjecture is false, but we prove a corrected statement that is essentially best possible, and applies to a considerably more general setting. Our methods include the use of maximum entropy measures, VCdimension, Dependent Random Choice and a new correlation inequality for product measures. Joint work with Peter Keevash.

06/10/2017 4:00 PMW316, Queen's BuildingJustin Ward (QMUL)Improved approximation for Kmeans in arbitrary dimension
In the general 'Kmeans problem', we are given n input points in a Euclidean space and seek to find k "center" points in the space so that the sum of the squared distances of each input point to its nearest center is minimized. While there have been several recent results for the special case in which the Euclidean space has some bounded dimension d, the best known approximation in arbitrary Euclidean spaces has remained (9+\epsilon) since 2002. In this talk I will present a new algorithm that achieves a 6.36approximation for this problem, as well as an improved 2.64 approximation for the Euclidean kmedian problem. The algorithm is based on a new Lagrangian multiplier preserving primal dual approach. This talk is based on joint work with Sara Ahmadian, Ashkan NorouziFard, and Ola Svensson (to appear in FOCS '17).

13/10/2017 4:30 PMW316, Queen's BuildingImre Leader (University of Cambridge)Decomposing the complete hypergraph
The GrahamPollak theorem asserts that, to decompose the complete graph on n vertices into complete bipartite subgraphs, we need at least n1. What happens for hypergraphs: how many complete rpartite rgraphs are needed to decompose the complete rgraph? (Joint work with Luka Milicevic and Ta Sheng Tan.)

20/10/2017 4:00 PMW316, Queen's BuildingVytautas Gruslys (University of Cambridge)Path partitions of regular graphs
We consider the problem of covering a regular graph by a small number of vertexdisjoint paths. Magnan and Martin conjectured that every kregular graph on n vertices can be partitioned into at most n / (k + 1) paths, a bound which is attained by a disjoint union of (k + 1)cliques. We prove the conjecture in the case where k is linear in n and n is large.
This talk is based on joint work with Shoham Letzter.

27/10/2017 4:00 PMQueens Building, W316David Conlon (University of Oxford)How to build a hypergraph expander
We present a simple mechanism, which can be randomised, for constructing sparse 3uniform hypergraphs with strong expansion properties. These hypergraphs are constructed using Cayley graphs over elementary abelian 2groups and have vertex degree which is polylogarithmic in the number of vertices. Their expansion properties, which are derived from the underlying Cayley graphs, include analogues of vertex and edge expansion in graphs, rapid mixing of the random walk on the edges of the skeleton graph, uniform distribution of edges on large vertex subsets and the geometric overlap property.

10/11/2017 4:00 PMW316, Queeen's BuildingAllan Lo (University of Birmingham)Hypergraph Fdesigns
We show that given any $r$uniform hypergraph $F$, the trivially necessary divisibility conditions are sufficient to guarantee an edgedecomposition of any sufficiently large complete $r$uniform hypergraph into edgedisjoint copies of $F$. The case when $F$ is complete corresponds to the existence of block designs, a problem going back to the 19th century, which was recently settled by Keevash. In particular, our argument provides a new proof of this result, which employs purely probabilistic and combinatorial methods. We also obtain several further generalizations.
This is joint work with Stefan Glock, Daniela K\"uhn and Deryk Osthus. 
24/11/2017 4:00 PMW316, Queens BuildingFelix Fischer (QMUL)TBA
TBA

01/12/2017 4:00 PMW316, Queen's BuildingNatalie Behague (QMUL)TBA
TBA

08/12/2017 4:00 PMW316, Queen's BuildingAmanda Cameron (QMUL)TBA
TBA

15/01/2010 4:30 PMM103Victor FalgasRouvryUnionclosed families of small weight

16/04/2010 5:30 PMM103Manfred Droste (Leipzig)Random constructions of countable abelian pgroups
By Ulm's theorem, countable reduced abelian pgroups are characterized, uniquely up to isomorphism, by their Ulm invariants. Given a sequence f of Ulm invariants, we provide a probabilistic construction of a countable abelian pgroup G_{f}, having the set of natural numbers as its domain, with Ulm invariants ≤ f. We then show that with probability 1, G_{f} has precisely f as its sequence of Ulm invariants. This establishes the existence part of Ulm's theorem in a probabilistic way. We also develop new results for valuated abelian pgroups which are essential for our construction.
Joint work with Ruediger Goebel (Essen).

04/06/2010 5:30 PMM103Robert Bailey (Regina)Generalised covering designs and cliquecoverings
Covering designs are a generalisation of tdesigns, where the requirement that any tsubset of points be contained in exactly λ blocks is replaced with the weaker requirement that they be contained in at least λ blocks. Covering arrays generalise orthogonal arrays in a similar manner.
In this talk, inspired by PJC's "generalised tdesigns", I will present a common generalisation of covering designs and covering arrays, as well as some methods of constructing these new designs. In particular, I'll focus on the case t=2, where there is a strong relationship with graph theory, in the form of clique coverings.
If time permits, I may also talk about the "dual" problem of generalised packing designs.

02/07/2010 4:00 PMM103Simeon Ball (UPC Barcelona)On large subsets of a finite vector space in which every subset of basis size is a basis
In this talk we consider sets of vectors S of the vector space F_{q}^{k} with the property that every subset of S of size k is a basis.
The classical example of such a set is the following.
Example. (Normal rational curve) The set
S = {(1,t,t^{2},...,t^{k1}  t∈F_{q}} ∪ {(0,,...,0,1)},
is a set of size q+1. It is easily shown that S has the required property by checking that the k×k Vandermonde matrix formed by k vectors of S has nonzero determinant.
For q even and k=3, one can add the vector (0,1,0) to S and obtain an example with q+2 vectors. For these parameters, such a set of q+2 vectors is called a hyperoval, and these have been studied extensively. There are many examples of hyperovals known which are not equivalent (up to change of basis and field automorphisms) to the example above. The only other known examples of size q+1 are an example of size 10 in F_{9}^{5}, due to Glynn, and an example in F_{2^h}^{4} due to Hirschfeld.
The following conjecture exists in various areas of combinatorics. It is known as the main conjecture for maximum distance separable codes, the representability of the uniform matroid in matroid theory, the embeddability of the complete design in design theory, and Segre's arcs problem in finite geometry.
Conjecture. A set of vectors S of the vector space F_{q}^{k}, with k≤q–1, with the property that every subset of S of size k is a basis, has size at most q+1, unless q is even and k=3 or k=q–1, in which case it has size at most q+2.
I shall present a proof of the conjecture for q prime and discuss the nonprime case. I shall also explain how to then prove the following theorem, which is a generalisation of Segre's "oval is a conic" theorem in the case k=3.
Theorem. If p≥k, then a set S of q+1 vectors of the vector space F_{q}^{k} with the property that every subset of S of size k is a basis, is equivalent to a normal rational curve, where q=p^{h}.

19/11/2010 4:30 PMM103Andy DrizenGenerating uniformly distributed random 2designs with block size 3
Jacobson and Matthews introduced the most hopeful method known for eﬃciently generating uniformly distributed Latin squares. I will discuss how the same methods can be extended to generate uniformly distributed generalisations of Latin squares and lambdafactorisations of the complete graph at random.

04/03/2011 5:00 PMM103Heidi Gebauer (ETH)Game theoretic Ramsey numbers
The Ramsey Number, R(k), is defined as the minimum N such that every 2coloring of the edges of K_{N} (the complete graph on N vertices) yields a monochromatic kclique. For 60 years it is known that 2^{k/2} < R(k) < 4^{k}, and it is a widely open problem to find significantly better bounds.
In this talk we consider a game theoretic variant of the Ramsey Numbers: Two players, called Maker and Breaker, alternately claim an edge of K_{N}. Maker's goal is to completely occupy a K_{k} and Breaker's goal is to prevent this. The game theoretic Ramsey Number R′(k) is defined as the minimum N such that Maker has a strategy to build a K_{k} in the game on K_{N}.
In contrast to the ordinary Ramsey Numbers, R′(k) has been determined precisely – a result of Beck. We will sketch a new, weaker result about R′(k) and use it to solve some related open problems.

02/03/2012 4:30 PMM103Sasha GnedinBlock characters of the symmetric groups
Block character of a finite symmetric group is a positive definite function which depends only on the number of cycles in permutation. We describe the cone of block characters by
identifying its extreme rays, and find relations of the characters to descent representations and the co invariant algebra of Sym_{n}. The decomposition of extreme block characters into the sum of characters of irreducible representations gives rise to certain limit shape theorems for random Young diagrams. We also study counterparts of the block characters for the infinite symmetric group Sym_{∞}, along with their connection to the Thoma characters of the infinite linear group GL_{∞}(q) over a Galois field. 
23/03/2012 4:00 PMM103Celia Glass (City) Peter CameronAcyclic orientations of graphs, 1
Acyclic orientations of graphs have a number of applications, including a heuristic for graph colouring. We will discuss why we are interested in them and some investigations. Stanley showed that the number of acyclic orientations of a graph is, apart from sign, the evaluation of the chromatic polynomial at −1. There is a recurrence for the average number of acyclic orientations of a graph with a given number of vertices and edges; we would like to have further information on this distribution (for example, the variance). Given two acyclic orientations, it is possible to move from one to the other by reversing only the edges whose orientations differ, preserving acyclicity at each step. This gives rise to various Markov chains for choosing at random. The rate of convergence of these is an open problem.

04/05/2012 5:30 PMM103Benny Sudakov (UCLA)The phase transition in random graphs  a simple proof
The classical result of Erdős and Rényi shows that the random graph G(n,p) experiences sharp phase transition around p = 1/n – for any ε>0 and p = (1ε)/n, all connected components of G(n,p) are typically of size O(log n), while for p = (1+ε)/n, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime p = (1+ε)/n, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games.
Joint work with M. Krivelelvich.

01/06/2012 5:30 PMM103Peter CameronCounting colourings
The chromatic polynomial P_{X}(q) of a graph X has the property that its value at a positive integer q is the number of proper colourings of the graph with q colours. However, the number it gives you may not be the number you want, for two reasons:
 it doesn't allow for the fact that different colourings may be equivalent under an automorphism of the graph;
 the order of the colours is significant, whereas you may want to count the partitions of the graph into independent sets.
I will present separate solutions for these two problems; one uses the orbital chromatic polynomial, while the other is a simple inclusionexclusion argument. However, combining the two methods to count partitions into independent sets up to automorphisms is an unsolved problem.
Another feature of the chromatic polynomial is that substituting −1 for q counts the number of acyclic orientations of the graph. It turns out that substituting −1 for q in the orbital chromatic polynomial does not count orbits on acyclic orientations; but there is a "twisted" version of the orbital chromatic polynomial which does this job.
These things will be illustrated by means of the Petersen graph.

09/11/2012 4:30 PMM103Laszlo Vegh (LSE)Approximating minimum cost knodeconnected spanning subgraphs
Given an undirected graph with costs on the edges and a positive integer k, consider the problem of finding a minimum cost spanning subgraph that is knodeconnected. We present a 6approximation algorithm for this NPcomplete problem, assuming that the number of nodes is at least k^{3}(k−1)+k. This gives the first constant factor approximation for the problem.
For edgeconnectivity variants, constant factor approximation can be achieved using the iterative rounding of the linear programming relaxation, a powerful technique developed by Jain. Whereas it has been long known that iterative rounding cannot yield a constant factor approximation for nodeconnectivity on arbitrary input graphs, we show that it does give a 2approximation for a restricted class of instances. We apply a combinatorial preprocessing, based on the Frank–Tardos algorithm for koutconnectivity, to transform any input into such an instance. This is a joint work with Joseph Cheriyan.

23/11/2012 4:30 PMM103Fatima Affiff Chaouche (University of Sciences and Technology Houari Boumediene, Algiers)Pancyclicity when each cycle must pass exactly k Hamilton cycle chords
We observe that Ω(log n) chords must be added to an ncycle to produce a pancyclic graph; we ask how much this must be increased in order that, given k with 3≤k≤n, there exists a cycle of each length ≥k which passes exactly kchords. We find that, for fixed k, the bound becomes Ω(n^{1/k}).

18/01/2013 4:30 PMM103Peter CameronSynchronizing nonuniform maps
A finite deterministic automaton is synchronizing if there is a sequence of transitions which ends up at the same state no matter which state we start from.
There has been a lot of interest in the case where the transitions of the automaton consist of the generators of a permutation group G and a single nonpermutation f: I will say that G synchronizes f if ⟨G,f⟩ is synchronizing.
It is known that a permutation group which synchronizes every nonpermutation is primitive, but the converse is false. An important theorem of Rystsov asserts that a group of degree n is primitive if and only if it synchronizes every map of rank n−1; also, a primitive group synchronizes any map of rank 2. João Araújo has conjectured that a primitive group synchronizes every nonuniform map (one whose kernel classes do not all have the same size).
I will report on some progress on this conjecture that João and I made last month, including an improvement of Rystsov's theorem from n−1 to n−2.

15/02/2013 4:30 PMM103Andrew TreglownYet another talk on perfect matchings in hypergraphs
Last term Peter Keevash and Fiachra Knox both gave talks on perfect matchings in hypergraphs. In this selfcontained talk we look at the problem of establishing minimum degree conditions which force a hypergraph to contain a perfect matching.
Indeed, given positive integers k and r with k/2 ≤ r ≤ k−1, we give a minimum rdegree condition that ensures a perfect matching in a kuniform hypergraph. This condition is best possible and improves on work of Pikhurko, who gave an asymptotically exact result. Our approach makes use of the absorbing method.
This is joint work with Yi Zhao (Georgia State University).

22/03/2013 5:30 PMM103Jan VolecA problem of Erdos and Sos on 3graphs
We show that for every ε>0 there exist δ>0$ and n_{0}∈N such that every 3uniform hypergraph on n≥n_{0} vertices with the property that every kvertex subset, where k≥δn, induces at least (1/4+ε){k choose 3} edges, contains K_{4}^{−} as a subgraph, where K_{4}^{−} is the 3uniform hypergraph on 4 vertices with 3 edges. This question was originally raised by Erdős and Sós. The constant 1/4 is the best possible.
This is a joint work with Roman Glebov and Dan Kral.

03/05/2013 5:30 PMM103Jeroen Schillewaert (Imperial College)Small maximal partial ovoids in generalized quadrangles
A maximal partial ovoid of a generalized quadrangle is a maximal set of points no two of which are collinear. The problem of determining the smallest size of a maximal partial ovoid in quadrangles has been extensively studied in the literature. In general, theoretical lower bounds on the size of a maximal partial ovoid in a quadrangle of order (s,t) are linear in s. I will discuss a simple probabilistic construction of a maximal partial ovoid of size at most s(log s)^{α} for a large class of quadrangles.

25/10/2013 5:30 PMM103Peter CameronCombinatorial YangBaxter
This is a rehearsal for a talk I will give at a meeting on Combinatorics and Physics in Cardiff the week after the end of term.
A combinatorial (or settheoretic) solution of the Yang–Baxter equation is a set X (usually finite) and a function r:X^{2}→X^{2} satisfying the braiding condition on X^{3}. With some other natural assumptions, combinatorial solutions give rise to abstract groups and permutation groups, related by homomorphism. The groups are soluble, and the derived length of the abstract group is one greater than that of the permutation group.
This is joint work with Tatiana GatevaIvanova, but I will be concentrating on the parts where I had some input.

21/11/2014 4:30 PMM103Oleg Pikhurko (University of Warwick)Measurable circle squaring
In the early 1990's Laczkovich showed that, for any two sets A and B in
R^n with the same nonzero Lebesgue measure and with boundary of box
dimension less than n, there is a partition of A into finitely many
parts that can be translated by some vectors to form a partition of B.
In particular, this resolved the longstanding Tarki's circle squaring
problem.We show that, in Laczkovich' theorem, one can additionally require
that all parts are Lebesgue measurable. This is a joint work with
András Máthé and Łukasz Grabowski. 
23/11/2015 5:00 PMM203Yufei Zhao (University of Oxford)Large deviations in random graphs
What is the probability that the number of triangles in an Erdős–Rényi random graph exceeds its mean by a constant factor? In this talk, I will discuss some recent progress on this problem.
Already the order in the exponent of the tail probability was a long standing open problem until several years ago when it was solved by DeMarco and Kahn, and independently by Chatterjee. We now wish to determine the exponential rate of the tail probability. Thanks for the works of ChatterjeeVaradhan (dense setting) and ChatterjeeDembo (sparse setting), this large deviations problem reduces to a natural variational problem. We solve this variational problem asymptotically, thereby determining the large deviation rate, which is valid at least for p > 1/n^c for some c > 0.
Based on joint work with Bhaswar Bhattacharya, Shirshendu Ganguly, and Eyal Lubetzky.

22/01/2016 4:00 PMM103 (Mathematical Sciences)Nick Day (QMUL)Colourings with no Short Odd Cycles
We show that for any positive integer r there exists an integer k and a kcolouring of the complete graph K_{2^{k} + 1} such that the colouring contains no monochromatic odd cycle of length less than r. This answers a question of Erdős and Graham. We use these colourings to give new lower bounds on the kcolour Ramsey number of the odd cycle and prove that, for all odd r and all k sufficiently large, there exists a constant c = c(r) > 0 such that the kcolour Ramsey number of C_{r} is at least (r1)(2+c)^{k1}.
This is joint work with Robert Johnson.

05/02/2016 4:00 PMM103 (Mathematical Sciences)Ginestra Bianconi (QMUL)Equilibrium and nonequilibrium models of complex network geometry
Network geometry aims at characterizing networks by means of geometrical tools and concepts. Network geometry is fundamental for systems as different as the brain or the quantum universe. After a broad overview of this field, recent works on network geometry will be presented. Here network geometry is modelled by means of simplicial complexes constructed not only by nodes and links but also by triangles and higher dimensional simplices. We will introduce Complex Quantum Network Manifolds (CQNM) describing the nonequilibrium evolution of growing simplicial complexes of dimension d. We show that in d=2 CQNM are homogeneous networks while for d >2 they are scalefree i.e. they are characterized by large inhomogeneities of degrees like most complex networks. From the selforganized evolution of CQNM quantum statistics emerge spontaneously. Here we define the generalized degrees associated with the faces of the ddimensional CQNMs, and we show that the statistics of these generalized degrees can either follow FermiDirac, Boltzmann or BoseEinstein distributions depending on the dimension of the faces. A generalisation of these models called network geometry with flavor will be presented. Finally ensembles of simplicial complexes of dimension d will be characterized, in particular the configuration model of simplicial complexes and the canonical ensemble. The entropy of these ensembles will be given and the asymptotic expression for the number of simplicial complexes in the configuration model will be discussed.

03/11/2017 4:00 PMW316, Queen's BuildingHakan Guler (QMUL)Rigidity of linearly constrained frameworks
A linearly constrained framework in ddimensions is a ddimensional barandjoint framework such that each vertex is allowed to move on a specific hyperplane. We denote linearly constrained frameworks by a triple (G, p, q) where G = (V, E) is a graph, p : V → R^d is the realisation map for the vertices, and q : V → R^d is the map that assigns unit vectors to the vertices that are normal to the associated hyperplanes. A linearly constrained framework is rigid if the only continuous motion of the vertices which satisfies the hyperplane constraints for the vertices and the length constraints for the edges, is the trivial motion which keeps each vertex fixed. We say that (G, p, q) is generic if (p, q) is algebraicly independent over the rationals. Streinu and Theran characterised generic rigidity of linearly constrained frameworks in R^2. In this talk we will give a characterisation for generic rigidity of linearly constrained frameworks in R^3. This is joint work with Bill Jackson.

17/11/2017 4:00 PMW316, Queens BuildingJohn Haslegrave (University of Warwick)Hamilton spheres in 3uniform hypergraphs
Dirac's theorem states that any nvertex graph with minimum degree at least n/2 contains a Hamilton cycle. Rödl, Ruciński and Szemerédi showed that asymptotically the same bound gives a tight Hamilton cycle in any kuniform hypergraph, where in this case "minimum degree" is interpreted as the minimum codegree, i.e. the minimum over all (k1)sets of the number of ways to extend that set to an edge. The notion of a tight cycle can be generalised to an lcycle for any l < k, and corresponding results for lcycles were proved independently by Keevash, Kuhn, Mycroft and Osthus and by Han and Schacht, and extended to the full range of l by Kuhn, Mycroft and Osthus. However, lcycles are essentially onedimensional structures. A natural topological generalisation of Hamilton cycles in graphs to higherdimensional structures is to ask for a spanning triangulation of a sphere in a 3uniform hypergraph. We give an asymptotic Diractype result for this problem. Joint work with Agelos Georgakopoulos, Richard Montgomery and Bhargav Narayanan.

07/12/2017 4:00 PMW316, Queens BuildingFelix FischerTruthful Outcomes from NonTruthful Position Auctions
The area of mechanism design in economics is concerned with algorithms that produce good outcomes given inputs from selfinterested individuals. One of the stars of mechanism design theory is the VickreyClarkeGroves (VCG) mechanism, which makes it optimal for each individual to truthfully reveal its input. In practice the VCG mechanism is used with surprising rarity and the mechanisms we actually find are nontruthful. An example of this phenomenon are position auctions used by internet search engines to allocate space for advertisements displayed next to genuine search results. Here only nontruthful mechanisms have ever been used, and what in theory looks like a beginner's mistake was a huge commercial success. An obvious advantage of the nontruthful mechanisms is that they use simpler payments, and it has been known for some time why they do not produce chaos when participants decide strategically how to bid. We will see that the simplicity of payments also comes with a greater robustness to uncertainty on part of the search engines regarding the relative values of positions. This talk is based on joint work with Paul Dütting (LSE) and David C. Parkes (Harvard).

01/12/2017 4:00 PM316, Queen's BuildingNatalie Behague (QMUL)Hypergraph Saturation Irregularities
We say that a graph G is saturated with respect to some graph F if G doesn't contain any copies of F but adding any new edge to G creates some copy of F. The saturation number sat(F,n) is the minimum number of edges an Fsaturated graph on n vertices can have. This forms an interesting counterpoint to the Turan number; the saturation number is in many ways less wellbehaved. For example, Tuza conjectured that sat(F,n)/n must tend to a limit as n tends to infinity and this is still open. However, Pikhurko disproved a strengthening of Tuza's conjecture by finding a finite family of graphs, whose saturation number divided by n does not tend to a limit. We will prove a similar result for hypergraphs and discuss some variants.

08/12/2017 4:00 PMW316, Queen's BuildingAmanda Cameron (Max Planck Institute, Leipzig)An Ehrhart theory generalisation of the Tutte polynomial
The Tutte polynomial is one of the most important and wellknown graph polynomials, and also features prominently in matroid theory. It is however not directly applicable to polymatroids, these being a natural generalisation of matroids. For instance, deletioncontraction properties do not hold. We construct a polynomial for polymatroids which behaves similarly to the Tutte polynomial of a matroid, and in fact contains the same information as the Tutte polynomial when we restrict to matroids. This is based on joint work with Alex Fink

12/01/2018 4:00 PMQueens' Building, Room W316Peter Cameron (St Andrews)Equitable partitions of Latin square graphs
A partition of a graph $G$ is equitable if, for any two parts $P_i$ and $P_j$ (possibly equal) and $x\in P_i$, the number $p_{ij}$ of neighbours of $x$ in $P_j$ depends only on $i$ and $j$ and not on $x$. It is easy to show that the spectrum of the matrix $(p_{ij})$ is contained in the spectrum of the graph.
Given a Latin square $L$ of order $n$, the corresponding Latin square graph has as vertex set the set of cells of the square, with two vertices joined if they lie in the same row or column or contain the same letter. Its eigenvalues are $3(n1)$, $n3$ and $3$. We have proved that in an equitable partition of a Latin square graph whose matrix does not have $3$ as an eigenvalue, each part is a union of rows, or of columns, or of letters, or of inflations of corner sets in Cayley tables of cyclic groups. I will also discuss some variants and generalisations.
This is joint work with Rosemary Bailey (QMUL/St Andrews) and Sergey Goryainov (Shanghai Jiao Tong University).

19/01/2018 4:00 PMQueens' Building, Room W316Simon Blackburn (RHUL)Private information retrieval
In the classical Private Information Retrieval (PIR) model, a user stores some data on a collection of servers and later wishes to retrieve a single bit of that data. This should be done without any individual server knowing which bit is being retrieved. The aim is to design a protocol that minimises the amount of communication between the user and servers. Variations of this model have been studied recently, motivated by applications in distributed storage. I will give a brief introduction to the area, and I will present some recent constructions and open problems. No knowledge of cryptography or distributed storage is required.

26/01/2018 4:00 PMQueens' Building, Room W316Natasha Morrison (Cambridge)Maximising the number of induced cycles
How many induced cycles can a graph on n vertices contain? For sufficiently large n, we determine the maximum number of induced cycles and the maximum number of even or odd induced cycles. We also characterize the graphs achieving this bound in each case. This answers a question of Tuza, and a conjecture of Chvátal and Tuza from 1988. Joint work with Alex Scott.

02/02/2018 4:00 PMQueens' Building Room W316Robert Johnson (QMUL)Voronoi games in the hypercube
The subject of spatial voting considers how candidates compete for vote share in a society whose opinions can be expressed in some geometric opinion space. The most classical result here is the Median Voter Theorem which describes the case when opinions lie in a 1dimensional interval. In higher dimensions the situation is much more complicated and there is no analogue of the Median Voter Theorem.
We investigate what can be said when the opinion space is the discrete hypercube (corresponding to d binary issues). This discrete model has been much less studied than the continuous ones and leads to some appealing problems in the combinatorics of the hypercube. We exhibit some intriguing behavior, results and open questions.Joint Work with Nicholas Day

09/02/2018 4:00 PMQueens' Building, Room W316Ivan Tomasic (QMUL)Graphons arising from graphs definable over finite fields
We prove a version of Tao's algebraic regularity lemma for asymptotic classes in the context of graphons. We apply it to study expander difference polynomials over fields with powers of Frobenius. This is joint work with Mirna Dzamonja (UEA).

16/02/2018 4:00 PMQueens' Building, Room W316László A. Végh (LSE)A ConstantFactor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
We give a constantfactor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constantfactor approximation algorithm for the special case of nodeweighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from nodeweighted metrics. For those instances, we then solve LocalConnectivity ATSP, a problem known to be equivalent (in terms of constantfactor approximation) to the asymmetric traveling salesman problem. This is joint work with Ola Svensson and Jakub Tarnawski.

23/02/2018 4:00 PMQueens' Building, Room W316Taoyang Wu (University of East Anglia)Distances on Evolutionary (Phylogenetic) Trees: Maximum Parsimony and Treewidth
In evolutionary biology, distances are often used to measure the incongruence between a pair of phylogenetic trees (i.e., leaflabelled trees) that are reconstructed by different methods or using different regions of genome. In this talk we discuss several combinatorial and algorithmic results concerning two recently introduced tree distances: one motivated by the maximum parsimony principle in evolutionary tree inference, and the other by the concept of treewidth in graph theory.

02/03/2018 4:00 PMQueens' Building, Room W316Nicholas Day (Umeå University)MakerBreaker percolation games
The (p,q)MakerBreakerpercolation game is played by two players, Maker and Breaker, who take turns claiming edges from the twodimensional integer lattice. On each of their turns Maker claims p different unclaimed edges, while on each of their turns Breaker claims q different unclaimed edges. Maker's aim is to build arbitrarily long paths from the origin of the lattice, while Breaker's aim is to prevent this from happening. We say that Maker wins the game if they can guarantee that, among the set of unclaimed edges and edges that Maker has claimed, there is always a path from the origin escaping to infinity.
In this talk we will discuss such MakerBreakerpercolation games and give a number of results for when Maker or Breaker can win. To do this we will look at and discuss certain MakerBreaker crossing games. These games are similar to the above percolation games, except that they are played on finite two dimensional grids and Maker's aim is to create a path of edges that crosses from the left side of the grid to the right side. We will give a number of results for such MakerBreaker crossing games, show how they relate back to the original percolation games, and discuss how they are related to the combinatorial games of Hex, Bridgit and the Shannon switching game.
This talk is based on joint work with Victor FalgasRavry. 
09/03/2018 4:00 PMQueens' Building, Room W316Imre Bárány (UCL)Theorems of Caratheodory and Tverberg without dimensionCaratheodory's classic result says that if a point $a$ lies in the convex hull of a set $P \subset R^d$, then it lies in the convex hull of a subset $Q \subset P$ of size at most $d+1$. What happens if we want a subset $Q$ of size $k < d+1$ such that $a \in conv Q$? In general, this is impossible as $conv Q$ is too low dimensional. We offer some remedy: $a$ is close to $conv Q$ for some subset $Q$ of size $k$, in an appropriate sense. Similar results hold for Tverberg's theorem as well. This is joint work with Nabil Mustafa.

23/03/2018 4:00 PMQueens' Building, Room E303Standa Živný (Oxford)Homomorphisms and generalisations seen from both sides
The topic of this talk is the computational complexity of the homomorphism problem between two relational structures, also known as the constraint satisfaction problem (CSP). We briefly discuss the known classifications of CSPs parametrised by the source or target structures. We then discuss a classification of generalvalued CSPs parametrised by the source structures. Based on joint work with Clement Carbonnel and Miguel Romero.

18/05/2018 4:00 PMQueens' Building Room W316Noam Lifshitz (Bar Ilan University)The Junta Method for HypergraphsNumerous problems in extremal hypergraph theory ask to determine the maximal size of a kuniform hypergraph on n vertices that does not contain an 'enlarged' copy H^+ of a fixed hypergraph H. These include wellknown problems such as the ErdősSós 'forbidding one intersection' problem and the FranklFüredi 'special simplex' problem.In this talk we present a general approach to such problems, using a 'junta approximation method' that originates from analysis of Boolean functions. We prove that any (H^+)free hypergraph is essentially contained in a 'junta'  a hypergraph determined by a small number of vertices  that is also (H^+)free, which effectively reduces the extremal problem to an easier problem on juntas. Using this approach, we obtain, for all C<k<n/C, a complete solution of the extremal problem for a large class of H's, which includes the aforementioned problems, and solves them for a large new set of parameters.Based on joint works with David Ellis and Nathan Keller

04/05/2018 4:00 PMQueens' Building Room W316Nick Wormald (Monash)The degree sequence of a random graph, and asymptotic enumeration of regular graphs
The distribution of the degree sequence of a random graph has been studied since the original papers on random graphs by Erdos and Renyi. About 25 years ago, results on asymptotic enumeration of graphs with given degree sequence prompted McKay and the speaker to conjecture a simple model for the degree sequence of a random graph. I will discuss the recent resolution of this conjecture, which was joint work with Anita Liebenau, and related results.

25/05/2018 4:00 PMQueens' Building, Room W316István Tomon (EPFL)Partitioning the Boolean lattice into long chains
By the well known theorem of Sperner, the minimum number of chains the Boolean lattice (2[n], \subset) can be partitioned into is \binom{n}{\floor{n/2}}. There are many ways to construct such a chain partition, however, most of these partitions contain long and short chains at the same time. A conjecture of Furedi asks if there exists a partition of 2[n] into \binom{n}{\floor{n/2}} chains such that the difference between the size of any two chains is at most 1.
While this conjecture is still open, we managed to construct a chain partition, where the size of every chain is \Theta(\sqrt{n}). More interestingly, it turns out that these chain partitions have applications in certain extremal set theory problems. We outline our results concerning the conjecture of Furedi and discuss the possible applications in more detail.

11/05/2018 4:00 PMQueens' Building, Room W316Rhys Evans (QMUL)Neumaier Graphs
A clique in a graph is a regular clique if every vertex not in the clique is adjacent to the same number of vertices inside the clique. In the early 1980's, Neumaier studied the existence of regular cliques in edgeregular graphs. The examples of edgeregular graphs with regular cliques that Neumaier knew of were all strongly regular graphs, so he asked if there exist edgeregular, nonstrongly regular graphs containing regular cliques. With this as motivation, we define a Neumaier graph as an edgeregular, nonstrongly regular graph containing a regular clique. We will discuss the answer to Neumaier's question, and then focus on the determination of the smallest Neumaier graph. No prior knowledge of edgeregular or strongly regular graphs is assumed.

01/06/2018 4:00 PMQueens' Building, Room W316Matt Fayers (QMUL)An interesting family of posets
I have discovered a family of finite posets which arise in representation theory. Remarkably, they can be defined in six quite different but equivalent ways. I will give all six definitions and some basic properties of these posets. Only very elementary theory of posets will be assumed.

08/06/2018 4:00 PMQueens' Building, Room W316William Raynaud (QMUL)Smallest cyclically covering subspaces of $\mathbb{F}_q^n$We say a subspace $U$ of ${\mathbb{F}_q^n}$ is {\em cyclically covering} if the union of the cyclic shifts of $U$ is equal to $\mathbb{F}_q^n$. We investigate the problem of determining the minimum possible dimension of a cyclically covering subspace of $\mathbb{F}_q^n$. (This is a natural generalisation of a problem posed by Peter Cameron.)We prove several upper and lower bounds, and we answer the question completely for all $n$ and $q$ such that $n=q^d1$ for some $d \in \mathbb{N}$. If time permits, we will briefly discuss extensions to more general group representations.We use arguments from combinatorics, representation theory and Galois theory.Based on joint work with Peter Cameron (St Andrews) and David Ellis (QMUL).

05/10/2018 4:00 PMQueens' Building: Room W316Eoin Long (Oxford)Cyclecomplete Ramsey numbers
The Ramsey number $r(C_{\ell},K_n)$ is the smallest natural number $N$ such that every red/blue edgecolouring of a clique of order $N$ contains a red cycle of length $\ell$ or a blue clique of order $n$. In 1978, Erd\H{o}s, Faudree, Rousseau and Schelp conjectured that $r(C_{\ell},K_n) = (\ell1)(n1)+1$ for $\ell \geq n\geq 3$ provided $(\ell,n) \neq (3,3)$. In this talk I will discuss a recent proof of this conjecture for large $\ell$, and a strong form of a conjecture due to Nikiforov, showing that $r(C_{\ell},K_n) = (\ell1)(n1)+1$ provided $\ell \geq \frac {C\log n}{\log \log n}$, for some absolute constant $C>0$. Up to the value of $C$ this is tight, and answers two further questions of Erd\H{o}s et al. up to multiplicative constants.
Joint work with Peter Keevash and Jozef Skokan. 
12/10/2018 4:00 PMQueens' Building, Room W316Jon Noel (Warwick)Supersaturation in PosetsSperner's Theorem is a classical result which says the largest antichain in {0,1}^n is precisely one of the "middle levels". Kleitman extended Sperner's Theorem by proving that, for 1<=m<=2^n, there is a subset of {0,1}^n of size m which minimises the number of "comparable pairs" and consists of m elements which are as close to the middle level as possible. This can be viewed as a "supersaturation" result for the boolean lattice; it has found various applications via the container method.In this talk, we focus on supersaturation problems in {0,1,2}^n. As it turns out, the natural analogue of Kleitman's result is false in this setting. Our main result provides an approximate quantitative form of Kleitman's result in {0,1,2}^n. As in the boolean case, we combine this result with the container method (in a standard way) to obtain certain enumerative and probabilistic results. Joint work with Alex Scott and Benny Sudakov.

19/10/2018 4:00 PMQueens' Building, Room W316Hannah Guggiari (Oxford)Size reconstructibility of graphs
The deck of a graph G is given by the multiset of (unlabelled) subgraphs \{Gv:v\inV(G)\}. The subgraphs Gv are referred to as the cards of G. Brown and Fenner recently showed that, for n\geq29, the number of edges of a graph G can be computed from any deck missing 2 cards. We will show that, for sufficiently large n, the number of edges can be computed from any deck missing at most 1/20 \sqrt{n} cards. This result is joint work with Alex Scott and Carla Groenland.

26/10/2018 4:00 PMQueens' Building, Room W316David Conlon (Oxford)The Ramsey number of books
We show that in every twocolouring of the edges of the complete graph $K_N$ there is a monochromatic $K_k$ which can be extended in at least $(1 + o_k(1))2^{k}N$ ways to a monochromatic $K_{k+1}$. This result is asymptotically best possible, as may be seen by considering a random colouring. Equivalently, defining the book $B_n^{(k)}$ to be the graph consisting of $n$ copies of $K_{k+1}$ all sharing a common $K_k$, we show that the Ramsey number $r(B_n^{(k)}) = 2^k n + o_k(n)$. In this form, our result answers a question of Erd\H{o}s, Faudree, Rousseau and Schelp and establishes an asymptotic version of a conjecture of Thomason.

02/11/2018 4:00 PMQueens' Building, Room W316Bill Jackson (QMUL)Rigidity of Graphs and Frameworks
The first reference to the rigidity of frameworksin the mathematical literature occurs in a problem posed by Euler in 1776. Consider a polyhedron P in 3space. We view P as a `panelandhinge framework' in which the faces are 2dimensional panels and the edges are 1dimensional hinges. The panels are free to move continuously in 3space, subject to the constraints that the shapes of the panels and the adjacencies between themare preserved, and that the relative motion between pairs of adjacent panels is a rotation about their common hinge. The polyhedron P is rigid if every such motion results in a polyhedron which is congruent to P.
Euler conjectured that every polyhedron is rigid. This conjecture was verified for the case when P is convex by Cauchy in 1813. Gluck showed in 1975 that it is true when P is `generic' i.e. there are no algebraic dependencies between the coordinates of the vertices of P. Connelly finally disproved the conjecture in 1982 by constructing a polyhedron which is not rigid.
I will describe results and open problems concerning the rigidity of various other types of frameworks. I will be mostly concerned with the generic case for which the problem of characterizing rigidity usually reduces to pure graph theory.

16/11/2018 4:00 PMQueens' Building, Room: W316John Talbot (UCL)Entropy compression and hypergraph transversalsThe density Turan problem was first considered by Bondy, Shen, Thomasse and Thomassen. They proved that any subgraph of a large blowup of a triangle, in which the edge density between each pair of vertex classes is greater than the inverse of the golden ration, must contain a triangle.We consider the analogous problem for a general kuniform hypergraph H: given a subgraph G of a large blowup of H, what density conditions guarantee the existence of a copy of H as a transversal of G?Using an entropy compression argument we are able to give general bounds for a kgraph $H$ with order $h$ and maximum degree $D$ of the form $11/(Dc(h,k))$. Where c(h,k) is the exponential growth rate of Dyck paths of height at most $h1$ and steps {+1,(k1)}. This growth rate is in turn given by computing the smallest real root of a generalised FIbonacci polynomial. In the case of $k=2$ (i.e. graphs) we recover a bound due to Nagy.This is joint work with Adam Sanitt.

23/11/2018 4:00 PMQueens' Building, Room W316Tamas Makai (QMUL)Supersaturation Problem for the Bowtie
The Tur\'an function $ex(n,F)$ denotes the maximal number of edges in an $F$free graph on $n$ vertices. However once the number of edges in a graph on $n$ vertices exceeds $ex(n,F)$, many copies of $F$ appear. We study the function $h_F(n,q)$, the minimal number of copies of $F$ in a graph on $n$ vertices with $ex(n,F)+q$ edges. The value of $h_F(n,q)$ has been extensively studied when $F$ is colour critical. We consider a noncolourcritical graph, namely the bowtie and establish bounds on $h_F(n,q)$ when $q=o(n^2)$.
This is joint work with Mihyun Kang and Oleg Pikhurko.

30/11/2018 4:00 PMQueens' Building, Room W316Peter J. Cameron (St Andrews)Trees, cycles and chocolate bars
By Cayley's theorem, the number of trees on the vertex set $\{1,\ldots,n\}$ is
$n^{n2}$. In such a tree, we can regard each edge as a transposition. If
we multiply together these transpositions (in any order), we obtain an
$n$cycle. (The simple proof resembles the argument to show the number of
breaks needed to convert a chocolate bar into separate squares.) Since there
are $(n1)!$ orderings of the edges, and $(n1)!$ cycles, all conjugate, one
might first think that a given tree produces each cycle exactly once. However,
this is false; the only trees for which it holds are stars.
So one can ask about the number and distribution of cycles produced by a given
tree, and (the inverse problem) the number of trees which give rise to a given
cycle. We have some results on these questions. An interesting feature is the
appearance of some famous combinatorial sequences such as the Euler numbers
and the FussCatalan numbers.
This is joint work with St Andrews undergraduate Liam Stott, done during his
summer research internship last summer.

07/12/2018 4:00 PMQueens' Building, Room W316No seminar.No seminar.
No Seminar.

09/11/2018 3:00 PMQueens' Building, Room: W316Julia Boettcher (LSE)Perfectly packing degenerate graphs with many leaves
A perfect packing of a family $(G_i)_{i\in[m]}$ of graphs in a host graph $H$ is a colouring of the edges of $H$ with colours $[m]$ such that the edges with colour $i$ form a copy of $G_i$ for each $i\in[m]$. We show that for large $n$ we can perfectly pack any family $(G_i)_{i\in[m]}$ of $d$degenerate graphs with maximum degree at most $cn/\log n$ into~$K_n$ if $\sum e(G_i)=n(n1)/2$ and if for $i\ge m\eta n$ we have $v(G_i)\le(1\eta)n$ and that~$G_i$ has at least $\eta n$ leaves.
This is joint work with Peter Allen, Dennis Clemens, Anusch Taraz.

09/11/2018 4:00 PMQueens' Building, Room: W316Katharina Jochemko (KTH, Stockholm)Combinatorial Positive Valuations
Valuations are a classical topic in convex geometry. The volume plays an
important role in many structural results, such as Hadwiger’s famous
characterization of continuous, rigidmotion invariant valuations on
convex bodies. Valuations whose domain is restricted to lattice
polytopes are less wellstudied. The BetkeKneser Theorem establishes a
fascinating discrete analog of Hadwiger’s Theorem for latticeinvariant
valuations on lattice polytopes in which the number of lattice points —
the discrete volume — plays a fundamental role. In this talk, we explore
striking parallels, analogies and also differences between the world of
valuations on convex bodies and those on lattice polytopes with a focus
on positivity questions and links to Ehrhart theory. 
14/12/2018 4:00 PMQueens' Building, Room: W316Fiona Skerman (Uppsala)Guessing numbers of odd cyclesFor a given number of colours, $s$, the guessing number of a graph is the base $s$ logarithm of the size of the largest family of colourings of the vertex set of the graph such that the colour of each vertex can be determined from the colours of the vertices in its neighbourhood. We show that, for any given integer $s > 2$, if a is the largest factor of $s$ less than or equal to $\sqrt{s}$, for sufficiently large odd $n$, the guessing number of the cycle $C_n$ with $s$ colours is $(n − 1)/2 + log_s (a)$. This answers a question posed by Christofides and Markström in 2011.Guessing numbers are related to index coding and our results show that the information defect of the coding problem where the side information is a large odd cycle is $(n + 1)/2− log_s(a)$. Joint work with Ross Atkins and Puck Rombach.

11/01/2019 4:00 PMQueens' Building, Room W316Madeline Brandt (Berkeley)Computing Berkovich skeleta of curves
Given a smooth curve defined over a valued field, it is a difficult problem to compute the Berkovich skeleton of the curve. In theory, one can find a semistable model for the curve and then find the dual graph of the special fiber, and this will give the skeleton. In practice, these procedures are not algorithmic and finding the model can become difficult. In this talk, we present a method for doing this in the case of superelliptic curves y^n=f(x). The solution is combinatorial and involves studying the covering from the curve to $\mathbb{P}^1$, and recovering data about the Berkovich skeleton from the tropicalization of $\mathbb{P}^1$ together with the marked ramification points. Throughout the talk we will study many examples in order to get a feel for the difficulties of this problem and how the procedure is carried out.

18/01/2019 4:00 PMQueens' Building, Room W316Matthew Jenssen (Oxford)Algorithms for #BIShard problems on expander graphs
We give an FPTAS and an efficient sampling algorithm for the highfugacity hardcore model on boundeddegree bipartite expander graphs and the lowtemperature ferromagnetic Potts model on boundeddegree expander graphs. The results apply, for example, to random (bipartite) $\Delta$regular graphs, for which no efficient algorithms were known for these problems (with the exception of the Ising model) in the nonuniqueness regime of the infinite $\Delta$regular tree. Joint work with Peter Keevash and Will Perkins.

25/01/2019 4:00 PMQueens' Building, Room W316Teerasak Khoployklang (QMUL)The Hamiltonian decomposition of 4regular connected Cayley graphs
Let Γ be a finite Abelian group with operation “+” and A be a symmetric subset of Γ. The Cayley graph Cay(A,Γ) is the graph having the elements of Γ to be the vertices and, for all vertices x and y of Cay(A,Γ), there exists an edge joining x and y if and only if x−y∈A. If Γ=Zn,then V (Cay(A, Z_{n})) = {0, 1, 2, ..., n − 1} and every vertex x of Cay(A, Z_{n}) is adjacent to x+a mod n for all a∈A.
The Cayley graph Cay(A, Zn) is denoted by Cay_{n}⟨a, b⟩. We denote the sets of edges of Cay_{n}⟨a, b⟩ which join vertices u and u + a mod n, and u and u + b mod n by E_{a }and E_{b}, respectively.
We will assume that gcd(a,b,n)=1, 2a ̸=0, 2b ̸=0 and a ̸=±b. In this case Cay_{n}⟨a, b⟩ is connected and regular of degree 4. In 1989, Bermond et al. proved that Cay_{n}⟨a,b⟩ can be decomposed into two Hamiltonian cycles. We extend this result by showing that, for e_{1 }∈ E_{a }and e_{2 }∈ E_{b}, Cay_{n}⟨a, b⟩ has a Hamiltonian decomposition such that e_{1 }and e_{2 }are contained in different Hamiltonian cycles.

01/02/2019 4:00 PMQueens' Building, Room W316Carla Groenland (Oxford)Intersection sizes of linear subspaces with the hypercubeWe continue the study by Melo and Winter [arXiv:1712.01763, 2017] on the possible intersection sizes of a kdimensional subspace with the vertices of the ndimensional hypercube in Euclidean space. Melo and Winter conjectured that all intersection sizes larger than 2^{k1} (the “large” sizes) are of the form 2^{k1} + 2^i . We show that this is almost true: the large intersection sizes are either of this form or of the form 35·2^{k6} . We also disprove a second conjecture of Melo and Winter by proving that a positive fraction of the “small” values is missing.Joint work with Tom Johnston.

08/02/2019 4:00 PMQueens' Building, Room W316Stephen Muirhead (QMUL)The band structure of spatial random permutations
A spatial random permutation (SRP) is a model of random permutation that is biased towards the identity in some underlying geometry; wellknown examples include the Mallows permutation and Feynman's representation of the Bose gas. SRPs are expected to exhibit certain universal phenomena, such as crossover behaviour in the mean displacement ("band structure") and the emergence of macroscopic cycles when the band exceeds a critical width. In this talk we study the band structure of a Boltzmann model of SRP on a lattice in which the energy is equal to the total displacement. Our analysis rests on a surprising connection between random permutations and Gaussian processes, via the matrix permanent; even though this connection is wellknown in other contexts, its application to random permutations is to the best of our knowledge novel. Joint work with Yan Fyodorov (King's College London).

15/02/2019 4:00 PMQueens' Building, Room W316Natalie Behague (QMUL)Semiperfect 1Factorizations of the HypercubeA 1factorization of a graph H is a partition of the edges of H into disjoint perfect matchings {M_1 , M_2 , . . . , M_n}, also known as 1factors. A 1factorization M =
{M_1 , M_2 , . . . , M_n} of a graph G is called perfect if the union of any pair of distinct 1factors M_i , M_j is a Hamilton cycle. The existence or nonexistence of perfect 1factorizations has been studied for various families of graphs. Perhaps the most famous open problem in the area is Kotzig’s conjecture, which states that the complete graph K 2n has a perfect 1factorization. In this talk we shall focus on another wellstudied family of graphs: the hypercubes Q_d in d dimensions. There is no perfect 1factorization of Q d for d > 2. As a result, we need to consider a weaker concept.
A 1factorization M is called ksemiperfect if the union of any pair of 1factors M i , M j with 1 ≤ i ≤ k and k + 1 ≤ j ≤ n is a Hamilton cycle. It was proved that there is
a 1semiperfect 1factorization of Q d for every integer d ≥ 2 by Gochev and Gotchev, Královič and Královič, and Chitra and Muthusamy, in answer to a conjecture of Craft. My main result is a proof that there is a ksemiperfect 1factorization of Q_d for all k and all d, except for one possible exception when k = 3 and d = 6. I will sketch the proof and explain why this is, in some sense, best possible. I will conclude with some questions concerning other generalisations of perfect 1factorizations. 
01/03/2019 4:00 PMQueens' Building, Room W316Ben Smith (QMUL)Matching Fields and Tropical Matroids
Matching fields are a collection of matchings on bipartite node sets satisfying an "edge exchange axiom". They were first considered by Sturmfels and Zelevinsky in the 90s as a combinatorial tool to study the algebraic variety of degenerate matrices. More recently, they have gained attention via their connection to tropical linear algebra, specifically to encode "tropical linear dependence". We will consider these objects and the natural ways in which they arise via the combinatorics of matrices. We shall also introduce some additional collections of bipartite graphs arising from tropical linear algebra and, in the process, answer two conjectures of Sturmfels and Zelevinsky on the structure of degenerate matrices.

08/03/2019 4:00 PMQueens' Building, Room W316Amirlan Seksenbayev (QMUL)Choosing a Monotone Sequence from a Random Sample in an Online Fashion
The origin of the longest monotone sequence selection problem lies in the infamous Ulam's problem of the longest possible increasing sequence in the random permutation of numbers. Although the latter problem was settled to a somewhat satisfactory degree, the online setup requires a completely different approach. Introduced first by Samuels and Steele, it has led to the emergence of numerous variations on the original problem. In this talk we focus on the classical problem, its dual counterpart, and a poissonised (continuous) version of the classical problem. The latest results on asymptotics of the value functions are discussed, together with the properties of several selection policies.

15/03/2019 4:00 PMQueens' Building, Room W316Jorge Alberto Olarte (FU Berlin)Tropical linear spaces, Dressians and transversal matroids
Tropical geometry is a relatively recent field that studies 'polyhedral
shadows' of algebraic varieties. In the tropical world there are many
objects and theorems which are analogous to those in algebraic geometry.
In this talk we will look specifically at tropical linear spaces which are
parametrized by valuated matroids. We will discuss the Dressian, which is
the space of all valuated matroids, and formulate some open questions. We
will focus on a particular class of valuated matroids that come from
matrices with tropical entries. These are the valuated analog of
transversal matroids, which are matroids that arise from bipartite graphs.
This is based on joint work with Alex Fink and, separately, with Marta
Panizzut and Benjamin Schröter. 
29/03/2019 4:00 PMQueens' Building, Room W316Andrew LewisPye (LSE)(CANCELLED) The idemetric property: when most distances are (almost) the sameI’ll talk about some recent work in which my coauthors and I introduce the idemetric property, which formalises the idea that most nodes in a graph have similar distances between them, and which turns out to be quite standard amongst smallworld network models. Modulo reasonable sparsity assumptions, we are then able to show that a strong form of idemetricity is actually equivalent to a very weak expander condition (PUMP). This provides a direct way of providing short proofs that smallworld network models such as the WattsStrogatz model are strongly idemetric (for a wide range of parameters), and also provides further evidence that being idemetric is a common property. We also consider how satisfaction of the idemetric property is relevant to algorithm design.This is joint work with Barmpalias, Huang, Li, Li, Pan and Roughgarden.

22/03/2019 4:00 PMQueens' Building, Room W316Mark Jerrum (QMUL)The basesexchange graph of a matroid: edge expansion and mixing
In a recent breakthrough paper, Anari, Liu, Oveis Gharan and Vinzant – building on work of Kaufman and Oppenheim – settled a longstanding conjecture about the edge expansion of the basesexchange graph of an arbitrary matroid. That at least is the headline result, but many other interesting things flow out of their work. I’ll spend the first half of the talk explaining the terms appearing in the title, and then go on to hint at some of the ideas involved and describe some of the algorithmic consequences. The talk will be a toricidealfree zone.

12/04/2019 4:00 PMQueens' Building, Room: W316Felipe Rincón (QMUL)Tropical Ideals
Tropical ideals are combinatorial objects introduced with the aim of giving tropical geometry a solid algebraic foundation. They can be thought of as discrete analogues of polynomial ideals in which any boundeddegree part is “matroidal”. I will introduce and motivate the notion of tropical ideals, and I will discuss work studying some of their main properties and their possible associated varieties.

24/04/2019 4:00 PMQueens' Building, Room W316James Aaronson (Oxford)Cyclically covering subspacesWe say that a subspace of $\mathbb{F}_2^n$ is cyclically covering if the union of its cyclic shifts is the whole space. We show that, if $p$ is a prime with 2 as a primitive root, then any cyclically covering subspace in $\mathbb{F}_2^p$ must have codimension at most 2, (conditionally) answering a question of Cameron from 1991. In this talk, we will discuss some of the ideas involved in the proof.Joint work with Carla Groenland and Tom Johnston.

27/09/2019 2:00 PMG.O. Jones Building, Room 410 A&BBen Barber (Bristol)The NamerClaimer game
In each round of the NamerClaimer game (i) Namer names a forbidden distance d, then (ii) Claimer claims a subset of [n] not containing two points at distance d. How quickly can Claimer claim subsets covering [n] if Namer is trying to slow them down?
There will be an answer, a surprising connection to Ramsey theory and several open problems. 
04/10/2019 2:00 PMMathematical Sciences Building, Room MB503Oliver Janzer (Cambridge)The extremal number of subdivisions
For a graph H, the extremal number ex(n,H) is defined to be the maximal number of edges in an Hfree graph on n vertices. For bipartite graphs H, determining the order of magnitude of ex(n,H) is notoriously difficult. In this talk I present recent progress on this problem.
The ksubdivision of a graph F is obtained by replacing the edges of F with internally vertexdisjoint paths of length k+1. Most of our results concern the extremal number of various subdivided graphs, especially the subdivisions of the complete graph and the complete bipartite graph.
Partially joint work with David Conlon and Joonkyung Lee. 
11/10/2019 2:00 PMMathematical Sciences Building, Room MB503Bill Jackson (QMUL)Abstract 3RigidityDetermining when a generic barjoint framework is rigid in 3space is a central open problem in discrete geometry. It is equivalent to determining the rank function of the 3dimensional rigidity matroid of the underlying graph of the framework. In an attempt to get a better understanding of this problem, Jack Graver defined the family of abstract 3rigidity matroids in 1990. He conjectured that there is a unique maximal abstract 3rigidity matroid (in the weak order on matroids) and that this matroid is the 3dimensional rigidity matroid. We prove the first part of Graver's conjecture by showing that the C_2^1cofactor matroid from approximation theory is the unique maximal abstract 3rigidity matroid.This is joint work with Katie Clinch and ShinIchi Tanigawa.

18/10/2019 2:00 PMMathematical Sciences Building, Room MB503Yani Pehova (Warwick)Packing Hamilton cycles in bipartite directed graphs
In 1981 Jackson showed that the diregular bipartite tournament (a balanced complete bipartite graph whose edges are oriented so that every vertex has the same in and outdegree) contains a Hamilton cycle, and conjectured that in fact the edge set of it can be partitioned into Hamilton cycles. We prove an approximate version of this conjecture: For every c>1/2 and ε>0 there exists n_0 such that every cnregular bipartite digraph on 2n>n_0 vertices contains (1ε)cn edgedisjoint Hamilton cycles. This is joint work with Anita Liebenau (UNSW Sydney).

25/10/2019 2:00 PMMathematical Sciences Building, Room MB503Maryam Sharifzadeh (Warwick)Asymptotic Structure for the Clique Density Theorem
The famous ErdősRademacher problem asks for the smallest number of $r$cliques in a graph with the given number of vertices and edges. Despite decades of active attempts, the asymptotic value of this extremal function for all $r$ was determined only recently, by Reiher. In this talk, we describe the asymptotic structure of all almost extremal graphs. This task for $r=3$ was previously accomplished by Pikhurko and Razborov. This is joint work with Jaehoon Kim, Hong Liu, and Oleg Pikhurko.

01/11/2019 2:00 PMMathematical Sciences Building, Room MB503Robert Johnson (QMUL)Correlation for permutations

08/11/2019 2:00 PMMathematical Sciences Building, Room: MB503Richard Montgomery (Birmingham)Spanning cycles in random directed graphs
A beautiful coupling argument of McDiarmid shows that, given any
orientated nvertex cycle C, a copy of C almost surely appears in D(n,p)
if p=(log n+log log n+omega(1))/n. This is not always optimal—as Frieze
had shown, for a directed Hamilton cycle p=(log n+omega(1))/n is sufficient.
This talk will address the following questions, by combining McDiarmid’s
coupling with constructive techniques:
 Is p=(log n+omega(1))/n sufficient for the appearance of any oriented
nvertex cycle?
 When is it likely that a copy of all such cycles can be found
simultaneously? 
22/11/2019 2:00 PMMathematical Sciences Building, Room MB503Frederik MallmannTrenn (KCL)Hierarchical Clustering: Objective Functions and Algorithms
Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Motivated by the fact that most work on hierarchical clustering was based on providing algorithms, rather than optimizing a specific objective, Dasgupta framed similaritybased hierarchical clustering as a combinatorial optimization problem, where a “good” hierarchical clustering is one that minimizes a particular cost function. He showed that this cost function has certain desirable properties: To achieve optimal cost, disconnected components (namely, dissimilar elements) must be separated at higher levels of the hierarchy, and when the similarity between data elements is identical, all clusterings achieve the same cost. We take an axiomatic approach to defining “good” objective functions for both similarity and dissimilaritybased hierarchical clustering. We characterize a set of admissible objective functions having the property that when the input admits a “natural” groundtruth hierarchical clustering, the groundtruth clustering has an optimal value. We show that this set includes the objective function introduced by Dasgupta. Equipped with a suitable objective function, we analyze the performance of practical algorithms, as well as develop better and faster algorithms for hierarchical clustering. We also initiate a beyond worstcase analysis of the complexity of the problem and design algorithms for this scenario.

07/02/2020 2:00 PMMathematical Sciences Building, Room MB503Andrew LewisPye (LSE)The idemetric property: when most distances are (almost) the sameI’ll talk about some recent work in which my coauthors and I introduce the idemetric property, which formalises the idea that most nodes in a graph have similar distances between them, and which turns out to be quite standard amongst smallworld network models. Modulo reasonable sparsity assumptions, we are then able to show that a strong form of idemetricity is actually equivalent to a very weak expander condition (PUMP). This provides a direct way of providing short proofs that smallworld network models such as the WattsStrogatz model are strongly idemetric (for a wide range of parameters), and also provides further evidence that being idemetric is a common property. We also consider how satisfaction of the idemetric property is relevant to algorithm design.This is joint work with Barmpalias, Huang, Li, Li, Pan and Roughgarden.

06/12/2019 2:00 PMMathematical Sciences Building, Room MB503Alexey Pokrovskiy (Birkbeck)Halfway to Rota's basis conjecture
In 1989, Rota made the following conjecture. Given n bases B1, ..., Bn in an ndimensional vector space V, one can always find n disjoint bases of V, each containing exactly one element from each Bi (we call such bases transversal bases). Rota’s basis conjecture remains open despite its apparent simplicity. In this talk, we will discuss how to find (0.5  o(1))n disjoint transversal bases, improving the previously best known bound of n/log n. This is joint work with Bucic, Kwan, and Sudakov.

13/12/2019 2:00 PMGraduate Centre, GC222Torsten Mütze (Warwick)Combinatorial generation via permutation languages
In this talk I present a general and versatile algorithmic framework for exhaustively generating a large variety of different combinatorial objects, based on encoding them as permutations, which provides a unified view on many known results and allows us to prove many new ones. In particular, we obtain the following four classical Gray codes as special cases: the SteinhausJohnsonTrotter algorithm to generate all permutations of an nelement set by adjacent transpositions; the binary reflected Gray code to generate all nbit strings by flipping a single bit in each step; the Gray code for generating all nvertex binary trees by rotations due to Lucas, van Baronaigien, and Ruskey; the Gray code for generating all partitions of an nelement ground set by element exchanges due to Kaye.
The first main application of our framework is the generation of patternavoiding permutations, yielding new Gray codes for different families of permutations that are characterized by the avoidance of certain classical patterns, (bi)vincular patterns, barred patterns, mesh patterns, monotone and geometric grid classes, and many others. We also obtain new Gray codes for all the combinatorial objects that are in bijection to these permutations, in particular for five different types of geometric rectangulations, also known as floorplans, which are divisions of a square into n rectangles subject to different restrictions.
The second main application of our framework are lattice congruences of the weak order on the symmetric group S_n. Recently, Pilaud and Santos realized all those lattice congruences as (n1)dimensional polytopes, called quotientopes, which generalize hypercubes, associahedra, permutahedra etc. Our algorithm generates the equivalence classes of each of those lattice congruences, by producing a Hamilton path on the skeleton of the corresponding quotientope, yielding a constructive proof that each of these highly symmetric graphs is Hamiltonian. We thus also obtain a provable notion of optimality for the Gray codes obtained from our framework: They translate into walks along the edges of a polytope.
This is joint work with Liz Hartung, Hung P. Hoang, and Aaron Williams (SODA 2020). 
24/01/2020 2:00 PMMathematical Sciences Building, Room MB503David Ellis (Bristol)Families of permutations with a forbidden intersection
A family of permutations is said to be 'tintersecting' if any two permutations in the family agree on at least t points. It is said to be (t1)intersectionfree if no two permutations in the family agree on exactly t1 points. Deza and Frankl conjectured in 1977 that a tintersecting family of permutations in S_n can be no larger than a coset of the stabiliser of t points, provided n is large enough depending on t; this was proved by the speaker and independently by Friedgut and Pilpel in 2008. We give a new proof of a stronger statement: namely, that a (t1)intersectionfree family of permutations in S_n can be no larger than a coset of the stabiliser of t points, provided n is large enough depending on t. This can be seen as an analogue for permutations of seminal results of Frankl and Furedi on families of kelement sets. Our proof is partly algebraic and partly combinatorial; it is more 'robust' than the original proofs of the DezaFrankl conjecture, using a combinatorial 'quasirandomness' argument to avoid many of the algebraic difficulties of the original proofs. Its robustness allows easier generalisation to various other permutation groups. Based on joint work with Noam Lifshitz (Hebrew University of Jerusalem).

31/01/2020 2:00 PMMathematical Sciences Building, Room MB503Matthias Beck (SF State/FU Berlin)Lonely runner polyhedra
We study the Lonely Runner Conjecture, conceived by Jörg M. Wills in the 1960's: Given positive integers n_1, n_2, ..., n_k, there exists a positive real number t such that for all 1 ≤ j ≤ k the distance of tn_j to the nearest integer is at least 1/(k+1). Continuing a viewobstruction approach by Cusick and recent work by Henze and Malikiosis, our goal is to promote a polyhedral ansatz to the Lonely Runner Conjecture. Our results include geometric proofs of some folklore results that are only implicit in the existing literature, a new family of affirmative instances defined by the parities of the speeds, and geometrically motivated conjectures whose resolution would shed further light on the Lonely Runner Conjecture.
This is joint work with Serkan Hosten (SF State) and Matthias Schymura (Lausanne). 
14/02/2020 2:00 PMMathematical Sciences Building, Room MB503Anthony Hilton (Reading)Bounds related to the edgelist chromatic and total chromatic numbers of a simple graph
We show that for a simple graph G, c' (G) ≤ Δ(G) + 2 where c' (G) is the choice index ( or edgelist chromatic number) of G, and Δ(G) is the maximum degree of G.
As a simple corollary of this result, we show that the total chromatic number χT(G) of a simple graph satisfies the inequality χT (G) ≤ Δ(G) + 4 and the total choice number cT(G) also satisfies this inequality.
We also relate these bounds to the Hall index and the Hall condition index of a simple graph, and to the total Hall number and the total Hall condition number of a simple graph.
This is joint work with M. Henderson, A.J.W. Hilton and R. Mary Jeya Jothi

21/02/2020 2:00 PMMathematical Sciences Building, Room MB503Louis Theran (St Andrews)(CANCELLED)

28/02/2020 2:00 PMMathematical Sciences Building, Room MB503Jozef Skokan (LSE)Decomposing tournaments into paths
In this work we consider a generalisation of Kelly’s conjecture which is due Alspach, Mason, and Pullman from 1976. Kelly’s conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by Kuehn and Osthus for large tournaments. The conjecture of Alspach, Mason, and Pullman concerns general tournaments and asks for the minimum number of paths needed in an edge decomposition of each tournament into paths. There is a natural lower bound for this number in terms of the degree sequence of the tournament and they conjecture this bound is correct for tournaments of even order. Almost all cases of the conjecture are open and we prove many of them.
This is joint work with Allan Lo (Birmingham), Viresh Patel (UVA) and John Talbot (UCL).

13/03/2020 2:00 PMMathematical Sciences Building, Room MB503Shoham Letzter (Cambridge)(CANCELLED)

20/03/2020 2:00 PMMathematical Sciences Building, Room MB503Victor Verdugo (LSE)(CANCELLED)

17/01/2020 2:00 PMMathematical Sciences Building, Room MB503Nick Wormald (Monash University)Fast uniform generation of regular graphs and contingency tables
We present a new technique for use in switchingbased random
generation of graphs with given degrees. For graphs with m edges and
maximum degree D=O(m^4), the ``best'' existing uniform sampler, by McKay
and Wormald, runs in time O(m^2D^2). Our new one runs in time O(m),
which is effectively optimal. For dregular graphs with d^2=o(n), the
best existing ones run in time O(nd^3). This is now improved to
O(nd+d^4). Similar results are obtained for generating random
contingency tables with given marginals (equivalently, bipartite
multigraphs with given degree sequence) in the sparse case. This is
joint work with Andrii Arman and Jane Gao.
This is an informal talk, aimed at nonspecialists. 
27/03/2020 2:00 PMMathematical Sciences Building, Room MB503Nicola Durante (Napoli)(CANCELLED)

03/03/2020 12:00 PMMathematical Sciences Building, Room MB503Igor Pak (UCLA and IML)Counting standard Young tableaux
We study the asymptotics of the number of standard Young tableaux of large skew diagrams. We present new bounds and discuss how they compare with the existing general bounds. I will also make a connection with the 1/32/3 conjecture for linear extension of posets. Our approach is based on a recent Naruse's hooklength formula which I will also explain, and is related to weighted lozenge tilings. The talk assumes no prior knowledge of the subject.

25/09/2020 2:00 PMonline via ZoomMarthe Bonamy (Bordeaux)Graph recolouring
Given a solution to a problem, we can try and apply a series of elementary operations to it, making sure to remain in the solution space at every step. What kind of solutions can we reach this way? How fast? This is motivated by a variety of applications, from statistical physics to reallife scenarios, including enumeration and sampling. In this talk, we will discuss various positive and negative results, in the special case of graph colouring.

02/10/2020 2:00 PMonline via ZoomJulian Sahasrabudhe (Cambridge)Random polynomials  roots near the unit circleLet f be a polynomial of degree n with iid Gaussian coefficients. It is a classical problem, reaching back to at least the 30s, to understand the typical distribution of the roots of f in the complex plane. In particular, it is a well known (but perhaps surprising) fact that most of the roots of such polynomials cluster tightly around the unit circle.While this phenomena is now well understood, several questions about the ``microscopic'' nature of this clustering remain open. Indeed, Shepp and Vanderbei in 1995 asked for the minimum distance between a root of f and the unit circle. In this talk I will sketch a resolution of this conjecture, based on joint work with Marcus Michelen, and mention some more detailed results in this vein.

09/10/2020 2:00 PMonline via ZoomIoannis Caragiannis (Aarhus)Impartial selection, additive approximation guarantees, and priors
We study the problem of impartial selection, a topic that lies at the intersection of computational social choice and mechanism design. The goal is to select the most popular individual among a set of community members. The input can be modelled as a directed graph, where each node represents an individual, and a directed edge indicates nomination or approval of a community member to another. An impartial mechanism is robust to potential selfish behaviour of the individuals and provides appropriate incentives to voters to report their true preferences by ensuring that the chance of a node to become a winner does not depend on its outgoing edges. The goal is to design impartial mechanisms that select a node with an indegree that is as close as possible to the highest indegree.
Recent progress has identified impartial selection rules with optimal approximation ratios. It was noted though that worstcase instances are graphs with few vertices. Motivated by this fact, we propose the study of additive approximation, the difference between the highest number of nominations and the number of nominations of the selected member, as an alternative measure of quality. We present randomized impartial selection mechanisms with additive approximation guarantees of o(n), where n is the number of nodes in the input graph.
We furthermore demonstrate that prior information on voters' preferences can be useful in the design of simple (deterministic) impartial selection mechanisms with good additive approximation guarantees. In this direction, we consider different models of prior information and analyze the performance of a natural selection mechanism that we call approval voting with default (AVD).
The talk is based on joint work with George Christodoulou and Nicos Protopapas. No advanced mathematical background (besides basic knowledge on graphs and probability) is required to follow the talk. 
16/10/2020 2:00 PMonline via ZoomShoham Letzter (UCL)An improvement on Łuczak's connected matchings methodA connected matching is a matching contained in a connected component. A wellknown method due to Łuczak reduces problems about monochromatic paths and cycles in complete graphs to problems about monochromatic matchings in almost complete graphs. We show that these can be further reduced to problems about monochromatic connected matchings in complete graphs.I will describe Łuczak's reduction, introduce the new reduction, and mention potential applications of the improved method.

20/11/2020 2:00 PMonline via ZoomLouis Theran (St Andrews)Unlabelled rigidity problems
Framework rigidity is concerned with questions of the following form: what can we learn about an unknown set of n points p_1, …, p_n in ddimensional space from the distances between a subset of the pairs {p_i, p_j}, with i and j known? Global rigidity of a framework (G, p) is then the question: can we recover p, up to an unknown isometry?
I will introduce and discuss variations of global rigidity problems when we are given lengths, but not the combinatorics of the measurement process that generated them. Maybe surprisingly, we can get positive results, under a suitable genericity hypotheses on the unknown configuration p. 
30/10/2020 2:00 PMonline via ZoomRoss Kang (Nijmegen)Global graph structure derived from local sparsity
The study of trianglefree graphs has a long tradition yet continues to produce novel insights. Classic results on the independence or chromatic number of trianglefree results may be viewed as leveraging local structural information  that is, the absence of edges in any neighbourhood  to produce global structure. In this talk, we mainly consider the obvious generalisation where instead of absence, some bound on the density of edges in any neighbourhood is assumed. This perspective has led to important general results, for example, by Alon, Krivelevich and Sudakov (1999), and by Molloy and Reed (1997). We discuss new probabilistic methods to handle this and related problems. This covers some joint works with Ewan Davies, Rémi de Joannis de Verclos, Eoin Hurley, François Pirot, JeanSébastien Sereni.

13/11/2020 2:00 PMonline via ZoomKitty Meeks (Glasgow)Reducing Reachability in Temporal Graphs
The concept of reachability sets (i.e. the set of vertices which can be reached from a given starting point by travelling along edges) is central to many networkbased processes, including the dissemination of information or the spread of disease through a network. In many cases  for example, considering the spread of a biological disease, a computer virus, or fake news  it might be desirable to reduce the number of vertices reachable from any given starting vertex. Moreover, in most settings, time plays a crucial role: each contact between individuals, represented by an edge, will only occur at certain time(s), when the corresponding edge is "active". The relative timing of edges is clearly crucial in determining the reachability set of any vertex in the graph.
In this talk, I will address the problems of reducing the maximum reachability of any vertex in a given temporal network by two different means:
(1) we can remove a limited number of edges from the graph, or
(2) every edge is retained, but we can change the relative order in which different edges are active (perhaps subject to some additional constraints).
Mostly, we find that these problems are computationally intractable even when very strong restrictions are placed on the input, but we identify a small number of special cases that admit polynomialtime or FPT algorithms, as well as giving some more general approximation algorithms.
Everything in this talk is based on joint work with Jessica Enright (University of Glasgow); I will also mention some joint results with George B. Mertzios (University of Durham), and Viktor Zamaraev (University of Liverpool) and Fiona Skerman (Uppsala University). 
04/12/2020 2:00 PMonline via ZoomHeng Guo (Edinburgh)Markov chain algorithms for bounded degree kSatI will present a Markov chain based algorithm to sample satisfying assignments of kCNF formulas, where each variable appears in sufficiently few (but still exponential in k) clauses. The solution space for this problem is not connected via single variable updates, and we bypass this issue by defining a suitable projection of the desired distribution and running Markov chains over it.Joint work with Weiming Feng, Yitong Yin, and Chihao Zhang

11/12/2020 2:00 PMonline via ZoomVictor Verdugo (Universidad de O'Higgins)Apportionment Mechanisms in the Presence of Types and Parity Constraints
How many seats should be allocated to each political party in an election? This question has a long and rich history, and plays a fundamental role in order to ensure appropriate levels of representation in the parliaments. We consider this question in the presence of types (e.g. men and women), where apart from ensuring proportionality at the party level we also have to find an allocation for the types under parity constraints. We consider two different approaches: one of them, following a greedy/local search paradigm, corresponds to a mechanism recently approved in the Chilean parliament (March 2020) to find the representatives of the constitutional assembly with the goal of designing a new political constitution for Chile (election to happen in April 2021); the other one is based on the idea of integral biproportionality, introduced by Balinski and Demange in the late 80’s. We analyze both mechanisms from an axiomatic and quantitative point of view. We also provide new results regarding integral biproportional solutions and the fair share, a.k.a matrix scaling solution, which represents the ideal (but not necessarily implementable) fractional biproportional solution.

27/11/2020 2:00 PMonline via ZoomJustin Ward (QMUL)Multipass streaming algorithms for submodular maximisation
Many problems in combinatorial optimisation, data science, and machine learning can be cast as finding the optimum value of a submodular objective function subject to some combinatorial constraint. Although this problem is NPhard even for a simple cardinality constraint, there are several classical algorithms that deliver constantfactor approximation guarantees for various constraints. Here, we consider what can be done in the following “streaming" setting. Suppose that a problem instance (i.e. the domain of some submodular function we seek to optimise) is too large to efficiently store in random access memory, and instead arrives as a stream of data elements (either once or multiple times). What can be done if we are allowed to store only a comparatively small number of these elements in the ground set? In this talk, I will discuss some recent join work with Theophile Thiery, that shows that by performing a constant number of passes through the data stream, we can obtain improved approximation guarantees nearly matching that of wellknown local search algorithms for the standard, offline setting. Our techniques apply to monotone and nonmonotone submodular maximisation under matroid constraints and also pmatchoid constraint, which generalise matching, setpacking, and matroid intersection problems.

29/01/2021 2:00 PMonline via ZoomMaya Stein (U Chile)Diractype conditions for embedding hypertrees
Solving a conjeture of Bollobás from the 1970's, Komlós, Sárközy and Szemerédi proved in 1995 that every graph of minimum degree \(n/2 + o(n)\) contains every \(n\)vertex tree of bounded maximum degree as a subgraph. We show an extension of this theorem to \(k\)uniform hypergraphs. The trees in our theorem are tight ktrees. Our proof relies on a decomposition of tight ktrees, weak hypergraph regularity, and absorption. We will also give an overview of related questions for graphs and hypergraphs.
This is joint work with Matías PavezSigné and Nicolás SanhuezaMatamala 
05/02/2021 2:00 PMonline via ZoomNicole Megow (Bremen)(Cancelled)

12/02/2021 2:00 PMonline via ZoomViresh Patel (Amsterdam)Algorithmic extensions of the BollobásHäggkvist conjectureDirac's Theorem is a classical result in graph theory stating that every nvertex graph with minimum degree at least n/2 has a Hamilton cycle. If we restrict to regular graphs (and impose some mild connectivity conditions), we might hope to lower the degree threshold: in that direction, Bollobás and Häggkvist independently conjectured that every kconnected, Dregular, nvertex graph with D≥n/(k+1) has a Hamilton cycle. Although the conjecture turns out to be false for k≥4, one might still wonder whether Hamiltonicity is easier to detect in regular (dense) graphs. We investigate this question. This is joint work with Fabian Stroh.

19/02/2021 2:00 PMonline via ZoomGal Kronenberg (Oxford)The maximum length of K_rBootstrap Percolation
How long does it take for a pandemic to stop spreading? In this talk, we consider this question in the bootstrap percolation setting.
Graphbootstrap percolation, also known as weak saturation, was introduced by Bollobás in 1968. In this process, we start with initial "infected" set of edges E_0, and we infect new edges according to a predetermined rule. Given a graph H and a set of previously infected edges E_t ⊆ E(K_n), we infect a noninfected edge e if it completes a new copy of H in G=([n] , E_t ∪ {e}). A question raised by Bollobás asks for the maximum time the process can run before it stabilizes. Bollobás, Przykucki, Riordan, and Sahasrabudhe considered this problem for the most natural case where H=K_r. They answered the question for r ≤ 4 and gave a nontrivial lower bound for every r ≥ 5. They also conjectured that the maximal running time is o(n^2) for every integer r. We disprove their conjecture for every r ≥ 6 and we give a better lower bound for the case r=5; in the proof we use the Behrend construction. This is a joint work with József Balogh, Alexey Pokrovskiy, and Tibor Szabó. 
26/02/2021 2:00 PMonline via ZoomTom Hutchcroft (Cambridge)Supercritical percolation on finite transitive graphs.In Bernoulli bond percolation, each edge of some graph are chosen to be either deleted or retained independently at random with retention probability p. For many large finite graphs, there is a phase transition such that if p is sufficiently large then there exists a giant cluster whose volume is proportional to that of the graph with high probability. We prove that in this phase the giant cluster must be unique with high probability: this was previously known only for tori and expander graphs via methods specific to those cases. The work that I will describe is joint with Philip Easo.

05/03/2021 2:00 PMonline via ZoomTyler Helmuth (Durham)Random unrooted spanning forestsIn Bernoulli(p) bond percolation, each edge of a given graph is declared open with probability p. The set of open edges is a random subgraph. The arboreal gas is the probability measure that arises if you condition on the event that the random subgraph is a spanning forest, i.e., contains no cycles. In the special case p=1/2 the arboreal gas is the uniform measure on spanning forests.What are the percolative properties of these forests? This turns out to be a surprisingly rich question, and I will discuss what is known and conjectured. I will also describe a "magic formula" for connection probabilities in the arboreal gas. This formula is related to the CoppersmithDiaconis magic formula for edgereinforced random walk, and I’ll give a glimpse into how this connection arises.Based on joint work with Roland Bauerschmidt, Nick Crawford, and Andrew Swan.

09/04/2021 9:00 AMonline via ZoomAnita Liebenau (UNSW)Two approximate versions of Jackson’s conjecture
A diregular bipartite tournament is a balanced complete bipartite graph whose edges are oriented so that every vertex has the same in and outdegree. In 1981, Jackson showed that a diregular bipartite tournament contains a Hamilton cycle, and conjectured that in fact the edge set of it can be partitioned into Hamilton cycles. We prove an approximate version of this conjecture: for every epsilon>0 there exists n_{0} such that every diregular bipartite tournament on 2n>n_{0} vertices contains a collection of (1/2epsilon)n cycles of length at least (2epsilon)n. Increasing the degree by a small proportion allows us to prove the existence of many Hamilton cycles: for every c>1/2 and epsilon>0 there exists n_{0} such that every cnregular bipartite digraph on 2n>n_{0} vertices contains (1epsilon)cn$ edgedisjoint Hamilton cycles.
Joint work with Yani Pehova.

26/03/2021 2:00 PMonline via ZoomDudley Stark (QMUL)The component counts of random injections
Similarly to the way that the digraph representing a permutation can be uniquely decomposed into cycles, the digraph representing an injection between two finite sets can be uniquely decomposed into cycles and paths. The component structure of a random injection undergoes a phase transition between cycles dominating and paths dominating as certain parameters change.

19/03/2021 2:00 PMonline via ZoomMatt Fayers (QMUL)The Mullineux map
The Mullineux map is a function on partitions which arises in the representation theory of the symmetric group. The Mullineux problem is to describe this function purely combinatorially. I will describe the history of this problem and explain the known combinatorial solutions, and then give a new solution based on crystals and regularisation.

16/04/2021 2:00 PMonline via ZoomAndrew Treglown (Birmingham)Extremal problems for multigraphs
An (n,s,q)graph is an nvertex multigraph in which every sset of vertices spans at most q edges. Turantype questions on the maximum of the sum of the edge multiplicities in such multigraphs have been studied since the 1990s. More recently, Mubayi and Terry posed the problem of determining the maximum of the product of the edge multiplicities in
(n,s,q)graphs. In this talk we will discuss recent progress on this problem, including a result that shows for infinitely many choices of (s,q), the solution is transcendental. This answers a question of Alon. This is joint work with Nick Day and Victor FalgasRavry.

08/10/2021 2:00 PMMB503 + online via ZoomBen Smith (Manchester)Constructing auction valuations from matroidsAuction theory is concerned with how an agent's valuation of goods informs their behaviour. When goods are indivisible, it is desirable for agents to have ``gross substitutes'' valuations, a class of valuations that lead to competitive equilibrium. In general, these valuations are complex to express; a general valuation on n goods requires 2^n values, and the gross substitutes (GS) property does not allow for a significant decrease on this number. Therefore, a key question is to find a simple class of valuations that generates all GS valuations.Matroids are combinatorial objects that capture independence data of mathematical structures; examples include linear independence of sets of vectors, and forests of graphs. As independence is a fundamental property, they play important roles across different areas of mathematics and computer science. In particular, they naturally arise in this setting as GS valuations are matroidal in structure. Given this, Ostrovsky and Paes Leme formulated the MatroidBased Valuation conjecture, that one could construct all GS valuations from weighted matroid rank functions.We take this further by introducing Rminor valuations, a more general class of valuations given by inducing a matroid through a weighted bipartite graph. We show that this is a more natural class of valuations to consider as it is complete, i.e., it is closed under many natural operations that GS valuations are. However, we show that not even Rminor valuations cover GS valuations by constructing a family of counterexamples, refuting the conjecture of Ostrovsky and Paes Leme.
This is joint work with Edin Husić, Georg Loho and László Végh.

26/11/2021 2:00 PMonline via ZoomVictor Falgas Ravry (Umeå)Bridgit revisited: MakerBreaker percolation games
In the game of Bridgit, two players – let us call them Alice and Bob – play in alternating turns by placing bridges on a rectangular board. On each of their turns, Alice adds a red bridge while Bob adds a blue bridge. Alice's aim is to build a connected path of red bridges from the lefthand side of the board to the righthand side, while Bob for his part tries to hinder her by assembling a connected path of blue bridges from the top side of the board to the bottom side.
Bridgit was introduced by David Gale in the 1950s, and was instantly and completely solved: for each board we know both the identity of the winning player under optimal play and an explicit winning strategy. But what happens if the players were allowed to place more than one bridge on each of their turns – say, for example that Alice places two bridges and Bob three? Such variants of the game turn out to be considerably more difficult to analyse than the original Bridgit. In this talk, I will describe some special cases where one can find explicit winning strategies (as well as some elementary cases that remain stubbornly open!), and how these are connected to percolationinspired MakerBreaker games.
Joint work with A. Nicholas Day

22/10/2021 2:00 PMMB503 + online via ZoomNatalie Behague (Ryerson)Subgraphs in semirandom graphs (and hypergraphs)
The semirandom graph process can be thought of as a one player game. Starting with an empty graph on n vertices, in each round a random vertex u is presented to the player, who chooses a vertex v and adds the edge uv to the graph. Given a graph property, the objective of the player is to force the graph to satisfy this property in as few rounds as possible.
We will consider the property of constructing a fixed graph G as a subgraph of the semirandom graph. BenEliezer, Gishboliner, Hefetz and Krivelevich proved that the player can asymptotically almost surely construct G given n^{1 – 1/d}w rounds, where w is any function tending to infinity with n and d is the degeneracy of the graph G. We have proved a matching lower bound. I will talk about this result, and also discuss a generalisation of our approach to semirandom hypergraphs. I will finish with some open questions.
This is joint work with Trent Marbach, Pawel Pralat and Andrzej Rucinski.

29/10/2021 2:00 PMonline via ZoomFatemeh Mohammadi (Ghent)Matroid stratifications of hypergraph varieties and their realization spaces.
I will provide an introductory talk to hypergraph varieties, focusing on the combinatorial aspect. I will not assume any prior knowledge of algebraic, polyhedral, or incidence geometry, and I will try to make the talk accessible to people with a broad range of backgrounds.
The main themes of the talk are (1) connecting the geometric properties of hypergraphs to their minimal matroids; (2) reducing the geometric invariants of these matroids to grid matroids; and (3) understanding the realizability of these matroids.
Finally, I will mention the application to conditional independence models in statistics and will present several combinatorial questions and computational challenges around this problem. This is based on joint works with Kevin Grace, Oliver Clarke, and Harshit J Motwani. 
10/12/2021 2:00 PMonline via ZoomJoonkyung Lee (Hanyang University)Majority dynamics on sparse random graphsMajority dynamics on a graph G is a deterministic process such that every vertex updates its ±1assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, O'Donnell, Tamuz and Tan conjectured that, in the ErdösRényi random graph G(n,p), the random initial ±1assignment converges to a 99%agreement with high probability whenever p=omega(1/n).
This conjecture was first confirmed for p ≥ lambda n^{–1/2} for a large constant lambda by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, it was unknown whether the conjecture holds for p< lambda n^{–1/2}. We break this Omega(n^{–1/2})barrier by proving the conjecture for sparser random graphs G(n,p), where lambda' n^{–3/5} log n ≤ p ≤ lambda n^{–1/2} with a large constant lambda' > 0.Joint work with Debsoumya Chakraborti, Jeong Han Kim, and Tuan Tran. 
05/11/2021 2:00 PMMB503 + online via ZoomMariaRomina Ivan (Cambridge)Induced Poset Saturation
Given a fixed poset P, we say that a family F of subsets of [n] is Pfree if it does not contain an (induced) copy of P. And we say that F is Psaturated if it is maximal Pfree. How small can a Psaturated family be? The smallest such size is the induced saturation number of P, sat*(n,P). Even for very small posets, the question of the growth speed of sat*(n,P) seems to be hard. We present background on this problem and some recent results.

03/12/2021 2:00 PMonline via ZoomNina Otter (QMUL)(Persistent) magnitude of pointcloud data
Magnitude is an isometric invariant of metric spaces that has been introduced by Tom Leinster in 2010, and is currently the object of intense research, since it has been shown to encode many invariants of a metric space such as volume, dimension, and capacity. In 2018 I proposed a way to relate magnitude to persistent homology, one of the main techniques used in Topological Data Analysis. Building on this connection, in recent work, Hepworth and Govc introduced persistent magnitude, a numerical invariant of a filtered simplicial complex associated to a metric space.
In this talk I will introduce magnitude, persistent magnitude, and further introduce alpha magnitude, a new invariant inspired by Hepworth and Govc’s notion of persistent magnitude, and establish some of its key properties. I will further explain how these invariants can be used to study datasets exhibiting selfsimilar properties, and compute some examples involving fractals. I will introduce all the concepts, and no previous knowledge on magnitude or persistent homology will be required
This talk is based on joint work with Sara Kalisnik and Miguel O’Malley, as well as the paper https://arxiv.org/abs/1807.01540

17/12/2021 2:00 PMMB503 + online via ZoomMatthias EnglertBreaking the Barrier of 2 for the Competitiveness of Longest Queue Drop
We consider the problem of managing the buffer of a sharedmemory switch that transmits packets of unit value. A sharedmemory switch consists of an input port, a number of output ports, and a buffer with a specific capacity. In each time step, an arbitrary number of packets arrive at the input port, each packet designated for one output port. Each packet is added to the queue of the respective output port. If the total number of packets exceeds the capacity of the buffer, some packets have to be irrevocably rejected. At the end of each time step, each output port transmits a packet in its queue and the goal is to maximize the number of transmitted packets.
The Longest Queue Drop (LQD) online algorithm accepts any arriving packet to the buffer. However, if this results in the buffer exceeding its memory capacity, then LQD drops a packet from whichever queue is currently the longest. The LQD algorithm was first introduced in 1991, and has shown to be 2competitive in 2001. Although LQD remains the best known online algorithm for the problem, determining its true competitiveness is a longstanding open problem. We show that LQD is 1.707competitive, establishing the first (2 − eps) upper bound for the competitive ratio of LQD, for a constant eps > 0, but there are still a number of outstanding questions.
(based on joint work with Antonios Antoniadis, Nicolaos Matsakis, and Pavel Vesely) 
15/10/2021 2:00 PMonline via ZoomBill Jackson (QMUL)Maximal matroids in weak order posets
Let X be a family of subsets of a finite set E. A matroid M on E is said to be an Xmatroid if each set in X is a circuit in M. We consider the problem of determining when there exists a unique maximal Xmatroid in the weak order poset of all Xmatroids on E (defined by putting M_1 ≤ M_2 if every independent set in M_1 is independent in M_2).

28/01/2022 2:00 PMonline, via ZoomTom Gur (Warwick)Worstcase to averagecase reductions via additive combinatorics
We present a new framework for designing worstcase to averagecase reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time T that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time O(T log T) that are correct on all inputs.
Using our framework, we obtain such efficient worstcase to averagecase reductions for fundamental problems in a variety of computational models; namely, algorithms for matrix multiplication, streaming algorithms for the online matrixvector multiplication problem, and static data structures for all linear problems as well as for the multivariate polynomial evaluation problem.
Our techniques crucially rely on additive combinatorics. In particular, we show a local correction lemma that relies on a new probabilistic version of the quasipolynomial BogolyubovRuzsa lemma.
Joint work with Vahid Asadi, Alexander Golovnev, and Igor Shinkar. 
11/02/2022 2:00 PMonline via ZoomSteve Noble (Birkbeck)The Tutte polynomial of an embedded graph
There have been many attempts to extend the Tutte polynomial from graphs (or matroids) to embedded graphs (or deltamatroids). One which keeps many of the desirable properties of the Tutte polynomial, at least for graphs embedded in an orientable surface (or even deltamatroids), is sometimes known as the ribbongraph polynomial and is essentially a twovariable polynomial specialization of Bollobas and Riordan's embedded graph polynomial.
We will review some of the many nice properties of the Tutte polynomial of a graph, namely that it is irreducible if and only if the graph (or matroid) is 2connected and that it detects whether or not a graph (or matroid) is seriesparallel and see that these properties extend to the ribbon graph polynomial.
No knowledge of either matroids or embedded graphs will be assumed! 
25/02/2022 2:00 PMOnline via Zoom. (This is the talk rescheduled owing to Storm Eunice)Cécile Mailler (Bath)Voronoi cells in random split trees
Take k nodes uniformly at random in a nnode graph, and let k competing epidemics spread along edges at constant speed from these initial nodes, infecting nodes when they reach them. A node can only get infected by one of the epidemics, the first one that reaches it. We are interested in the sizes of the final territories of the k epidemics, which we call the Voronoi cells of the k initial nodes. In this joint work with Markus Heydenreich (Munich) and Alex Drewitz (Cologne), we prove limiting theorems for the sizes of the Voronoi cells of k nodes taken uniformly at random in an nnode random split tree.

11/03/2022 2:00 PMMB503 + streamed . Please note that we will be starting promptly at 2pm!Omer Bobrowski (QMUL)Homological connectivity in random Čech complexes
A wellknown phenomenon in random graphs is the phasetransition for connectivity, proved first by Erdős Rényi in 1959.
In this talk we will discuss a highdimensional analogue of this phenomenon which we refer to as "homological connectivity".
Loosely speaking, homological connectivity is the point where the homology of a simplicial filtration stops changing.
The model we study is the Čech complex generated over a spatial Poisson point process.
We will show that there is a sequence of sharp phase transitions (for different degrees of homology) and also explore the behavior of the complex inside each critical window.

04/03/2022 2:00 PMMB503 + streamedBelinda Wickes (QMUL)Separating path systems for complete graphs
For any graph G, a family S of subsets of the edges of G is said to be a separating path system for G if both of the following hold. Firstly, for every pair of edges e,f in E(G), there is some P in S with the property that P contains e but not f. Secondly, every element of S is a path in G. A natural question is ‘how small can such a separating path system be?’.
FalgasRavry, Kittipassorn, Korándi, Letzter and Narayanan conjectured that for any graph G on n vertices, the size of a separating path system for G is O(n). They also proved this conjecture for certain graphs. In this talk we focus on the case where G is the complete graph K_{n}, giving a method for finding small separating path systems. 
18/03/2022 2:00 PMMB503 + streamedTheo Thiery (QMUL)Improved approximation algorithm for the maximum weight independent set problem in (k+1)claw free graphs.We study the problem of finding a maximum weight independent set (MWIS) in a (k+1)claw free graph. In this classical combinatorial optimization problem, we are given a weighted graph with no induced dclaw and the goal is to find a subset of the vertices of maximum weight such that no two vertices in the subset share an edge. A special case of this problem is the (hyper)graph matching problem where edges have up to k vertices.While there is a (k+1)/3approximation algorithm for the unit weight case, the weighted case has had a longstanding approximation ratio of (k+1)/2. In a recent paper, Neuwohner obtained an improvement over the previous bound but the order of magnitude of the improvement is 10^(7).As it is a dense problem, the talk will start by introducing the problem and covering recent results. Then, we will give an analysis of the former (d+1)/2approximation algorithm, and finish by highlighting the main ideas to improve upon Neuwohner's result and obtain a ratio of at most (k+1)/2  1/6.Ongoing work with Justin Ward.

08/04/2022 1:30 PMMB503 + streamedAlexey Pokrovskiy (UCL)Rainbow matchings in coloured multigraphsThis talk will be about taking a coloured multigraph and finding a rainbow matching using every colour. There's a variety of conjectures that guarantee a matching like this in various classes of multigraphs (eg the AharoniBerger Conjecture). In the talk, I'll discuss an easy technique to prove asymptotic versions of conjectures in this area.
This is joint work with David Munhá Correia and Benny Sudakov

27/05/2022 1:00 PMMB503Asier Calbet Ripodas (QMUL)Triangle saturated graphs with large minimum degree
Given a graph H, we say that a graph G is Hsaturated if G is maximally Hfree, meaning G contains no copy of H but adding any new edge to G creates a copy of H. The general saturation problem is to determine sat(n,H), the minimum number of edges in an Hsaturated graph G on n vertices.
The special case when H is a triangle is straightforward – it is an easy exercise to show that sat(n,K_3) = n − 1 for n ≥ 1 and that the unique extremal graph is a star. Note that a star has many vertices of degree 1. One might ask what happens if we forbid such small degree vertices. We then have the more difficult problem of determining sat(n,K_3,t), the minimum number of edges in a triangle saturated graph G on n vertices that additionally has minimum degree at least t.
Day showed that for fixed t, sat(n,K_3,t) = tn − c(t) for large enough n, where c(t) is a constant depending on t. He proved the bounds 2^t t^(3/2) << c(t) ≤ t^(t^(2t^2)). We show that the order of magnitude of c(t) is 4^t / √t .
The order of magnitude of c(t) turns out to be intimately related to Bollobás’ celebrated Two Families Theorem. We end by presenting a conjectured generalisation of the Two Families Theorem, which, if proven, would allow one to extend these results from K_3 to general K_r. 
17/08/2022 2:00 PMMB 503 + streamedNick Wormald (Monash)Playing games with the kcore
Given an integer b>0. two players, called Maker and Breaker, play a game on a graph G. In each round, Breaker claims b unclaimed edges and then Maker claims one. Maker wins if she can form a giant component (one with at least tn vertices, for some given constant t>0) from the edges she claimed. If the edges are all used up before she manages this, Breaker wins. Clearly there is either a winning strategy for Maker, or one for Breaker. The larger b is, the easier it is for Breaker to win.
Suppose that G is drawn randomly from the common random graph model G(n,p). Maker cannot possibly win unless $G$ has a giant component. The threshold value of p for which this giant component occurs (with high probability, i.e. close to 1) is 1/n. So let p=c/n for c>1. We can determine the smallest b for which Breaker wins with high probability.
A key part of our proof involves properties of the kcore of the random graph. I will give some background on this, as well as on MakerBreaker games, and describe how the two have come together in this problem. This is joint work with Rani Hod, Michael Krivelevich, Tobias Muller and Alon Naor. 
27/01/2023 2:00 PMMB503Marc Roth (Oxford)The complexity of counting small induced subgraphsIn this talk I will present recent results on the parameterised and finegrained complexity of the problem of counting induced kvertex subgraphs that satisfy a graph property P, in an nvertex host graph G. More precisely, the goal is to understand for which P this problem becomes tractable, given that k is significantly smaller than n. Formally, the question is: For which graph properties P is the problem in the class FPT, that is, solvable in time f(k) * poly(n), for some computable function f.Initial work on this problem is due to Jerrum and Meeks (JCSS 15, TOCT 15) who answered the question for a variety of graph properties such as properties that are closed under taking graph minors. More recent work is built upon the framework of socalled graph motif parameters due to Curticapean, Dell and Marx (STOC 17). In this talk, I will provide an introduction to graph motif parameters and show how to use them to obtain complete complexity classifications for a wide range of graph properties, including for example all hereditary graph properties.
Based on joint works with Jacob Focke, Johannes Schmitt, and Philip Wellnitz.

14/10/2022 2:00 PMMB503Barnabás Janzer (Cambridge)Large hypergraphs without tight cycles
An runiform tight cycle of length k>r is a hypergraph with vertices v_1,…,v_k and edges {v_i,v_(i+1),…,v_(i+r−1)} (for all i), with the indices taken modulo k. Sós, and independently Verstraëte, asked the following question: how many edges can there be in an nvertex runiform hypergraph if it contains no tight cycles of any length? In this talk I will review some known results, and present recent progress on this problem.

30/09/2022 2:00 PMMB503Viresh Patel (QMUL)Hamilton cycles in regular oriented and directed graphs
Classical theorems of Dirac and of GhouilaHouri establish the minimum degree theshold that guarantees the existence of a Hamilton cycle in a graph and in a directed graph respectively. (For oriented graphs, the degree threshold was established much more recently.) By imposing suitable regularity and/or connectivity conditions on graphs, one can lower the degree threshold at which a Hamilton cycle is guaranteed to appear, and this is quite well understood in the case of graphs. Conjectures of Kuhn and Osthus and of Jackson describe the corresponding situation for directed graphs and oriented graphs respectively. I will discuss approximate solutions to these conjectures.
This is based on joint work with Allan Lo and Mehmet Akif Yildiz.

21/10/2022 2:00 PMGC103Alp Müyesser (UCL)A random HallPaige conjecture (Please note the nonstandard room!)
A rainbow matching in an edgecoloured graph is a matching whose edges all have different colours. Let G be a group of order n and consider an edgecoloured complete bipartite graph, whose parts are each a copy of the group G, and the edge (x, y) gets coloured by the group element xy. We call this graph the multiplication table of G. For which groups G does the multiplication table of G have a rainbow matching? This is an old question in combinatorial group theory due to Hall and Paige, with close connections to the study of Latin squares. The problem has been resolved in 2009 with a proof relying on the classification of finite simple groups. In 2021, a "simpler" proof for large groups appeared, this time using tools from analytic number theory. We present a third resolution of this problem, again only for large groups, and using techniques from probabilistic combinatorics. The main advantage of our approach is that we are able to find rainbow matchings in randomlike subgraphs of the multiplication table of G. This flexibility allows us to settle numerous longstanding conjectures in combinatorial group theory.

28/10/2022 2:00 PMMB503Franziska Eberle (LSE)Online Graph Exploration  Old and New Results
Exploring unknown environments is a fundamental task in many domains, e.g., robot navigation, network security, and internet search. In this talk, we give an overview of the current state of the art in online graph exploration in the fixed graph scenario. We provide details and lower bound examples of some algorithms such as the Nearest Neighbour (NN) algorithm with its competitive ratio of O(log n).
Afterwards, we design a general framework to robustify algorithms that carefully interpolates between a given algorithm and NN. We prove new performance bounds that leverage the individual good performance on particular inputs while establishing robustness to arbitrary inputs. This robustification schemes also allows us to initiate the study of a learningaugmented variant of the problem by adding access to machinelearned predictions and naturally integrating these predictions into the NN algorithm. This method significantly outperforms any known online algorithm if the prediction is of high accuracy while maintaining good guarantees when the prediction is of poor quality. 
04/11/2022 2:00 PMMB503Jane Tan (Oxford)Induced subgraphs of induced subgraphs of large chromatic number
If a graph has large chromatic number, must it contain induced subgraphs with some particular local structure witnessing this property? A positive answer here would be useful in studying chiboundedness, where an important strategy involves dropping down to an induced subgraph which still has high chromatic number but is structurally simpler (for instance, trianglefree). However, earlier this year, a string of papers by Carbonero, Hompe, Moore and Spirkl, and then Briański, Davies and Walczak provided fascinating constructions which in particular show that there are K_{p+1}free graphs of large chromatic number in which every induced subgraph of large chromatic number contains a copy of K_p. In this talk, we'll discuss generalisations of this result replacing cliques by arbitrary graphs F with at least one edge.

02/12/2022 2:00 PMMB503Alex McDonough (UC Davis)RotorRouting Induces the Only Consistent Sandpile Torsor Structure on Plane Graphs
Every finite graph has an associated sandpile group, which can be described in terms of chipfiring. A sandpile torsor algorithm is a map which associates each plane graph (i.e. planar embedding) with a free transitive action of its sandpile group on its spanning trees. We define a notion of consistency, which requires a torsor algorithm to be preserved with respect to a certain class of contractions and deletions. We then show that the rotorrouting sandpile torsor algorithm (which is equivalent to the Bernardi algorithm) is consistent. Furthermore, we demonstrate that there are only three other consistent algorithms, which all have the same structure as rotorrouting. This proves a conjecture of Klivans. Joint work with Ankan Ganguly.

16/12/2022 2:00 PMMB503Katherine Staden (Open University)Ringel's conjecture on treepacking
When can (the edgeset of) a graph G be decomposed into copies of a given graph H? This question goes all the way back to Euler; despite this, the setting where the number of vertices in G and H are comparable is not yet wellunderstood. I will talk about the resolution of a conjecture of Ringel from 1963 where G is the complete graph on 2n+1 vertices and H is any given tree with n edges. This is joint work with Peter Keevash; the conjecture was independently resolved by Montgomery, Pokrovskiy and Sudakov.

18/11/2022 2:00 PMMB503Konrad Anand (QMUL)Lazy DepthFirst Sampling of Spin SystemsWe examine the new sampling technique, lazy depthfirst sampling, particularly as applied to spin systems.We are given a graph G = (V,E), q `spins’ or `colours’, and vector b of weights for each spin, and a matrix A of weights of interactions between spins. Given a configuration \sigma, i.e., an assignment of a spin to each v \in V, the weight of the configuration is the product of the weights of each vertex and each edge. Normalizing gives us a probability distribution.The goal is to sample a configuration on a subset of the graph. We do so in a lazy fashion, breaking the distribution into a mixture of a simple measure and a difficult measure and recursing only when we encounter the difficult. This provides interesting perfect sampling results.

09/12/2022 2:00 PMMB503Tony Guttmann (Melbourne)Selfavoiding walks crossing a domain and gerrymander sequences
The problem of selfavoiding walks in a domain (e.g. a finitesize square or rectangular subset of the square lattice, or a triangular or hexagonal subset of the hexagonal lattice) is both a combinatorial problem of considerable interest, and has applications to telecommunications. Designing efficient algorithms to study this problem by exact enumeration has recently led to spectacular advances in reducing computational complexity. I will report on recent joint work with Iwan Jensen (Flinders University) and Aleks Owczarek (Melbourne) which has enabled us to conjecturally determine the asymptotics very precisely. Furthermore, in current work we have proved the equivalence of this problem to the seemingly unrelated combinatorial problem of gerrymander sequences, and have consequently been able to give very precise asymptotic estimates for that problem too.

03/03/2023 2:00 PMMB503Imre Leader (Cambridge)Large sumsets from small subsets
Many classical theorems of additive combinatorics state that a certain sumset is large. For example, the CauchyDavenport theorem gives a lower bound on the size of
the sumset A+B for two subsets A and B of the cyclic group of order p. What would happen if we insisted that, in forming the sums, we were only allowed to use a bounded number of elements of B? How close could we get to the lower bound of A+B1 given by the CauchyDavenport theorem, for example? (Joint work with Bela Bollobas and Marius Tiba.) 
17/02/2023 2:00 PMMB503Eoin Long (Birmingham)A bipartite version of the Erdős–McKay conjecture
Erdős and McKay conjectured that if all homogeneous sets in an nvertex graph are of order O(log n) then the graph contains induced subgraphs of each size from {0,1,…,Ω(n^2)}. In this talk I will outline a proof of a bipartite version of this conjecture: if all balanced homogeneous sets in an n×n bipartite graph are of order O(log n) then the graph contains induced subgraphs of each size from {0,1,…,Ω(n^2)}.
Based on joint work with Laurentiu Ploscaru.

31/03/2023 2:00 PMMB503Andrea Freschi (Birmingham)The induced saturation problem for posets
For a fixed poset P, a family F of subsets of [n] is induced Psaturated if F does not contain an induced copy of P, but for every subset S of [n] such that S \notin F, then P is an induced subposet of F \cup {S}. The size of the smallest such family F is denoted by sat*(n,P).
In recent years, there has been a growing interest in tackling the problem of determining sat*(n,P). Keszegh, Lemons, Martin, Pálvölgyi and Patkós [Journal of Combinatorial Theory Series A, 2021] proved that there is a dichotomy of behaviour for this parameter: given any poset P, either sat*(n,P)=O(1) or sat*(n,P) ≥ log _2 n. Furthermore, they conjectured that either sat*(n,P)=O(1) or sat*(n,P) ≥ n+1.
In this talk we present some progress on this conjecture, namely that either sat*(n,P)=O(1) or sat*(n,P) ≥ 2 \sqrt(n2). This is joint work with Simón Piga, Maryam Sharifzadeh and Andrew Treglown.

10/03/2023 2:00 PMMB503Jessica Enright (Glasgow)Copsandrobbers on multilayer graphs
I will describe the game of copsandrobbers and then its generalisation to multilayer graphs. In this setting, a graph consists of a single set of vertices with multiple (potentially intersecting) edge sets. We allow the cops and robber to move only on their assigned layer, and ask of the cops can be guaranteed to catch the robber in finite time. Using several examples, I’ll show that initial intuition about the best way to allocate cops to layers is not always correct. I will outline arguments showing that the number of cops required to catch a robber in a multilayer graph is neither bounded from above nor below by any function of the cop numbers of the individual layers. Additionally, we’ll talk about a question of worstcase division of a simple graph into layers: given a simple graph G, what is the maximum number of cops required to catch a robber over all multilayer graphs where each edge of G is in at least one layer and all layers are connected? For cliques, suitably dense random graphs, and graphs of bounded treewidth, we have determined this parameter up to multiplicative constants.
Lastly I’ll outline a multilayer variant of Meyniel's conjecture, and show the existence of an infinite family of graphs whose multilayer cop number is bounded from below by a constant times n / log n, where n is the number of vertices in the graph. 
24/02/2023 2:00 PMMB503David Hannon (QMUL)Optimal Impartial Selection
We consider directed graphs without loops, and rules that select a subset of the vertices in any graph. A selection rule is impartial if the selection of a vertex is independent of its outgoing edges and we also aim to make our selection rule competitive, that is, select vertices with high indegree. This models peer selection where vertices are candidates and directed edges represent votes. We wish to select highly voted candidates such that a candidate cannot influence their own selection.

24/03/2023 2:00 PMMB503Candida Bowtell (Warwick)Large rainbow structures in complete graphs
Given a properly coloured complete graph, a natural problem to consider is that of finding large and spanning rainbow substructures. Looking at matchings, we know that in some optimal proper colourings of the complete balanced bipartite graph one can't obtain a perfect rainbow matching. However, proving the RyserBrualdiStein Conjecture for large even n, Montgomery recently showed that one can always guarantee a rainbow matching missing at most two vertices in any optimal colouring. Looking at paths in properly coloured (nonbipartite) complete graphs, again it is known that we can't guarantee a rainbow Hamilton path. However, Andersen conjectured that one can always find a rainbow path avoiding at most one vertex. In this talk we'll discuss these problems in more detail, including what is already known and some current work in progress with Alistair Benford and Richard Montgomery.

16/06/2023 2:00 PMMB503Catarina Carvalho (Hertfordshire)Digraphs with caterpillar duality
We search for the class of digraphs whose obstruction sets, in the digraph homomorphism problem, consist of caterpillars. The conjecture being that this class of digraphs should be the same as the class of digraphs that are preserved by majority and set function polymorphisms. This is work in progress.

17/03/2023 2:00 PMMB503Mark Walters (QMUL)Cops and Robbers and constructible graphs
The simplest Cops and Robbers game is as follows. Both the cop and robber are placed on a graph and then they alternately take turns where they either move to a neighbouring vertex or remain at the same vertex. The cop wins if, at some point, he is at the same vertex as the robber – the robber wins if he can ensure this never happens.
If the graph is finite then it is easy to show that a graph is copwin if and only if it is constructible, meaning that the graph can be obtained from the onepoint graph by adding dominated vertices one at a time.
But if the graph is infinite then the situation is more complicated. We will discuss what happens, including the first example of a copwin graph that is not constructible.
Joint work with Maria Ivan and Imre Leader 
26/04/2023 10:30 AMMB503Javier Cembrano (TU Berlin)Multidimensional political apportionment
Deciding how to allocate the seats of a deliberative assembly is one of the most fundamental problems in the political organization of societies, and has been widely studied over already two centuries. The idea of proportionality is at the core of most approaches to tackle this problem, and this notion is captured by the divisor methods, such as the Jefferson/D'Hondt method. In a seminal work, Balinski and Demange extended the singledimensional idea of divisor methods to the setting in which the seat allocation is simultaneously determined by two dimensions, and proposed the socalled biproportional apportionment method. The method, currently used in several electoral systems, is however limited to two dimensions and the question of extending it is considered to be an important problem both theoretically and in practice.
In this work we initiate the study of multidimensional proportional apportionment. We first formalize a notion of multidimensional proportionality that naturally extends that of Balinski and Demange. By means of analyzing an appropriate integer linear program we are able to prove that, in contrast to the twodimensional case, the existence of multidimensional proportional apportionments is not guaranteed and deciding their existence is NPcomplete. Interestingly, our main result asserts that it is possible to find approximate multidimensional proportional apportionments that deviate from the marginals by a small amount. The proof arises through the lens of discrepancy theory, mainly inspired by the celebrated BeckFiala Theorem. We finally evaluate our approach by using the data from the recent 2021 Chilean Constitutional Convention election.
This is joint work with José Correa and Victor Verdugo. 
23/06/2023 2:00 PMMB503Robert Johnson (QMUL)Asymmetry of 2step Transit Probabilities in Regular Graphs
Suppose that the vertices of a regular graph are coloured red and blue with an equal number of each (we call this a balanced colouring). Since the graph is undirected, the number of edges from a red vertex to a blue vertex is clearly the same as the number of edges from a blue vertex to a red vertex. However, if instead we count walks of length 2, then this symmetry disappears. How extreme can this asymmetry be?
More precisely, given a dregular graph, for which pairs (x,y) is there a balanced colouring for which the probability that a random walk starting from a red vertex stays within the red class for at least 2 steps is x, and the corresponding probability for blue is y?
We will discuss a variety of questions and results on this including a general bound for dregular graphs, an exact (asymptotic) answer for the 2dimensional torus, and many open problems.
Joint work with Ron Gray. 
29/09/2023 2:00 PMMB503Ilya Shkredov (LIMS)The popularity gapSuppose that A is a finite, nonempty subset of a cyclic group of either infinite or prime order. We show that if the difference set A − A is “not too large”, then there is a nonzero group element with at least as many as (2 + o(1))A^2/A − A representations as a difference of two elements of A; that is, the second largest number of representations is, essentially, twice the average. Here the coefficient 2 is best possible. We also prove continuous and multidimensional versions of this result, and obtain similar results for sufficiently dense subsets of an arbitrary abelian group.This is a joint paper with V.F. Lev.

06/10/2023 2:00 PMMB503Namrata (Warwick)Kneser graphs are Hamiltonian.
For integers k ≥ 1 and n ≥ 2k + 1, the Kneser graph K(n, k) has as vertices all kelement subsets of an nelement ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph K(5,2). This problem received considerable attention in the literature, including a recent solution for the sparsest case n = 2k + 1. The main contribution of this paper is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph J(n,k,s) has as vertices all kelement subsets of an nelement ground set, and an edge between any two sets whose intersection has size exactly s. Clearly, we have K(n, k) = J(n, k, 0), i.e., generalized Johnson graph include Kneser graphs as a special case. Our results imply that all known families of vertextransitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász’ conjecture on Hamilton cycles in vertextransitive graphs from 1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.

13/10/2023 2:00 PMMB503Amedeo Sgueglia (UCL)Rainbow subgraphs in uniformly coloured perturbed graphsWe consider the model of randomly perturbed graphs, which is the union of any nvertex graph G_delta with minimum degree at least delta n and the binomial random graph G(n,p). In this talk, we discuss the problem of finding rainbow subgraphs in G_delta cup G(n,p), when each edge in the union gets a colour independently and uniformly at random from a fixed palette.
This is joint work with Kyriakos Katsamaktsis and Shoham Letzter. 
20/10/2023 2:00 PMMB503Tom Johnston (Bristol)Shotgun assembly of random graphs
How much local information is needed to reconstruct a graph? In the graph shotgun assembly problem, we are given the balls of radius r around the vertices of a graph and we are asked to identify the graph. We will consider this problem for the ErdősRényi random graph G(n,p) for a wide range of values of r and discuss the thresholds on p for when the graph is or is not reconstructible with high probability. In particular, we will give the threshold for each r ≥ 3.

23/02/2024 2:00 PMMB503Alex Scott (Oxford)A few steps towards the ErdosHajnal Conjecture.
A typical graph contains cliques and independent sets of no more than logarithmic size. The ErdosHajnal Conjecture asserts that if we forbid some induced subgraph H then we can do much better: the conjecture claims that there is some c=c(H)>0 such that every Hfree graph G contains a clique or independent set of size at least G^c. The conjecture looks far out of reach, and is only known for a small family of graphs. We will survey some recent progress.
Joint work with Tung Nguyen and Paul Seymour. 
03/11/2023 2:00 PMMB503Matthew Jenssen (KCL)On the evolution of trianglefree graphs in the ordered regimeErdos, Kleitman and Rothschild proved that the number of trianglefree graphs on n vertices is asymptotic to the number of bipartite graphs; or in other words, a typical trianglefree graph is bipartite. Osthus, Promel and Taraz proved a sparse analogue of this result: if m > (sqrt{3}/4 +epsilon) n^{3/2} sqrt{log n}, a typical trianglefree graph on n vertices with m edges is bipartite (and this no longer holds below this threshold).What do typical trianglefree graphs at sparser densities look like and how many of them are there? We consider what we call the ordered regime, where typical trianglefree graphs are not bipartite but have a dense maxcut. In this regime we prove asymptotic formulas for the number of trianglefree graphs and give a precise probabilistic description of their structure. This leads to further results such as determining the threshold at which typical trianglefree graphs are qcolourable for q ≥ 3, determining the threshold for the emergence of a giant component in the complement of a maxcut, and many others.This is joint work with Will Perkins and Aditya Potukuchi.

17/11/2023 2:00 PMMB503Nora Frankl (Open University)Helly numbers of exponential lattices
The Helly number of a set in the plane is the smallest N such that the following is true. If any N members of a finite family of convex sets contains a point of S, then there is a point of S which is contained in all members of the family. An exponential lattice with base x consists of points whose coordinates are positive integer powers of x. We prove lower and upper bounds on Helly numbers of exponential lattices in terms of x, and we determine their values exactly in some cases. We also consider asymmetric exponential lattices, and characterise those that have finite Helly numbers. Joint work with Gergely Ambrus, Martin Balko, Attila Jung and Márton Naszódi.

24/11/2023 2:00 PMMB503Nikolaos Fountoulakis (Birmingham)Nonmonotone dynamics in random graphs
In this talk, we will discuss the evolution of classes on nonmonotone dynamics on a binomial random graph. In particular, we will start with majority dynamics either with two or more states. There, each vertex updates their state adopting the state that has the majority among its neighbours.
We will continue with generalisations of this dynamics in the context of population games. Assume that a 2player symmetric game with 2 strategies is played between the adjacent members of the vertex set.
(In this context the states are the strategies.) Players/vertices update their strategies synchronously: at each round, each player selects the strategy that is the best response to the current set of strategies its neighbours play. We show that such a system reduces to generalised majority and minority dynamics. We show rapid convergence to unanimity for p in a range that depends on a certain characteristic of the payoff matrix. In the presence of a certain type of bias in the payoff matrix, we determine a sharp threshold on p above which the largest connected component reaches unanimity with high probability, and below which this does not happen.
This is joint work with Calina Durbac and Jordan Chellig 
15/12/2023 2:00 PMMB503Adva Mond (Cambridge)Minimum degree edgedisjoint Hamilton cycles in random directed graphsAt most how many edgedisjoint Hamilton cycles does a given directed graph contain? A trivial upper bound is the minimum between the minimum out and indegrees. We show that a typical random directed graph D(n,p) contains precisely this many edgedisjoint Hamilton cycles, given that p ≥ (log^C n)/n where C is some fixed integer, which is optimal up to a factor of polylog n.Our proof provides a randomised algorithm to generate the cycles and uses a (relatively) recent "online sprinkling" idea, as was introduced by Ferber and Vu, to generate D(n,p), allowing us to control some key properties of the graph.This is a joint work with Asaf Ferber and Kaarel Haenni.

10/11/2023 2:00 PMMB503ChienChung Huang (ENS, Paris)Robust Sparsification for Matroid Intersection with Applications
Matroid intersection is a classical optimization problem where, given two matroids over the same ground set, the goal is to find the largest common independent set. We show how to construct a certain "sparsifer": a subset of elements, of size O(S^{opt} \cdot 1/epsilon), where S^{opt} denotes the optimal solution, that is guaranteed to contain a 3/2 + epsilon approximation, while guaranteeing certain robustness properties. We call such a small subset a \emph{Density Constrained Subset} (DCS), which is inspired by the EdgeDegree Constrained Subgraph (EDCS) [Bernstein and Stein, 2015], originally designed for the maximum cardinality matching problem in a graph. Our proof is constructive and hinges on a greedy decomposition of matroids, which we call the \emph{densitybased decomposition}. We show that this sparsifier has certain robustness properties that can be used in oneway communication and randomorder streaming models.

26/01/2024 2:00 PMMB503Stefanie Gerke (RHUL)Lower bounds on the maximum bisection in a weighted graphs with bounded degree
A bisection in a graph is a cut in which the number of vertices in the two parts differ by at most 1. In this paper, we give lower bounds for the maximum weight of bisections of edgeweighted graphs with bounded maximum degree. We show a tight lower bound for the maximum size of bisections in 3regular graphs. We also consider edgeweighted trianglefree subcubic graphs and show that a much better lower bound (than for edgeweighted subcubic graphs) holds for such graphs if we exclude K1,3. This is joint work with Gregory Gutin, Anders Yeo, and Yacong Zhou.

09/02/2024 2:00 PMMB503Robert Brignall (Open University)Unbounded cliquewidth in hereditary graph classes
Graph width parameters play an important role in the complexity of algorithms on graphs. For example, the metatheorems of Courcelle and coauthors typically say something like the following: an evaluation problem can be solved in polynomial time on some graph class if (1) the problem can be expressed in some restricted form of logic, and (2) every graph in the class has a suitable bounded width parameter.
One wellknown parameter is treewidth: Robertson and Seymour showed that there is a single fundamental obstruction to minorclosed classes having bounded treewidth: the class of planar graphs. (That is, a class has bounded treewidth if and only if it forbids some planar graph as a minor). More recently, Geelen, Kwon, McCarty and Wollan showed that there is a similar single fundamental obstruction to vertexminorclosed classes having bounded rankwidth: the class of circle graphs.
For cliquewidth (which is strongly related to rankwidth) and hereditary graph classes (closed under taking induced subgraphs), the situation is much worse. Two minimal hereditary classes with unbounded cliquewidth were found in 2011 by Lozin, and in the 13 years since more have been uncovered, including a countably infinite collection in 2018. In this talk, I will present a framework that can be used to construct most of the known minimal classes, and also uncountably many more. Time permitting, I will also discuss how the hunt for minimal classes is not the only task if one wanted to establish a complete characterisation.
This talk is based on joint work with Dan Cocks.

16/02/2024 2:00 PMMB503Leo Versteegen (Cambridge)Linear graph codes
A linear graph code is a family C of graphs on n vertices such that the symmetric difference of the edge sets of any two graphs in C is also the edge set of a graph in C. In the talk, we will investigate the maximal size of a graph code that does not contain a copy of a fixed graph H. There are graphs H that are not contained in linear codes of size 2^{ \binom{n}{2} } / exp(sqrt(log n)), but we will show that for almost all graphs H with an even number of edges, there exists eps_H>0 such that a linear graph code without copy of H can contain at most 2^{\binom{n}{2}} / n^{eps_H} graphs.

02/02/2024 2:00 PMMB503Mark Jerrum (QMUL)The computational complexity of the Tutte polynomial: 34 years on
In 1990 Jaeger, Vertigan and Welsh published a paper "On the computational complexity of the Jones and Tutte polynomials" in Math. Proc. Cambridge Philos. Soc. In doing so they started a flourishing line of enquiry that brought together researchers in combinatorics, theoretical computer science, probability and statistical physics. The 157 citations listed on MathSciNet attest to the impact of the paper. Dominic Welsh died on 30th November, and this talk is a small contribution to his memory.
The Tutte polynomial is a twovariable polynomial associated with a matroid. If you are not a fan of matroids, don't worry: the only ones that will arise in this talk are very concrete, specifically, graphic matroids (associated with undirected graphs) and binary matroids (associated with sets of vectors over GF(2)). I'll define the Tutte polynomial, and provide interpretations of the polynomial evaluated at certain points and along certain hyperbolas in R^2. I'll survey the results of Jaeger, Vertigan and Welsh, which give a complete picture of the computational complexity of exactly evaluating the Tutte polynomial in the graphic case. I'll then describe a couple of substantial fairly recent advances: (i) an efficient algorithm by Anari, Liu, Oveis Gharan and Vinzant for approximating the Tutte polynomial in a region of R^2 that includes network reliability; (ii) a proof by Noble of a "lost theorem" of Vertigan concerning the number of bases of a binary matroid.

01/03/2024 2:00 PMMB503Angelica Pachon (Swansea)On random graph models with properties of real networks
Understanding mechanisms for generating random graph models with properties of real networks is an important topic in complex networks. Although there is a large literature on random graph models with a powerlaw degree distribution, a positive clustering coefficient or with a giant component, much work remains to be done to generate random graph models with several of these properties. In this talk we will discuss some results about random graph models with powerlaw degree distribution and giant component. At the end, we will present some work in progress about random graph models with powerlaw degree distribution and positive clustering coefficient.

15/03/2024 2:00 PMMB503Simona Boyadzhiyska (Birmingham)Covering real grids with multiplicityGiven a field F, finite subsets S1, . . . ,Sd ⊆ F, and a point p ∈ S1 × · · · × Sd, what is the smallest number of hyperplanes needed to cover all points of S1 × · · · × Sd \ {p} ⊆ F^d while omitting p entirely? This question was answered precisely in a celebrated paper of Alon and Furedi.We will discuss a variant of this problem in which every point in S1 × · · · × Sd \ {p} must be covered at least k ≥ 1 times, while the remaining point p is again left uncovered. In contrast to the case k = 1, this problem is generally not well understood for larger k. Recently Clifton and Huang, and Sauermann and Wigderson investigated the special case where F is the reals and the grid is {0, 1}^d. A natural next step is to consider larger grids over the reals. In this talk, we will focus on the twodimensional setting and determine the answer for several different types of grids.
This is joint work with Anurag Bishnoi, Shagnik Das, and Yvonne den Bakker. 
22/03/2024 2:00 PMMB503Edith Elkind (Oxford)Fairness in Multiwinner Voting
Many cities around the world allocate a part of their budget based on residents’ votes, following a process known as participatory budgeting. It is important to understand which outcomes of this process should be viewed as fair, and whether fair outcomes could be computed efficiently. We summarise recent progress on this topic. We first focus on a special case of participatory budgeting where all candidate projects have the same cost (known as multiwinner voting), formulate progressively more demanding notions of fairness for this setting, and identify efficiently computable voting rules that satisfy them. We then discuss the challenges of extending these ideas to the general model.

05/04/2024 2:00 PMMB503Kyriakos Katsamaktsis (UCL)Ascending subgraph decomposition
We prove for large graphs the following conjecture of Alavi, Boals Chartrand, Erdős and Oellermann from 1987: any graph with (m+1)m/2 edges can be decomposed into graphs G_1,...,G_m such that G_i has exactly i edges and is isomorphic to a subgraph of G_{i+1}. This is joint work with Shoham Letzter, Alexey Pokrovskiy and Benny Sudakov.

12/04/2024 2:00 PMMB503Neil Olver (LSE)A strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column
We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two nonzero entries per row, or at most two nonzero entries per column. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale's 9th problem.
Our approach is based on the recent primaldual interior point method (IPM) due to Allamigeon, Dadush, Loho, Natura and Végh (FOCS '22). They show that the number of iterations needed by the IPM can be bounded in terms of the straight line complexity of the central path; roughly speaking, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. As our main contribution, we show that the straight line complexity of any minimum cost generalized flow instance is polynomial in the number of arcs and vertices. By a reduction of Hochbaum, the same bound applies to any linear program with at most two nonzeros per column or per row. Further, we demonstrate how to handle initialization, and how to ensure that the bit complexity of each iterate remains bounded during the execution of the algorithm.
Joint work with Daniel Dadush, Zhuan Khye Koh, Bento Natura and László Végh. 
03/05/2024 2:00 PMMB503Asier Calbet Rípodas (QMUL)The asymptotic behaviour of sat(n,F}
Given a family F of graphs, we say that a graph G is Fsaturated if it is maximally Ffree, meaning G does not contain a graph in F but adding any new edge to G creates a graph in F. We then define sat(n,F)$ to be the minimum number of edges in an Fsaturated graph on n vertices. In 1986, Kászonyi and Tuza showed that sat(n,F)=O(n)$ for all families F and Tuza conjectured that for singleton families sat(n,F)/n converges. Tuza's Conjecture remains wide open. In this talk, I will discuss recent results about the asymptotic behaviour of sat(n,F)$, mostly in the sparse regime sat(n,F) ≤ n+o(n)$, in each of the cases when F is a singleton, when F is finite and when F is possibly infinite.
Joint work with Andrea Freschi.

20/08/2024 11:00 AMMB503. Please note the nonstandard time.Kevin Schewior (SDU)Recent Advances in Stochastic Function Evaluation: Score Classification and Voting
In stochastic function evaluation, one is given a (succinctly represented) Boolean function and n (typically independent) random variables with known probability distributions. Each of the variables can be queried at known cost, which reveals the value of the respective variable. The goal is to efficiently compute a strategy for querying variables that determines the value of the function applied to these variables at (approximately) minimum expected cost.
In the first part of this talk, we consider scoreclassification functions (Gkenosis, Grammel, Hellerstein, and Kletenik; 2018). Here, variables are Boolean and the function value only depends on which given subinterval of [0, n] the total number of successes is in. We give simple nonadaptive constantfactor approximation algorithms. This part is joint work with Benedikt Plank.
In the second part of this talk, we consider a setting where the random variables correspond to votes, their values correspond to candidates, and the value of the function is the outcome of an election. We give adaptive constantfactor approximations for the absolutemajority and relativemajority versions of this problem. This part is joint work with Lisa Hellerstein and Naifeng Liu.