Term 1 2013/14 - Room MS.04

Date	Name	Title
Oct'4, 2013	Shagnik Das (Zurich)	The minimum number of disjoint pairs in set systems
Oct'11, 2013	Guus Regts (CWI, Amsterdam)	Compact orbit spaces, graph limits and limits of edge-coloring models
Oct'18, 2013	Oliver Roche-Newton (Reading)	Variations on the sum-product problem
Oct'25, 2013	Jan Volec (Warwick)	Compactness and finitely forcible graphons
Nov'1, 2013	Frantisek Kardos (Bordeaux)	One of Barnette's conjectures confirmed: (not only) fullerene graphs are hamiltonian
Nov'8, 2013	Marthe Bonamy (Montpellier)	The Erdos-Hajnal Conjecture
Nov'15, 2013	Ross Kang (Utrecht)	Bounded spectrum list colouring
Nov'22, 2013	Evan DeCorte (TU Delft)	Low-dimensional spherical sets avoiding orthogonal pairs of points
Nov'29, 2013	Yi Zhao (Atlanta)	Minimum degree thresholds for Hamilton cycles in k-uniform hypergraphs
Dec'6, 2013	Tereza Klimošová (Warwick)	Infinite dimensional finitely forcible graphon

---

Term 2 2013/14 - Room MS.04

Date	Name	Title
Jan'10, 2014 (in MS.03)	Vitaliy Kurlin (Durham)	Book embeddings of Reeb graphs
Jan'17, 2014	Colin Cooper (King's College London)	Random walks and the component structure of the vacant set Slides
Jan'24, 2014	Richard Sharp (Warwick)	A Weil-Petersson metric for metric graphs
Feb'7, 2014	Danny Hefetz (Birmigham)	On biased Chooser-Picker and Picker-Chooser games
Feb'14, 2014	Jan Foniok (Warwick)	Adjoint functors in graph theory
Feb'21, 2014 B1.01.	Franz Kiraly (UCL)	Algebraic Matroids with Graph Symmetry
Feb'28, 2014	Humberto Naves (Zurich)	Generating random graphs in biased Maker-Breaker games
Mar'7, 2014	Matthias Hamann (Hamburg)	Canonical tree structure of graphs
Mar'14, 2014	Andrew Thomason (Cambridge)	Independent sets in hypergraphs

---

Term 3 2013/14 - Room MS.04

Date	Name	Title
May 2, 2014	Johannes Carmesin (Hamburg)	An introduction to infinite matroids
May 9, 2014	David Gamarnik (MIT)	Convergent sequences of sparse graphs: A large deviations approach
May 16, 2014	Anita Liebenau (Warwick)	What is Ramsey-equivalent to the clique?
May 23, 2014	Natan Rubin (Paris)	How many times a Delaunay triangulation can change?
May 30 2014	Ofer Zeitouni	The Barvinok-Godsil-Gutman permanent estimator and singular values of Gaussian matrices
Jun'6, 2014	No seminar	Coincides with CMI Worskhop "Extremal and Probabilistic Combinatorics", Oxford
Jun'13, 2014	Andrzej Grzesik (Krakow)	Around the Caccetta-Haggkvist Conjecture
Jun'20, 2014	Balazs Udvari (Szeged)	The rectilinear crossing number of K_n
June'27, 2014	Jon Noel (Oxford)	Choosability of Graphs With Bounded Order

---

Abstracts

Oct'4, 2013 Shagnik Das (Zurich)
The minimum number of disjoint pairs in set systems.

Let $\mathcal{F}$ be a family of subsets of $[n]$ such that all sets have size $k$ and every pair of sets intersect. The celebrated theorem of Erd\H{o}s-Ko-Rado from 1961 says that when $n \ge 2k$, any such family has size at most $\binom{n-1}{k-1}$. A natural question to ask is how many disjoint pairs must appear in a set system of larger size. In 1978, Ahlswede and Katona resolved this question for $k = 2$.

In this talk, we shall determine the minimum number of disjoint pairs in small $k$-uniform families, thus confirming a conjecture of Bollob\'as and Leader. Moreover, we obtain similar results for a number of extensions of the Erd\H{o}s-Ko-Rado theorem, determining for example the minimum number of $t$-disjoint pairs that appear in set systems larger than the corresponding extremal bound. This provides a partial solution to the Kleitman-West problem.

Joint work with W. Gan and B. Sudakov

---

Oct'11, 2013 Guus Regts (CWI, Amsterdam)
Compact orbit spaces, graph limits and limits of edge-coloring models

Let $G$ be a group of orthogonal transformations of a Hilbert space $H$. Let $R$ and $W$ be bounded $G$-stable subsets of $H$. Let $\|.\|_R$ be the seminorm on $H$ defined by $\|x\|_R:=\sup_{r\in R}|\langle x,r\rangle|$ for $x\in H$. If $W$ is weakly compact and the orbit space $R^k/G$ is compact for each $k\in\mathbb{N}$, then the orbit space $W/G$ is compact when $W$ is equipped with the norm topology induced by $\|.\|_R$.
In this talk I will discus a few consequences of this result: the compactness of the graphon space and the existence of limits of edge-coloring models.

This is based on joint work with Lex Schrijver

---

Oct'18, 2013 Oliver Roche-Newton (Reading)
Variations on the sum-product problem

The Erdős-Szemerédi sum-product conjecture represents a major open problem in the field of Arithmetic Combinatorics. Roughly speaking, it states that a set of integers must determine either many distinct pairwise sums, or many distinct pairwise products (or both).

An interpretation of the conjecture is that it states that one set of integers cannot be too similar to both an arithmetic and geometric progression. There are many different ways to make this idea more precise, and I will discuss sum-product type results which provide some evidence in support of the original Erdős-Szemerédi conjecture.

---

Oct'25, 2013 Jan Volec (Warwick)
Compactness and finitely forcible graphons

Graphons are limit objects that are associated with convergent sequences of
graphs. Problems from extremal combinatorics led to a study of graphons
determined by finitely many subgraph densities, which are referred to as
finitely forcible graphons. In 2011, Lovasz and Szegedy asked several questions
about the complexity of the topological space of so-called typical vertices of
a finitely forcible graphon can be. In particular, they conjectured that the
space is always compact. We disprove the conjecture by constructing a finitely
forcible graphon such that the associated space of typical vertices is not
compact. In fact, our construction actually provides an example of a finitely
forcible graphon with the space which is even not locally compact. This is a
joint work with Roman Glebov and Dan Kral.

---

Nov'1, 2013 Frantisek Kardos (Bordeaux)
One of Barnette's conjectures confirmed: (not only) fullerene graphs are hamiltonian

Fullerene graphs, i.e., 3-connected planar cubic graphs with pentagonal and hexagonal faces, are conjectured to be Hamiltonian. This is a special case of a conjecture of Barnette, dating back to the 60s, stating that 3-connected planar cubic graphs with faces of size at most 6 are Hamiltonian. We present a computer-assisted proof of the conjecture.

---

Nov'8, 2013 Marthe Bonamy (Montpellier)
The Erdos-Hajnal Conjecture

A random graph on $n$ vertices has a.a.s. no clique or stable set of order significantly greater than $log \ n$ (Erd\H{o}s 1963). Let $\mathcal{C}$ be a non-trivial graph class closed under induced subgraphs. The Erd\H{o}s-Hajnal (E-H for short) conjecture states that any such $\mathcal{C}$ behaves quite differently from random graphs: the graphs in $\mathcal{C}$ have a polynomial-size clique or stable set. The polynomial depends of course on $\mathcal{C}$.

Similarly, a graph $H$ has the E-H property if the E-H conjecture is true for the class of graphs that do not contain $H$ as an induced subgraph. The initial (equivalent) statement of the E-H conjecture was ''every graph has the E-H property''.

So far, only very little is known about the conjecture: We know that all graphs on $\leq 5$ vertices, except for $C_5$ and $P_5$, have the E-H property, and that it suffices to decide whether all prime graphs have the E-H property. In an effort to approach the cases $P_5$ and $C_5$, Bousquet, Lagoutte and Thomass\'e proved that the E-H conjecture is true for the class of graphs without long paths or long anti-paths, and we prove it for the class of graphs without long cycles or long anti-cycles. This is joint work with Nicolas Bousquet and St\'ephan Thomass\'e.

---

Nov'15, 2013 Ross Kang (Utrecht)
Bounded spectrum list colouring

Král' and Sgall introduced a notion of list colouring where the lists
are composed of colours from some predetermined set (in this talk we
call this the "spectrum"), that in particular has bounded size. This
notion was already observed to be closely related to an extremal
parameter for Property B or hypergraph 2-colourability. We can relate
the notion to a possibly new variant of Property B we dub Property K
(K for "Kleur", of course). In doing so, we see for instance that
there is a graph that is k-choosable if the spectrum is constrained to
a set of size 2k-1, but not 2^{\Omega(k)}-choosable in general. We
also consider further aspects of this problem. Joint work with Marthe
Bonamy.

---

Nov'22, 2013 Evan DeCorte (TU Delft)
Low-dimensional spherical sets avoiding orthogonal pairs of points

Let M_n be the maximum surface measure of a subset of the n-dimensional unit sphere not containing a pair of orthogonal vectors. A 1974 conjecture of H.S. Witsenhausen states that the extremal configuration is given by two diametrically opposite spherical caps of equal size. In the same article, Witsenhausen proves M_n <= 1/n. A result of A.M. Raigoroskii from 1999 gives exponentially decreasing upper bounds for M_n via a Frank-Wilson type approach. However for n=3, the original 1/3 bound of Witsenhausen is the best known. In this talk we outline a proof that M_3 is strictly less than 1/3. This is joint work with Oleg Pikhurko.

Nov'29, 2013 Yi Zhao (Atlanta)
Minimum degree thresholds for Hamilton cycles in k-uniform hypergraphs

Given positive integers t<k, a k-uniform hypergraph (k-graph) is called a (k, t)-cycle if its vertices can be ordered cyclically such that each of its edges contains k consecutive vertices and two consecutive edges share exactly t vertices. We determine the minimum codegree threshold that ensures a Hamilton t-cycle in a k-graph for all t< k/2, and the minimum vertex degree threshold that ensures a Hamilton 1-cycle in a 3-graph. This improves several asymptotic results obtained earlier. In addition, we determine the minimum vertex degree threshold for a perfect C_4-tiling in a 3-graph, where C_4 is the 3-graph with four vertices and two edges.
These are joint works with Jie Han.

---

Dec'6, 2013 Tereza Klimošová (Warwick)
Infinite dimensional finitely forcible graphon

Graphons are analytic objects associated with convergent sequences of graphs. Problems from extremal combinatorics and theoretical computer science led to a study of graphons determined by finitely many subgraph densities, which are referred to as finitely forcible. We show that there exists a finitely forcible graphon such that the topological space of its typical points has infinite Lebesgue covering dimension, disproving the conjecture by Lovasz and Szegedy. The talk is based on joint work with Roman Glebov and Daniel Kral.

---

Jan'10, 2014 Vitaliy Kurlin (Durham)
Book embeddings of Reeb graphs

Let X be a simplicial complex with a piecewise linear function f:X->R. The Reeb graph Reeb(f,X) is the quotient of X, where we collapse each connected component of $f^{-1}(t)$ to a single point. Reeb graphs are used as simple representations of shapes in image analysis. For instance, f can be a height function on a triangulated subset of a Euclidean space. One of the obstacles in practice is to visualise abstract Reeb graphs in a low-dimensional space. We prove that any Reeb graph (more generally, any directed acyclic graph) can be embedded into a multi-page book, which is the product of the real line and a star graph with several edges attached to one central vertex. In such a book embedding all nodes of the graph lie in the binding axis and each oriented arc of the graph is in one page. We give a simple code of any book embedding and can work with codes instead of abstract Reeb graphs. arXiv: http://arxiv.org/abs/1312.1725

---

Jan'17, 2014 Colin Cooper (King's College London)
Random walks and the component structure of the vacant set

The first part of the talk is an introduction to discrete random walks on finite graphs. The cover time $C(G)$ of a connected graph $G$ is the maximum of the expected time for a random walk to visit all vertices of the graph, taken over all possible starting positions of the walk.

The vacant set of a random walk is the set of vertices of the graph so far unvisited by the walk. This gives a more precise description of the likely behavior of the walk than the notion of cover time given above.

The second part of the talk is a description of the change in structure of the vacant set of the random walk. We consider random walks on two classes of random graphs ($G_{n,p}$ and $G_g$) and explore the likely component structure of the vacant set. In both cases, the size of the vacant set $N(t)$ can be obtained explicitly as a function of the walk step $t$.

---

Jan'24, 2014 Richard Sharp (Warwick)
A Weil-Petersson metric for metric graphs

A (finite) graph may be made into a metric graph by assigning lengths to the edges. The space of all such assignments on a given graph (suitably normalized) is, in some sense, an analogue of the moduli space of a Riemann surface. This moduli space supports a natural Riemannian metric: the Weil-Petersson metric. In this talk, we shall propose a analogue of this metric in the graph case, defined using ideas from ergodic theory, and discuss some of its properties. I hope the talk will be fairly accessible. This is joint work with Mark Pollicott.

---

Feb'7, 2014 Danny Hefetz (Birmigham)
We consider several biased Chooser-Picker and Picker-Chooser games and determine (or at least approximate) their threshold biases. We also discuss their relations to analogous Maker-Breaker and Avoider-Enforcer games and the probabilistic intuition they exhibit. Based on joint work with Malgorzata Bednarska-Bzdega and Tomasz Luczak.

---

Feb'14, 2014 Jan Foniok (Warwick)
Theorem (Geller, Stahl): Let G be a graph. Then the lexicographic product G[K_2] is n-colourable if and only if G admits a homomorphism to the Kneser graph K(n,2).

Theorem (El-Zahar, Sauer): For two graphs G and H, the categorial product G × H is n-colourable if and only if G admits a homomorphism to the exponential graph K_n^H.

What do these two theorems have in common? Each is an example of the same phenomenon, known in category theory as adjoint functors. I will explain what they are and show some other applications, such as a circular version of the Gallai–Roy (–Hasse–Vitaver) Theorem. Time permitting, I will also discuss their applications in the complexity of constraint satisfaction problems.

---

Feb'21, 2014 Franz Kiraly (UCL)
We study the properties of two kinds of matroids: (a) algebraic matroids and (b) finite and infinite matroids whose ground set have some canonical symmetry, for example row and column symmetry and transposition symmetry.

For (a) algebraic matroids, we expose cryptomorphisms making them accessible to techniques from commutative algebra. This allows us to introduce for each circuit in an algebraic matroid an invariant called circuit polynomial, generalizing the minimal polynomial in classical Galois theory, and studying the matroid structure with multivariate methods.

For (b) matroids with symmetries, we introduce combinatorial invariants capturing structural properties of the rank function and its limit behavior, and obtain proofs which are purely combinatorial and do not assume algebraicity of the matroid; these imply and generalize known results in some specific cases where the matroid is also algebraic.

These results are motivated by, and readily applicable to framework rigidity, low-rank matrix completion and determinantal varieties, which lie in the intersection of (a) and (b) where additional results can be derived. We study the corresponding matroids and their associated invariants, and for selected cases, we characterize the matroidal structure and the circuit polynomials completely.

http://arxiv.org/abs/1312.3777

---

Feb'28, 2014 Humberto Naves
In this talk we present a general approach connecting biased Maker-Breaker games and problems about local resilience in random graphs. Using this method, we investigate the threshold bias b for which Maker can win certain (1 : b) games. We utilize this approach to prove new results and also to derive some known results about biased games. Joint work with: Michael Krivelevich and Asaf Ferber

---

Mar' 7, Matthias Hamann
We will discuss the decomposition problem of a graph into its `k-connected pieces’. For k=2 this is given by the well-known block-cutvertex tree and Tutte gave a solution for k=3. A notion due to Mader (k-blocks) offered recently a way to extend Tutte’s decomposition theorem to arbitrary k. We will discuss this new decomposition theorem.

Robertson and Seymour suggested another concept for these `k-connected pieces’: tangles of order k. We will discuss the connections between tangles and k-blocks and obtain an even stronger result: one which combines the decomposition theorem for k-blocks and the one for tangles.

We also address the existence problem of k-blocks (i.e. what assumptions on a graph will force it to contain a k-block) and some algorithmic questions.

---

Mar'14, Andrew Thomason (Cambridge)
Independent sets in hypergraphs

Quite a few graph theoretical questions can be phrased in terms of
independent sets in hypergraphs. Some nice results could be proved if the
number of independent sets were small, but usually it is too big. We give
some examples, such as list colouring of graphs and hypergraphs, sparse
Turan theorems, counting solutions to equations, counting graphs with a
given property, and so on.

For some of these applications, it would suffice to replace the collection
of independent sets by a smaller collection of "containers". This is a
collection of sets such that each independent set is a subset of a
container set. To be useful, each container must not be too big and the
total number of containers must not be too big: these statements can be
made precise and will be illustrated by examples.

We demonstrate a simple way to construct containers in a simple hypergraph:
though not optimal, this is enough to give useful information in several of
the cases above, such as finding the size of hereditary properties. (Joint
work with David Saxton.)

---

May 2, Johannes Carmesin

We give an introduction to infinite matroids and the matroid intersection conjecture, the most important open problem about them. This talk is self contained and includes many examples.

---

May 9, 2014 David Gamarnik (MIT)
Convergent sequences of sparse graphs: A large deviations approach

The theory of converging graph sequences is well developed for the class of dense graphs. The theory of converging sparse graph sequences, however, is far less understood. We show that prior definitions of converging sparse graph sequences are inadequate to capture important graph theoretic and statistical physics properties, and introduce a new definition based on the
large deviations theory. We show that the new definition implies most the known types of convergences and conjecture
that sparse random graphs are converging in the sense of the new definition. Establishing this conjecture will have
an important implications for the theory of spin glasses.

Joint work with Jennifer Chayes and Christian Borgs (Microsoft Research)

---

May 30, 2014 Ofer Zeitouni (Weizmann)

The Barvinok--Godsil-Gutman estimator for the permanent of a matrix $A$ with positive entries is the determinant squared of the Hadamard product of $A$ with a matrix of i.i.d. standard Gaussian. Since the expectations of the latter is the permanent, analysis of the estimator is closely related to the study of concentration properties, and in particular singular values estimates. For well connected matrices $A$ (a notion that will be explained in the talk), we derive sharp estimates on the performance of the BGG estimator. Joint work with Mark Rudelson http://arxiv.org/abs/1301.6268

---

May 16, 2014 Anita Liebenau (Warwick)
What is Ramsey-equivalent to the clique?

A graph G is Ramsey for H if every two-colouring of the edges of G contains a monochromatic copy of H. Two graphs H and H' are Ramsey-equivalent if every graph G is Ramsey for H if and only if it is Ramsey for H'. In the talk we discuss the problem of determining which graphs are Ramsey-equivalent to the complete graph K_k. In particular we prove that the only connected graph which is Ramsey-equivalent to K_k is itself. This gives a negative answer to a question of Szabó, Zumstein and Zürcher.

For the proof we determine the smallest possible minimum degree that a minimal Ramsey graph for K_k . K_2 (the graph containing the clique with a hanging edge) can have.

This represents joint work with Jacob Fox, Andrey Grinshpun, Yury Person and Tibor Szabó.

---

May 23, 2014 Natan Rubin (Jussieu Institute of Mathematics/Paris 6)
Title: How many times a Delaunay triangulation can change?

Given a finite set P of points in the plane, three points of P form a Delaunay triangle if their circumscribing circle contains no further points of P. These triangles form the famous Delaunay triangulation which, along with its dual Voronoi diagram, is central to Combinatorial Geometry.

Despite several decades of intensive study, our understanding of the combinatorial behavior of Voronoi and Delaunay structures is still far from satisfactory. For example, if the points of P are moving along lines at uniform speed, it has been long conjectured that their Delaunay triangulation experiences at most near-quadratically many discrete changes during the motion.

Our recent study affirms the above conjecture. This is done in a far more general, purely topological setting. We discuss this work in connection with some other fundamental results on the combinatorial complexity of geometric structures. No prior knowledge of combinatorial geometry is assumed.

---

Jun'13, 2014 Andrzej Grzesik (Krakow)
Around the Caccetta-Haggkvist Conjecture

We will present some results and new approaches to the Caccetta-Haggkvist Conjecture and to related conjectures, in particular Seymour Second Neighbourhood Conjecture.

---

Jun'20, 2014 Balazs Udvari (Szeged)
The rectilinear crossing number of K_n

---

Jun'27, 2014 Jon Noel (Oxford)
The choice number of a graph $G$ is the minimum integer $k$ such that whenever each vertex of $G$ is assigned to a list of $k$ colours, there exists a proper colouring of $G$ in which every vertex is mapped to a colour in its list. It is easily observed that the choice number is at least as large as the chromatic number; however, in general, the choice number is not bounded above by any real-valued function of the chromatic number.

In this talk, we discuss a proof of a conjecture of Ohba which states that if $|V(G)|\leq 2\chi(G)+1$, then the choice number of $G$ is equal to the chromatic number of $G$. We also discuss a generalisation which implies a best possible bound on the choice number of graphs with at most $3\chi$ vertices, and several open problems for future study.

This is joint work with Bruce Reed, Doug West, Hehui Wu and Xuding Zhu.

---