Combinatorics Study Group

The Combinatorics Study Group seminar is held from 4pm-5pm (unless otherwise stated) on Fridays, in room W316 of the Queen's building at Queen Mary, University of London. We meet for tea before the seminar from 3.30pm in the Senior Common Room of the Queens building. (The Queen's building is on Mile End road midway between Stepney Green and Mile End Underground Stations. For more information, see the directions here). All the seminar attendees are cordially invited to join the speaker for drinks after the seminar, in the bar in the Queens building.

Current programme:

Year :

Date

Room

Speaker

Title
02/10/2009 5:30 PM

M103

Diane Donovan (Queensland)

The importance of latin trades in the study of completing partial latin squares

Seminar series:

Combinatorics Study Group

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 PM

M103

John Talbot (UCL)

Triangles in tripartite graphs

Seminar series:

Combinatorics Study Group

Mantel's theorem (1907) says that a graph with n vertices and more than n² /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 PM

M103

Aidan Roy

Optimal designs in complex projective space, 1

Seminar series:

Combinatorics Study Group
06/11/2009 4:30 PM

M103

Aidan Roy

Optimal designs in complex projective space, 2

Seminar series:

Combinatorics Study Group
13/11/2009 4:30 PM

M103

Thomas Prellberg

Counting area-weighted Dyck-paths in a slit

Seminar series:

Combinatorics Study Group
27/11/2009 4:30 PM

M103

Olof Sisask

Fourier analysis and approximate structure in additive combinatorics, 1

Seminar series:

Combinatorics Study Group

Given a somewhat large subset A of F_pⁿ, an n-dimensional 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 two-part 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 almost-periodicity, which we shall be able to translate into tangible combinatorial results. I plan to assume very few prerequisites.
04/12/2009 4:30 PM

M103

Olof Sisask

Fourier analysis and approximate structure in additive combinatorics, 2

Seminar series:

Combinatorics Study Group

Given a somewhat large subset A of F_pⁿ, an n-dimensional 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 two-part 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 almost-periodicity, which we shall be able to translate into tangible combinatorial results. I plan to assume very few prerequisites.
11/12/2009 4:30 PM

M103

Raul Mondragon

Two problems on connectivity of networks

Seminar series:

Combinatorics Study Group
01/01/2014 4:30 PM

M103

Viresh Patel (QMUL)

A domination algorithm for {0,1}-instances of the travelling salesman problem

Seminar series:

Combinatorics Study Group

The development of approximation algorithms for NP-hard 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 well-known 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\}$-edge-weighting 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 polynomial-time 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 PM

M103

Mark Walters (QMUL)

Fast wins in n-in-a-row games

Seminar series:

Combinatorics Study Group

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 PM

M103

Trevor Pinto (QMUL)

Saturated subgraphs of the hypercube

Seminar series:

Combinatorics Study Group
28/02/2016 4:30 PM

M103

Kitty Meeks (QMUL)

The parameterised complexity of subgraph counting problems

Seminar series:

Combinatorics Study Group
07/03/2014 4:30 PM

M103

Neville Ball (QMUL)

Cops and Robbers on Geometric Graphs

Seminar series:

Combinatorics Study Group

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 PM

M103

Tony Guttmann (Melbourne)

Calculation of the spanning tree constant for three-dimensional lattices

Seminar series:

Combinatorics Study Group

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 PM

M103

Donovan Young (QMUL, Physics)

The distribution of dominoes in the game of memory

Seminar series:

Combinatorics Study Group

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 dominoe? For the case p=n this is just the dominoe tiling problem solved by Kastelyn. This talk will investigate the case for the remaining values of p.
13/06/2014 5:30 PM

M103

Paul Renteln (California State University)

Reflection Group Numerology

Seminar series:

Combinatorics Study Group
22/08/2014 4:30 PM

Maths 103

Dillon Mayhew (Victoria University of Wellington)

Characterising representable matroids in two different ways

Seminar series:

Combinatorics Study Group

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 excluded-minors. 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 minor-minimal 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 PM

M103

Eoin Long (University of Oxford

Frankl-Rödl type theorems for codes and permutations

Seminar series:

Combinatorics Study Group

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 Frankl-Rö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 Frankl-Rödl type theorem for permutations with a
forbidden distance. Joint work with Peter Keevash.
03/10/2014 5:30 PM

M103

Simon Griffiths (University of Oxford)

Random Graph Processes

Seminar series:

Combinatorics Study Group

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 triangle-free 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
quasi-randomness 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 PM

M103

Dan Kral (University of Warwick)

Combinatorial limits and their relation to extremal combinatorics and property testing.

Seminar series:

Combinatorics Study Group

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 well-structured, 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 self-contained and no previous knowledge of the area is needed.
17/10/2013 5:30 PM

M103

Nick Day (QMUL)

Saturated graphs of prescribed minimum degree

Seminar series:

Combinatorics Study Group

A graph G is H-saturated 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_p-saturated 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 PM

M103

Robert Johnson (QMUL)

Strategy Stealing in Avoidance games

Seminar series:

Combinatorics Study Group

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 PM

M103

Olivier Henard (QMUL)

The random graph near the critical window: a probabilistic review.

Seminar series:

Combinatorics Study Group

In the Erd\"os-Renyi 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 non-concentrated 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 PM

4.01, Bancroft Road Teaching Rooms, Mile End Campus, QMUL.

Peter Cameron (St Andrews)

Regular Polytopes

Seminar series:

Combinatorics Study Group

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
3-dimensional 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 C-group}, 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 $n-k$ 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 PM

M103

Iain Moffat (RHUL)

From embedded graphs to delta-matroids.

Seminar series:

Combinatorics Study Group

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 delta-matroids play the role of matroids in topological graph theory. Delta-matroids 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 delta-matroids, and that embedded graphs provide an excellent guide for studying delta-matroids. Throughout this talk I will emphasise a direct analogy with the classical matroid-graph 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 PM

M103

Sam Alexander (UCL)

Biologically Unavoidable Sequences

Seminar series:

Combinatorics Study Group

A 'biologically unavoidable sequence' is an infinite sequence of colours from {1,2,…,n} that occurs in every infinite n-coloured directed acyclic graph satisfying some mild biologically-motivated axioms. We sketch: 1. that eventually-periodic 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 PM

M103

Alex 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
non-realisable 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
series-parallel 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 PM

M103

Richard 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 PM

M103

Bill Jackson (QMUL)

Generic rigidity of point-line frameworks

A point-line 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 `point-line 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 point-line framework is rigid. This is joint work with John Owen.
23/01/2015 4:30 PM

M103

Sean 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 PM

M103

Marcin 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 fixed-parameter tractable algorithm for Graph Isomorphism parameterized by the treewidth that relies on an isomorphic-invariant modification of the well-known Robertson-Seymour 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 AM

Adthasit 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 2-edge-connected plane graph has a Tutte trail. I will also discuss the relationship between Tutte trails and the conjecture of Carsten Thomassen that every 4-connected line graph is Hamiltonian.
13/02/2015 4:30 PM

M103

Akihiro 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 PM

M103

Bernd Schulze (Lancaster)

Rigidity of frameworks on expanding spheres

In this talk we will discuss the rigidity and flexibility of bar-joint frameworks in (d+1)-dimensional space whose vertices are constrained to lie on concentric d-spheres 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 3-space.

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 non-trivial symmetries, we also briefly discuss the impact of symmetry on the flexibility of frameworks on variable spheres.

This is joint work with Anthony Nixon, Shin-ichi Tanigawa and Walter Whiteley.
06/03/2015 4:30 PM

M103

Trevor Pinto (QMUL)

Directed Paths in the Cube

In 1997, Bollobás and Leader gave tight lower bounds for the number of edge-disjoint 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 down-set, B is an up-set and the paths are required to be directed (that is, the vertices in the path form a chain). I will sketch a novel compression-type argument that proves a stronger version of this conjecture.
13/03/2015 10:13 AM

M103

Alan 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) Hankel-totally positive if the Hankel matrix
$H = (a_{i+j})_{i,j \ge 0}$ associated to $(a_k)$ is (coefficientwise)
totally positive. The (coefficientwise) Hankel-total positivity of a
sequence $(a_k)$ implies its (coefficientwise) log-convexity, but is
much stronger. (For sequences of real numbers, Hankel-total 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 Stieltjes-type (or Jacobi-type)
continued fraction. As a consequence I can show that a number of
sequences of polynomials arising in enumerative combinatorics are
coefficientwise Hankel-totally 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 Hankel-totally positive
but which cannot be handled by this continued-fraction 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 PM

M103

Bhargav 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 PM

M103

Shabnam 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 Kadomtsev-Petviashvili (KP) Equation and well-known 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 Jimbo-Miwa equation. In light of this "modern combinatorics toolkit", we present several open questions on what may make a Wronskian-integrable PDE admit (or exclude) certain combinatorial structures.
10/04/2015 5:30 PM

M103

Benjamin Schröter (Berlin)

Matroidal Subdivisions, Dressians and Tropical Grassmannians

AttachmentSizeAbstract [PDF 135KB]135.88 KB
24/04/2015 5:30 PM

M103

Ivan Izmestiev

Impossible 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 PM

M103

David 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 r-locally-F.) 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 d-dimensional 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 PM

M103

Abhishek 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 Marcus-Tardos theorem, proved by Klazar and Marcus.
22/05/2015 5:30 PM

M103

Katharine Clinch (QMUL)

Global Rigidity of Direction-Length Frameworks

A two-dimensional direction-length 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 end-vertices), and “length” edges L (which specify the distance between their end-vertices); together with a realisation p of this graph in the plane.

Given a direction-length 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 PM

M103

Anthony 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 PM

M103 (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 PM

M103 (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}{r-1}$. 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 PM

M103 (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 PM

M103 (Mathematical Sciences)

Ben Barber (University of Bristol)

Edge decompositions of graphs

An F-decomposition of a graph G is a partition of E(G) into copies of F. Determining whether a graph has an F-decomposition is NP-complete, 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 Nash-Williams' 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 triangle-decomposition. I'll also mention an application to completion of partial mutually orthogonal latin squares.
30/10/2015 4:00 PM

M103 (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).

http://arxiv.org/abs/1506.02697
06/11/2015 4:00 PM

M103

Shoham 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 PM

M103

Luka 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 PM

M103

David 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 PM

M203 (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 AM

M103

Susama 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 PM

M103

Mark 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 PM

M103

Mark 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 PM

M103

Arè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 PM

M103

Ben 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 PM

M103 (Mathematical Sciences)

Jan van den Heuvel (LSE)

Generalised Colouring Numbers of Graphs

The well-known 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
tree-depth and tree-width).
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 minor-closed graphs).

Joint work with Patrice Ossona de Mendez, Daniel Quiroz, Roman
Rabinovich, and Sebastian Siebertz.
26/02/2016 4:00 PM

M103 (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 PM

M103

Gary 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 PM

M103

Roger 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 six-vertex 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 six-vertex 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 PM

M103 (Mathematical Sciences)

Sean Eberhard (Oxford)

Product-free subsets of the alternating group

There is an obvious product-free subset of the symmetric group of density 1/2, but what about the alternating group? An argument of Gowers shows that a product-free 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 Brascamp--Lieb-type inequality for the symmetric group due to Carlen, Lieb, and Loss.
01/04/2016 4:00 PM

M103 (Mathematcal Sciences)

Hakan Guler (QMUL)

Rigidity of Body-Bar Frameworks

Informally, a body-bar framework consists of some rigid bodies and some bars each connecting two different rigid bodies. We can use multigraphs to illustrate body-bar 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 body-bar framework is rigid if and only if the underlying multigraph contains the union of six edge-disjoint 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 non-generic
body-bar frameworks that have the same characterisation as the generic ones.
29/04/2016 4:15 PM

M103

Paul 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 PM

M203

Georg 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 PM

M203

Alina 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 PM

M203

Heng 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 Swendsen-Wang 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 PM

M203

Bhargav 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 PM

M203

Eoin 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 r-regular n-vertex 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^{(1-o(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 PM

M203

Eoin 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 r-regular n-vertex 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^{(1-o(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 PM

M203

Jason Long (Cambridge)

Increasing Sequences of Integer Triples

We will consider a deceptively simple question formulated by Po-Shen 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 PM

M203

Enzo Nicosia (QMUL)

Random Functional Geometric Graphs: Elementary properties and open problems

This is a work-in-progress 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 PM

M203

Tony Nixon (Lancaster)

Global rigidity of generic frameworks on surfaces

A d-dimensional bar-and-joint framework is said to be globally rigid if every d-dimensional 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 3-dimensions 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 PM

M203

Luka Milicevic (Cambridge)

Decomposing Complete Hypergraphs

AttachmentSizeAbstract [PDF 80KB]80.06 KB
09/12/2016 12:30 PM

M203

Andrew 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 PM

M203

David 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 edge-isoperimetric inequality
of Harper, Bernstein, Lindsay and Hart specifies, for each integer k, the smallest
possible size g_n(k) of the edge-boundary 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' edge-boundary; 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 edge-boundary 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 PM

M203

Arran 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 $(k-1)$--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 PM

M203

Will Perkins (Birmingham)

An occupancy approach to bounding graph polynomials
03/02/2017 4:00 PM

M203

Mark Jerrum (QMUL)

Counting list H-colourings in hereditary graph classes

Suppose H is a fixed graph. H-colourings 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 H-colourings,
and demonstrated a dichotomy, in terms of the graph H, between polynomial time
and #P-complete.

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_ H-colourings. In this talk, I’ll present a classification
(in fact a trichotomy) for the problem of approximately counting list H-colourings 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 PM

M203

Jack 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 PM

Bancroft Road 3.01

Leo Liberti (Paris)

New formulation-based 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 diagonally-dominant inner approximation of Ahmadi and Hall's, a randomized-type 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 vice-president 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 part-time professor at Ecole Polytechnique. His main research interests are mixed-integer nonlinear programming and distance geometry.
24/02/2017 4:00 PM

Queen's building W316

Queen's building W316

Record breaking Condorcet domains

The theory of rankings and voting is riddled with curious “paradoxes” related to non-transitivity. I will introduce a few new results on non-transitive 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 3-element 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 mid-1980s. 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 Akello-Egwel, Leedham-green, 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+-year-old records. I will conclude with a list of open questions for further research.
03/03/2017 4:00 PM

Queen's building W316

Anthony 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 non-empty intersection) and the non-union property (i.e the union of any
two subsets is not equal to {1,2,...,n}) contains at most 2^(n-2) 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 PM

Queen's building W316

Rhiannon 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 widely-used 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 PM

Queen's building W316

Alan 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 PM

Queen's building W316

Farbod 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 PM

Queen's building W316

Tony Guttmann, Melbourne

Pattern-avoiding 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 Elvey-Price).
29/09/2017 4:00 PM

W316, Queen's Building

Eoin Long (University of Oxford)

Forbidden vector-valued 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 Frankl-Rödl forbidden intersection theorem in which set intersections are vector-valued. 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, VC-dimension, Dependent Random Choice and a new correlation inequality for product measures. Joint work with Peter Keevash.
06/10/2017 4:00 PM

W316, Queen's Building

Justin Ward (QMUL)

Improved approximation for K-means in arbitrary dimension

In the general 'K-means 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.36-approximation for this problem, as well as an improved 2.64 approximation for the Euclidean k-median 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 Norouzi-Fard, and Ola Svensson (to appear in FOCS '17).
13/10/2017 4:30 PM

W316, Queen's Building

Imre Leader (University of Cambridge)

Decomposing the complete hypergraph

The Graham-Pollak theorem asserts that, to decompose the complete graph on n vertices into complete bipartite subgraphs, we need at least n-1. What happens for hypergraphs: how many complete r-partite r-graphs are needed to decompose the complete r-graph? (Joint work with Luka Milicevic and Ta Sheng Tan.)
20/10/2017 4:00 PM

W316, Queen's Building

Vytautas Gruslys (University of Cambridge)

Path partitions of regular graphs

We consider the problem of covering a regular graph by a small number of vertex-disjoint paths. Magnan and Martin conjectured that every k-regular 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 PM

Queens Building, W316

David Conlon (University of Oxford)

How to build a hypergraph expander

We present a simple mechanism, which can be randomised, for constructing sparse 3-uniform hypergraphs with strong expansion properties. These hypergraphs are constructed using Cayley graphs over elementary abelian 2-groups 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 PM

W316, Queeen's Building

Allan Lo (University of Birmingham)

Hypergraph F-designs

We show that given any $r$-uniform hypergraph $F$, the trivially necessary divisibility conditions are sufficient to guarantee an edge-decomposition of any sufficiently large complete $r$-uniform hypergraph into edge-disjoint 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 PM

W316, Queens Building

Felix Fischer (QMUL)

TBA

TBA
01/12/2017 4:00 PM

W316, Queen's Building

Natalie Behague (QMUL)

TBA

TBA
08/12/2017 4:00 PM

W316, Queen's Building

Amanda Cameron (QMUL)

TBA

TBA
15/01/2010 4:30 PM

M103

Victor Falgas-Rouvry

Union-closed families of small weight
16/04/2010 5:30 PM

M103

Manfred Droste (Leipzig)

Random constructions of countable abelian p-groups

By Ulm's theorem, countable reduced abelian p-groups 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 p-group 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 p-groups which are essential for our construction.

Joint work with Ruediger Goebel (Essen).
04/06/2010 5:30 PM

M103

Robert Bailey (Regina)

Generalised covering designs and clique-coverings

Covering designs are a generalisation of t-designs, where the requirement that any t-subset 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 t-designs", 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 PM

M103

Simeon 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 sucn a set is the following.

Example. (Normal rational curve) The set

S = {(1,t,t²,...,t^k-1 | 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 non-zero 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₉⁵, due to Glynn, and an example in F_2^h⁴ 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 non-prime 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 PM

M103

Andy Drizen

Generating uniformly distributed random 2-designs 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 lambda-factorisations of the complete graph at random.
04/03/2011 5:00 PM

M103

Heidi Gebauer (ETH)

Game theoretic Ramsey numbers

The Ramsey Number, R(k), is defined as the minimum N such that every 2-coloring of the edges of K_N (the complete graph on N vertices) yields a monochromatic k-clique. 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 PM

M103

Sasha Gnedin

Block 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 coinvariant 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 PM

M103

Celia Glass (City) Peter Cameron

Acyclic 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 PM

M103

Benny 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 PM

M103

Peter Cameron

Counting 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 inclusion-exclusion 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 PM

M103

Laszlo Vegh (LSE)

Approximating minimum cost k-node-connected 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 k-node-connected. We present a 6-approximation algorithm for this NP-complete problem, assuming that the number of nodes is at least k³(k−1)+k. This gives the first constant factor approximation for the problem.

For edge-connectivity 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 node-connectivity on arbitrary input graphs, we show that it does give a 2-approximation for a restricted class of instances. We apply a combinatorial preprocessing, based on the Frank–Tardos algorithm for k-outconnectivity, to transform any input into such an instance. This is a joint work with Joseph Cheriyan.
23/11/2012 4:30 PM

M103

Fatima 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 n-cycle 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 PM

M103

Peter Cameron

Synchronizing non-uniform 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 non-permutation f: I will say that G synchronizes f if ⟨G,f⟩ is synchronizing.

It is known that a permutation group which synchronizes every non-permutation 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 non-uniform 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 PM

M103

Andrew Treglown

Yet another talk on perfect matchings in hypergraphs

Last term Peter Keevash and Fiachra Knox both gave talks on perfect matchings in hypergraphs. In this self-contained 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 r-degree condition that ensures a perfect matching in a k-uniform 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 PM

M103

Jan Volec

A problem of Erdos and Sos on 3-graphs

We show that for every ε>0 there exist δ>0$ and n₀∈N such that every 3-uniform hypergraph on n≥n₀ vertices with the property that every k-vertex subset, where k≥δn, induces at least (1/4+ε){k choose 3} edges, contains K₄⁻ as a subgraph, where K₄⁻ is the 3-uniform 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 PM

M103

Jeroen 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 PM

M103

Peter Cameron

Combinatorial Yang-Baxter

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 set-theoretic) solution of the Yang–Baxter equation is a set X (usually finite) and a function r:X²→X² satisfying the braiding condition on X³. 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 Gateva-Ivanova, but I will be concentrating on the parts where I had some input.
21/11/2014 4:30 PM

M103

Oleg 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 non-zero 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 long-standing 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 PM

M203

Yufei 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 Chatterjee--Varadhan (dense setting) and Chatterjee--Dembo (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 PM

M103 (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 k-colouring 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 k-colour 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 k-colour Ramsey number of C_{r} is at least (r-1)(2+c)^{k-1}.

This is joint work with Robert Johnson.
05/02/2016 4:00 PM

M103 (Mathematical Sciences)

Ginestra Bianconi (QMUL)

Equilibrium and non-equilibrium 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 non-equilibrium evolution of growing simplicial complexes of dimension d. We show that in d=2 CQNM are homogeneous networks while for d >2 they are scale-free i.e. they are characterized by large inhomogeneities of degrees like most complex networks. From the self-organized evolution of CQNM quantum statistics emerge spontaneously. Here we define the generalized degrees associated with the faces of the d-dimensional CQNMs, and we show that the statistics of these generalized degrees can either follow Fermi-Dirac, Boltzmann or Bose-Einstein 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 PM

W316, Queen's Building

Hakan Guler (QMUL)

Rigidity of linearly constrained frameworks

A linearly constrained framework in d-dimensions is a d-dimensional bar-and-joint 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 PM

W316, Queens Building

John Haslegrave (University of Warwick)

Hamilton spheres in 3-uniform hypergraphs

Dirac's theorem states that any n-vertex 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 k-uniform hypergraph, where in this case "minimum degree" is interpreted as the minimum codegree, i.e. the minimum over all (k-1)-sets of the number of ways to extend that set to an edge. The notion of a tight cycle can be generalised to an l-cycle for any l < k, and corresponding results for l-cycles 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, l-cycles are essentially one-dimensional structures. A natural topological generalisation of Hamilton cycles in graphs to higher-dimensional structures is to ask for a spanning triangulation of a sphere in a 3-uniform hypergraph. We give an asymptotic Dirac-type result for this problem. Joint work with Agelos Georgakopoulos, Richard Montgomery and Bhargav Narayanan.
07/12/2017 4:00 PM

W316, Queens Building

Felix Fischer

Truthful Outcomes from Non-Truthful Position Auctions

The area of mechanism design in economics is concerned with algorithms that produce good outcomes given inputs from self-interested individuals. One of the stars of mechanism design theory is the Vickrey-Clarke-Groves (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 non-truthful. 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 non-truthful 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 non-truthful 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 PM

316, Queen's Building

Natalie 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 F-saturated graph on n vertices can have. This forms an interesting counterpoint to the Turan number; the saturation number is in many ways less well-behaved. 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 PM

W316, Queen's Building

Amanda Cameron (Max Planck Institute, Leipzig)

An Ehrhart theory generalisation of the Tutte polynomial

The Tutte polynomial is one of the most important and well-known 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, deletion-contraction 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 PM

Queens' Building, Room W316

Peter 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(n-1)$, $n-3$ 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 PM

Queens' Building, Room W316

Simon 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 PM

Queens' Building, Room W316

Natasha 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 PM

Queens' Building Room W316

Robert 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 1-dimensional 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 PM

Queens' Building, Room W316

Ivan 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 PM

Queens' Building, Room W316

László A. Végh (LSE)

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

We give a constant-factor 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 constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem. This is joint work with Ola Svensson and Jakub Tarnawski.
23/02/2018 4:00 PM

Queens' Building, Room W316

Taoyang Wu (University of East Anglia)

Distances on Evolutionary (Phylogenetic) Trees: Maximum Parsimony and Tree-width

In evolutionary biology, distances are often used to measure the incongruence between a pair of phylogenetic trees (i.e., leaf-labelled 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 PM

Queens' Building, Room W316

Nicholas Day (Umeå University)

Maker-Breaker percolation games

The (p,q)-Maker-Breaker-percolation game is played by two players, Maker and Breaker, who take turns claiming edges from the two-dimensional 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 Maker-Breaker-percolation games and give a number of results for when Maker or Breaker can win. To do this we will look at and discuss certain Maker-Breaker 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 Maker-Breaker crossing games, show how they relate back to the original percolation games, and discuss how they are related to the combinatorial games of Hex, Bridg-it and the Shannon switching game.

This talk is based on joint work with Victor Falgas-Ravry.
09/03/2018 4:00 PM

Queens' Building, Room W316

Imre Bárány (UCL)

Theorems of Caratheodory and Tverberg without dimension

Caratheodory'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 PM

Queens' Building, Room E303

Standa Ž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 general-valued CSPs parametrised by the source structures. Based on joint work with Clement Carbonnel and Miguel Romero.
18/05/2018 4:00 PM

Queens' Building Room W316

Noam Lifshitz (Bar Ilan University)

The Junta Method for Hypergraphs

Numerous problems in extremal hypergraph theory ask to determine the maximal size of a k-uniform hypergraph on n vertices that does not contain an 'enlarged' copy H^+ of a fixed hypergraph H. These include well-known problems such as the Erdős-Sós 'forbidding one intersection' problem and the Frankl-Fü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 PM

Queens' Building Room W316

Nick 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 PM

Queens' Building, Room W316

Istvá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 PM

Queens' Building, Room W316

Rhys 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 edge-regular graphs. The examples of edge-regular graphs with regular cliques that Neumaier knew of were all strongly regular graphs, so he asked if there exist edge-regular, non-strongly regular graphs containing regular cliques. With this as motivation, we define a Neumaier graph as an edge-regular, non-strongly 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 edge-regular or strongly regular graphs is assumed.
01/06/2018 4:00 PM

Queens' Building, Room W316

Matt Fayers (QMUL)

An interesting family of posets