Date	Name	Title
3 Oct	David Bevan (Open University)	Tours on graphs and grid classes of permutations
10 Oct	Victor Zamaraev (Warwick)	Boundary properties of factorial classes of graphs
17 Oct	Felix Lazebnik (Delaware)	On Graphs Defined by Some Systems of Equations
24 Oct	Johannes Carmesin (Hamburg)	Edge-disjoint double rays in infinite graphs
31 Oct	Louigi Addario-Berry (McGill)	Growing random trees, maps, and squarings
7 Nov	Fiona Skerman (Oxford)	Modularity of networks
14 Nov	Konstantinos Tyros (Warwick)	Density Ramsey type results for words and a concentration inequality.
21 Nov	Felix Joos (Ulm)	Induced Matchings in Graphs
28 Nov	Robert Brignall (Open University)	From permutations to graphs: well-quasi-ordering and infinite antichains
5 Dec	Archontia Giannopoulou (Durham)	New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs

Term 2 2014/15 - Room MS.04

Date	Name	Title
9 Jan	David Ellis (Queen Mary)	The structure of graphs which are locally indistinguishable from a lattice
16 Jan	Tomasz Tkocz (Warwick)	Expanders and local vs global invertibility of certain operators
23 Jan	Jeroen Schillewaert (Imperial)	Small maximal independent sets
30 Jan	András Máthé (Warwick)	Solving Tarski's circle-squaring problem with measurable sets
6 Feb	Bruno Federici (Warwick)	Hyperbolicity, non-amenability and bounded codegree for planar graphs
13 Feb	Omer Angel (UBC)	Monotone subsequences of random walks
20 Feb	Anita Liebenau (Warwick)	The oriented cycle game
27 Feb	Katherine Staden (Warwick)	On degree sequences forcing the square of a Hamilton cycle
6 Mar	Jason Miller (MIT)	Liouville quantum gravity as a mating of trees
13 Mar	Mykhaylo Tyomkyn (Birmingham)	Strong Turan stability

Term 3 2014/15 - Room MS.04

Date	Name	Title
8 May	Tamas Hubai (Budapest)	Positive graphs
15 May	Frank Vallentin (Cologne)	New upper bounds for the density of translative packings of superspheres
22 May	Peter Morters (Bath) (Part of conference)	Robustness of spatial preferential attachment networks
29 May	Joonkyung Lee (Oxford)	Some Advances on Sidorenko's Conjecture
5 Jun	Endre Csóka	Limits of some combinatorial problems
12 Jun	Richard Mycroft (Birmingham)	User-friendly hypergraph regularity

---

3 Oct, David Bevan (Open University)
Tours on graphs and grid classes of permutations

A tour on a graph G is a walk that ends at the vertex from which it starts. We call a tour balanced if, for each edge e of G, the number of times e is traversed in one direction is the same as the number of times it is traversed in the other direction. We will look at an outline of a proof that the family of balanced tours on a connected graph G grows at the same rate as the family of all tours on G of even length.

A grid class of permutations is defined by a matrix which specifies the acceptable shape for plots of permutations in the class, in terms of the possible locations of increasing and decreasing subsequences. Building on the result concerning balanced tours, we will explore a proof that the growth rate of a grid class is given by the square of the spectral radius of an associated graph known as its row-column graph. This beautiful discovery is the first general theorem giving exact growth rates for a whole family of permutation classes, and enables us to characterise all slowly growing grid classes.

If there is time, we will also briefly consider limits in grid classes.

---

10 Oct, Victor Zamaraev (Warwick)
Boundary properties of factorial classes of graphs

For a class of graphs X, let X_n be the number of graphs with vertex set {1,...,n} in the class X, also known as the speed of X. It is known that in the family of hereditary classes (i.e. those that are closed under taking induced subgraphs) the speeds constitute discrete layers and the first four lower layers are constant, polynomial, exponential, and factorial. For each of these four layers a complete list of minimal classes is available, and this information allows to provide a global structural characterization for the first three of them. The minimal layer for which no such characterization is known is the factorial one. A possible approach to obtaining such a characterization could be through identifying all minimal superfactorial classes. However, no such class is known and possibly no such class exists. To overcome this difficulty, we employ the notion of boundary classes that has been recently introduced to study algorithmic graph problems and reveal the first few boundary classes for the factorial layer. Joint work with Vadim Lozin.

---

17 Oct, Felix Lazebnik (Delaware)
On Graphs Defined by Some Systems of Equations

In this talk I will present a simple method for constructing infinite
families of graphs defined by a class of systems of equations over
commutative rings. The graphs in all such families possess some general
properties including regularity or bi-regularity, existence of special
vertex colorings, and existence of covering maps between every two members
of the same family (hence, embedded spectra). Another general property is
that nearly every graph constructed in this manner
edge-decomposes either the complete, or complete bipartite, graph which it
spans.

In many instances, specializations of these constructions have proved
useful in various graph theory problems, but especially in many extremal
problems which deal with cycles in graphs. I will explain motivations for
these constructions, survey both old and new results, and state open questions.

---

24 Oct, Johannes Carmesin (Hamburg)
Edge-disjoint double rays in infinite graphs

Halin’s theorem says that if, in an infinite graph, for each natural number k there are k vertex-disjoint rays, then there are infinitely many vertex- disjoint rays. There are four natural variants of this theorem obtained from the above by replacing ‘ray’ by ‘double ray’ or ‘vertex-disjoint’ by ‘edge- disjoint’. Three of these had been known for a long time, and the fourth was conjectured to be true by Andreae in 1981. In this talk, I talk about the proof of the forth variant. The talk includes many figures and will be self-contained. In particular, no special knowledge about infinite graphs is required. This is joint work with Nathan Bowler and Julian Pott.

---

31 Oct, Louigi Addario-Berry (McGill)

Growing random trees, maps, and squarings

We use a growth procedure for binary trees due to Luczak and Winkler, a
bijection between binary trees and irreducible quadrangulations of the
hexagon due to Fusy, Poulalhon and Schaeffer, and the classical angular
mapping between quadrangulations and maps, to define a growth procedure for
maps. The growth procedure is local, in that every map is obtained from its
predecessor by an operation that only modifies vertices lying on a common
face with some fixed vertex. The sequence of maps has an almost sure limit
G; we show that G is the distributional local limit of large, uniformly
random 3-connected graphs.

A classical result of Brooks, Smith, Stone and Tutte associates squarings of
rectangles to edge-rooted planar graphs. Our map growth procedure induces
a growing sequence of squarings, which we show has an almost sure limit: an
infinite squaring of a finite rectangle, which almost surely has a unique
point of accumulation. We know almost nothing about the limit, but it
should be in some way related to "Liouville quantum gravity".

Parts joint with Nicholas Leavitt.

---

Modularity is a quality function on partitions of a network which aims
to identify highly clustered components. Given a graph G, the
modularity of a partition of the vertex set measures the extent to
which edge density is higher within parts than between parts; and the
modularity q(G) of G is the maximum modularity of a partition of V(G).

Knowledge of the maximum modularity of the corresponding random graph
is important to determine the statistical significance of a partition
in a real network. We provide bounds for the modularity of random
regular graphs.

Modularity is related to the Hamiltonian of the Potts model from
statistical physics. Hence we are interested in the modularity of
lattices. Guimerà et. al. show that lattices have near maximal
modularity. We extend this to all subgraphs of lattices and graphs
which embed with low distortion. We also show that small tree-width
and maximal degree guarantee high modularity.

This is join work with Prof. Colin McDiarmid.

---

Density Ramsey type results for words and a concentration inequality.

In this talk we will present the density versions of the Hales–Jewett Theorem and the Carlson–Simpson Theorem. The Hales–Jewett Theorem is one of the most representing results in Ramsey theory. Its density version was first proved by H. Furstenberg and Y. Katznelson in 1991 using Ergodic Theory. However, since then, combinatorial proofs have been discovered. The Density Hales–Jewett Theorem has as a consequence Szem ́eredi’s Theorem on arithmetic progressions as well as its multidimensional version. The Density Carlson–Simpson Theorem is an extension of the Density Hales–Jewett Theorem and concerns the space of the left variable words. The proofs of the above results required a new regularity method that led to a concentration inequality for product spaces.

---

In contrast to matchings in graphs, one might say that induced
matchings do not behave nicely (structurally and algorithmically). I survey
some recent results on induced matchings and give some explanations why
induced matchings are more complicated than matchings. Most of the results
are stimulated by a conjecture of Erdös and Nesetril saying that the edge
set of every graph with maximum degree D can be partitioned into 5/4*D^2
induced matchings. This conjecture is still widely open.

---

The celebrated Graph Minor Theorem tells us that every infinite
collection of graphs contains one graph which is a minor of another, so graphs
are "well-quasi-ordered with respect to the minor ordering". If we replace
"minor" with "induced subgraph" this statement is not always true: for example,
the set of all cycles forms an infinite antichain. However, by restricting to
some smaller class of graphs, we can recover this property, which has important
consequences in the study of computational complexity.

In this talk, I will show how recent structural developments made in the study
of permutation patterns can be used to establish the well-quasi-orderability (or
not) of some graph classes, for example of permutation graphs defined by a
forbidding a path and a clique.

---

Tolerance graphs model interval relations in such a way that intervals
can tolerate a certain amount of overlap without being in conflict. In one of the
most natural generalizations of tolerance graphs, namely multitolerance graphs,
two tolerances are allowed for each interval – one from the left and one from the
right side. In this talk we introduce two new geometric representations for
tolerance and multitolerance graphs, given by points and line segments in the plane.
Using them, we prove that the dominating set problem can be solved in polynomial
time on tolerance graphs and that it is APX-hard on multitolerance graphs. This
problem is the first one that has been discovered with a different complexity status
in these two graph classes.

---

9 Jan, David Ellis (Queen Mary)
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 $\mathbb{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 $\mathbb{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. We will also discuss some results and open problems on
the properties of a random n-vertex graph which is $r$-locally-$F$. This
is all joint work with Itai Benjamini (Weizmann Institute of Science).

---

16 Jan, Tomasz Tkocz (Warwick)
Expanders and local vs global invertibility of certain operators

I shall present how expander graphs help solve some problems in geometric functional analysis.

---

23 Jan, Jeroen Schillewaert (Imperial)
Small maximal independent sets

We study random constructions in incidence structures using a general theorem on set systems. Our main result applies to a wide variety of well-studied problems in finite geometry to give almost tight bounds on the
sizes of various substructures. This is joint work with Michael Tait and Jacques Verstraete.

---

30 Jan, András Máthé (Warwick)
Solving Tarski's circle-squaring problem with measurable sets

"Tarski's circle-squaring problem is the challenge, posed by Alfred Tarski in 1925, to take a disc in the plane, cut it into finitely many pieces, and reassemble the pieces so as to get a square of equal area. This was proven to be possible by Miklos Laczkovich in 1990; the decomposition makes heavy use of the axiom of choice and is therefore non-constructive" - as we can read on Wikipedia.

Laczkovich's solution to the circle-squaring is by a reduction to a combinatorial problem about the existence of perfect matchings in certain infinite bipartite graphs. The proof uses ideas from number theory, in particular, the theory of uniform distribution of sequences.

I will explain Laczkovich's proof and explain how one can modify the combinatorial argument to obtain the perfect matchings algorithmically yielding a measurable decomposition of the disc to the square.

Joint work with Lukasz Grabowski and Oleg Pikhurko.

---

6 Feb, Bruno Federici (Warwick)
Hyperbolicity, non-amenability and bounded codegree for planar graphs

Hyperbolicity and (non-)amenability, as well as their relationship, have been extensively studied for groups and manifolds, while only recently for general graphs too. In this talk we discuss the case of planar graphs of bounded maximum degree, proving that any two of the following properties imply the third: hyperbolicity, non-amenability and bounded maximum length of faces.

---

13 Feb, Omer Angel (UBC)
Monotone subsequences of random walks

The celebrated Erdos-Szekeres Theorem states that any sequence of length
n contains a monotone subsequence of length $\sqrt{n}$. We consider the
situation when the sequence is an n step random walk, and show that this
bound is almost sharp: with high probability the maximal sequence has
length at most $n^{1/2+epsilon}$. Joint with Yuval Peres and Richard
Balka; no probability background is assumed.

---

20 Feb, Anita Liebenau (Warwick)
The oriented cycle game

We will look at the following combinatorial game: Two players, CycleMaker and CycleBreaker, alternately orient the edges of the complete graph on n vertices. CycleMaker wins if the final tournament contains a directed cycle. Otherwise, CycleBreaker wins. For n large enough, this game is a simple win for CycleMaker. Hence, we equip CycleBreaker with more power: she is allowed to direct more edges per round. We are interested in the largest number of edges that CycleBreaker is allowed to direct in each round such that CycleMaker still has a winning strategy. This threshold is at most n-3, and it was conjectured to be tight by Bollobás and Szabó. We show that the threshold is at most 19n/20. Joint work with Dennis Clemens.

---

Date: TBA, Jacob Cooper (Warwick)
Finitely forcible graphons with no small regularity partitions

Graphons are analytic objects that represent the behaviour of convergent sequences of dense graphs. Problems from extremal combinatorics and theoretical computer science have led to a study of graphons determined by finitely many subgraph densities, the so-called finitely forcible graphons. A conjecture of Lovasz and Szegedy on the space of typical vertices of finitely forcible graphons implied that the number of parts in weak eps-regular partitions of finitely forcible graphons is always polynomial in 1/eps. The conjecture has recently been disproved by Glebov, Klimosova and Kral but the constructed example has a number of parts growing only subexponentially in 1/eps. We construct an example of a finitely forcible graphon such that the number of parts in its weak eps-regular partitions is exponential in 1/eps^1.999, which almost matches the existing general upper bound. Joint work with Tomas Kaiser, Dan Kral and Jonathan Noel.

---

27 Feb, Katherine Staden (Warwick)
On degree sequences forcing the square of a Hamilton cycle

A famous conjecture of P\'osa from 1962 asserts that every graph
on $n$ vertices and with minimum degree at least $2n/3$ contains the
square of a Hamilton cycle. The conjecture was proven for large graphs in
1996 by Koml\'os, S\'ark\"ozy and Szemer\'edi. I will discuss a degree
sequence version of P\'osa's conjecture: Given any $\eta >0$, every graph
$G$ of sufficiently large order $n$ contains the square of a Hamilton
cycle if its degree sequence $d_1 \leq \dots \leq d_n$ satisfies $d_i \geq
(1/3+\eta)n+i$ for all $i \leq n/3$. The degree sequence condition here is
asymptotically best possible. This is joint work with Andrew Treglown
(Birmingham).

---

6 Mar, Jason Miller (MIT)
Liouville quantum gravity as a mating of trees

There is a simple way to “glue together” a coupled pair of continuum random trees to produce a topological sphere. The sphere comes equipped with a measure and a space-filling curve (which describes the “interface” between the trees). We present an explicit and canonical way to embed the sphere into the Riemann sphere. In this embedding, the measure is Liouville quantum gravity with parameter gamma in (0,2), and the curve is space-filling version of SLE with kappa=16/gamma^2. We will explain how these constructions are related to understanding the scaling limits of random planar maps. Based on joint work with Bertrand Duplantier and Scott Sheffield.

---

13 Mar, Mykhaylo Tyomkyn (Birmingham)
Strong Turan stability

We study the behaviour of $K_{r+1}$-free graphs~$G$ of almost extremal size, that is, typically, $e(G)=ex(n,K_{r+1})-O(n)$. We show that such graphs must have a large amount of symmetry. In particular, if $G$ is saturated, then all but very few of its vertices must have twins. As a corollary, we obtain a new proof of a theorem of Simonovits on the structure of extremal graphs with $\omega(G)\leq r$ and $\chi(G)\geq k$ for fixed $k \geq r \geq 2$.

Joint work with Andrew Uzzell.

---

8 May, Tamas Hubai (Budapest)
Positive graphs

We call a graph positive if it has a nonnegative homomorphism number into
any target graph with real edge weights. The Positive Graphs Conjecture
offers a structural characterization: these are exactly the graphs that can
be obtained by gluing together two copies of the same graph along an
independent set of vertices. In this talk I will discuss our recent results
on the Positive Graphs Conjecture. (Joint work with Dávid Kunszenti-Kovács
and László Lovász.)

---

15 May, Frank Vallentin (Cologne)
New upper bounds for the density of translative packings of superspheres

In this talk I will present new upper bounds for the maximum density of translative packings of superspheres in three dimensions (unit balls for the $l^p$-norm). This will give some strong indications that the lattice packings experimentally found in 2009 by Jiao, Stillinger, and Torquato are indeed optimal among all translative packings. We apply the linear programming bound of Cohn and Elkies which originally was designed for the classical problem of packings of round spheres. The proof of our new upper bounds is computational and rigorous. Our main technical contribution is the use of invariant theory of pseudo-reflection groups in polynomial optimization.

This is joint work with Maria Dostert, Cristob\'al Guzm\'an, and Fernando M\'ario de Oliveira Filho.

---

22 May, Peter Morters (Bath)

Robustness of spatial preferential attachment networks

A growing family of random graphs is called robust if it retains a giant component after percolation with arbitrarily small positive retention probability. We study robustness for graphs, in which new vertices are given a spatial position on the unit circle and are connected to existing vertices with a probability favouring short spatial distances and high degrees. In this model of a scale-free network with clustering we can independently tune the power law exponent τ of the degree distribution and the rate −δ at which the connection probability decreases with the distance of two vertices. We show that the network is robust if τ < 2 + 1/δ , but fails to be robust if τ > 2 + 1/(δ−1) . This seems to be the first instance of a scale-free network where robustness depends not only on its degree distribution but also on its clustering features. This is joint work with Emmanuel Jacob (ENS Lyon).

---

29 May, Joonkyung Lee (Oxford)

Some Advances on Sidorenko's Conjecture

A bipartite graph $H$ is said to have Sidorenko's property if the
probability that the uniform random mapping from $V(H)$ to the vertex set
of any graph $G$ is a homomorphism is at least the product of the
probabilities that each edge of $H$ is mapped into an edge in $G$. In this
talk, I will give an overview of the known results and new approaches to
attack Sidorenko’s conjecture, especially an embedding algorithm to prove
that bipartite graphs admitting a specific form of tree decomposition have
Sidorenko's property. This is joint work with David Conlon, Jeong Han Kim,
and Choongbum Lee.

---

5 Jun, Endre Csóka
Limits of some combinatorial problems

We show some new examples how limit theory of combinatorial
structures can help understanding other combinatorial problems. First,
we generalize the Manickam–Miklós–Singhi Conjecture, using limit
theory. Then we introduce two limit problems of Alpern’s Caching Game,
which are good approximations of the finite game when some parameters
tend to infinity. With the use of these limit problems, we show a
surprising result which disproves some conjectures about the finite
problem.

---

12 Jun Richard Mycroft (Birmingham)
User-friendly hypergraph regularity

The celebrated Szemerédi regularity lemma has led to a great many advances in extremal graph theory over recent decades. More recently, hypergraph analogues of the regularity lemma have yielded similar developments in the theory of hypergraphs. However, these so-called 'strong hypergraph regularity lemmas' have the disadvantage of being very technical, and proofs which make use of them tend to be very long. In this talk I will discuss a 'regular slice lemma', which I believe provides a more user-friendly way of handling hypergraph regularity. I will argue that by using this lemma, one can significantly shorten arguments in extremal hypergraph theory, but also that these arguments are closer in flavour to arguments making use of the graph regularity lemma. This is joint work with Peter Allen, Julia Böttcher and Oliver Cooley.