# Combinatorics 2014-15

### Agelos Georgakopoulos

Oleg Pikhurko

*The seminars are held on Friday at 2pm-3pm*

### Term 1 2014/15 - Room MS.04

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.

and Multitolerance Graphs

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)**

**S**trong 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.

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.