Combinatorics Seminar

Organisers:

Term 1 2016/17 - Room MS.04

Date Name Title
7 Oct Felix Reidl (Aachen) Characterising structural sparseness by neighbourhood complexity
Or: If your neighbourhood is boring you probably live in a sparse region.
14 Oct David Ellis (QMUL)  Some applications of the $p$-biased measure to Erd\H{o}s-Ko-Rado type problems
21 Oct Maryam Sharifzadeh (Warwick) Ramsey-Turan-type of extremal problems
28 Oct Ping Hu (Warwick) Tilings in graphons
4 Nov Katherine Staden (Warwick) The number of triangles in a graph with a given number of vertices and edges
11 Nov Alexey Pokrovskiy (ETH) Rainbow cycles and rainbow expanders
18 Nov Agnes Backhausz (Eötvös Loránd University) On the graph limit approach to eigenvectors of random regular graphs
25 Nov Richard Montgomery (Cambridge) Subdivisions in C_4-free graphs
2 Dec Tim Netzer (Innsbruck) Checking Inclusion of Polytopes and Spectrahedra
9 Dec Will Perkins (Birmingham)
An occupancy approach to bounding graph polynomials

Term 2 2016/17 - Room MS.04

Date Name Title
13 Jan Christoph Koch (Warwick)
Jigsaw percolation on random hypergraphs
20 Jan Mihyun Kang (TU-Graz)

27 Jan Angelika Steger (ETH Zurich)

3 Feb

10 Feb Jakub Sosnovec (Warwick)
17 Feb Amin Coja-Oghlan (Frankfurt)

24 Feb Jakub Konieczny (Oxford)
3 Mar
10 Mar
17 Mar

Term 3 2016/17 - Room MS.04

Date Name Title
28 April
5 May
12 May
19 May
26 May
2 June
9 June
16 June
23 June tbc

30 June tbc

7 Oct Felix Reidl (Aachen) Characterising structural sparseness by neighbourhood complexity

Or: If your neighbourhood is boring you probably live in a sparse region.

Structurally sparse graphs always had a special place in algorithm theory:
almost any problem becomes much more tractable if we restrict ourselves to
nice graph classes like trees, planar graphs, or graphs excluding a minor.
On the other hand, algorithms on such classes are only of limited use
in real-world settings---hardly any real-world network exhibits these stricter
notions of structural sparseness.

In this talk we will explore a notion of sparseness (so-called bounded expansion
classes introduced by Nesetril and Ossona de Mendez) that is general enough
to hold in real-world settings while still providing use with a rich algorithmic
toolkit. In particular, we will see a novel characterisation of bounded expansion
of structurally sparse graphs.

14 Oct: David Ellis (QMUL) Some applications of the $p$-biased measure to Erd\H{o}s-Ko-Rado type problems

Erd\H{o}s-Ko-Rado type problems' are well-studied in extremal combinatorics; they concern the sizes of families of objects in which any two (or any $r$) of the objects in the family 'agree', or 'intersect', in some way.

If $X$ is a finite set, the '$p$-biased measure' on the power-set of $X$ is defined as follows: choose a subset $S$ of $X$ at random by including each element of $X$ independently with probability $p$. If $\mathcal{F}$ is a family of subsets of $X$, one can consider the {\em $p$-biased measure} of $\mathcal{F}$, denoted by $\mu_p(\mathcal{F})$, as a function of $p$. If $\mathcal{F}$ is closed under taking supersets, then this function is an increasing function of $p$. Seminal results of Friedgut and Friedgut-Kalai give criteria under which this function has a 'sharp threshold'. Perhaps surprisingly, a careful analysis of the behaviour of this function also yields some rather strong results in extremal combinatorics which do not explicitly mention the $p$-biased measure - in particular, in the field of Erd\H{o}s-Ko-Rado type problems. We will discuss some of these, including a recent proof of an old conjecture of Frankl that a symmetric three-wise intersecting family of subsets of $\{1,2,\ldots,n\}$ has size $o(2^n)$, and some 'stability' results characterizing the structure of 'large' $t$-intersecting families of $k$–element subsets of $\{1,2,\ldots,n\}$. Based on joint work with (subsets of) Nathan Keller, Noam Lifschitz and Bhargav Narayanan.

21 Oct: Maryam Sharifzadeh (Warwick) Ramsey-Turan-type of extremal problems

Motivated by the fact that the extremal example for Tur\'an theorem has linear-sized independent sets, Erd\H os and S\'os initiated the so-called Ramsey-Tur\'an theory, where they studied the maximum size of an $H$-free graph $G$ with the additional condition that $\alpha(G)=o(|G|)$. During this talk, I will discuss the Ramsey-Tur\'an variation of some classical results, whose extremal graphs are close to the Tur\'an graph, including Corr\'adi-Hajnal theorem on triangle factors in graphs and Erd\H os-Rothschild problem on the number of edge-colorings with no monochromatic clique.

Joint work partly with J\'ozsef Balogh and Hong Liu, and partly with J\'ozsef Balogh and Theodore Molla.

28 Oct: Ping Hu (Warwick) Tilings in graphons

We introduce a counterpart to the notion of vertex disjoint tilings by copy of a fixed graph F to the setting of graphons. The case F be an edge gives the notion of matchings in graphons. We give a transference statement that allows us to switch between the finite and limit notion, and derive several favorable properties, including the LP-duality counterpart to the classical relation between the fractional vertex covers and fractional matchings/tilings. As an application of our theory, we determine the asymptotically almost surely F-tiling number of inhomogeneous random graphs G(n,W). As another application, we give a strengthening of a theorem of Komlos, which gives minimum degree threshold that guarantees a prescribed lower bound on the fractional F-cover number of a graphon W.

Joint work with Jan Hladky and Diana Piguet.

4 Nov Katherine Staden (Warwick) The number of triangles in a graph with a given number of vertices and edges

The famous theorem of Tur\'an from 1940 states that every $n$-vertex graph with at least $n^2/4$ edges contains at least one triangle. Erd\H{o}s asked for a quantitative version of this statement: for every n and m, how \emph{many} triangles an must an n-vertex m-edge graph contain? This question has received a great deal of attention, and a long series of partial results culminated in an asymptotic solution by Razborov, extended to larger cliques by Nikiforov and Reiher. Currently, an exact solution is only known for a small range of edge densities, due to Lov\'asz and Simonovits. In this talk, I will discuss the history of the problem and recent work which gives an exact solution for almost the entire range of edge densities. This is joint work with Hong Liu and Oleg Pikhurko.

4 Nov: Richard Montgomery (Cambridge) Subdivisions in C_4-free graphs

Bollob\'as and Thomason, and independently Koml\'os and Szemer\'edi, showed in 1994 that any graph $G$ with average degree $d(G)$ contains a subdivision of a clique with at least $c\sqrt{d(G)}$ vertices, for some universal constant $c>0$. In 1999, Mader conjectured that $C_4$-free graphs $G$ in fact contain a subdivision of a larger clique, one with at least $c d(G)$ vertices, for some universal constant $c>0$. I will discuss a proof of this conjecture as well as a generalisation concerning $K_{s,t}$-free graphs.

This is joint work with Hong Liu.

11 Nov: Alexey Pokrovskiy (ETH) Rainbow cycles and rainbow expanders

A subgraph of an edge-coloured complete graph is called rainbow if all its edges have different colours. Andersen conjectured that every properly n-edge-coloured complete graph Kn has a rainbow Hamiltonian path. This seminar will be about a proof of an approximate version of this conjecture - that every properly edge-coloured Kn has a rainbow cycle of length n - O(n^{3/4}). One of the main ingredients of our proof, which is of independent interest, shows that a random subgraph of a properly edge-coloured Kn formed by the edges of a random set of colours has a similar edge distribution as a truly random graph with the same edge density. In particular it has very good expansion properties.

This is joint work with Noga Alon and Benjamin Sudakov.

18 Nov: Agnes Backhausz (Eötvös Loránd University) On the graph limit approach to eigenvectors of random regular graphs

The goal of the talk is to show how the graph limit approach
can be used to understand spectral properties of large random
regular graphs. In our work, we consider eigenvectors of
random regular graphs of fixed degree. As the number of
vertices tends to infinity, as a "limit", we investigate
invariant random processes on the infinite tree that
satisfy the eigenvalue equation and that can be "modelled" on
random regular graphs. In this infinite setting, based on
certain entropy inequalities, we could prove that (under
appropriate conditions) all these processes are Gaussian.
As a consequence, we could prove that the distribution of
delocalized eigenvectors of finite random regular graphs
is close to the Gaussian distribution. Joint work with Balazs
Szegedy.

2 Dec: Tim Netzer (Innsbruck) Checking Inclusion of Polytopes and Spectrahedra

The question whether one polytope is contained in another arises in interesting applications. Its computational complexity depends on the type of the input, and reaches from polynomial time to co-NP-hard. Spectrahedra are generalizations of polyhedra, and appear as feasible sets in semidefinite programming. In many applications, one or both of the given sets are spectrahedra, and inclusion testing becomes even more complicated, even at a conceptual level. There are certain relaxations of the problem, that work well in practice. After introducing the necessary background, we show that these relaxations are only reliable for simplices, and we derive some quantitative error bounds in the general case. The results use methods from operator theory, and some nice elementary constructions.

9 Dec: Will Perkins (Birmingham) An occupancy approach to bounding graph polynomials

I will present a new method for proving tight bounds on graph polynomials and on the number of independent sets, matchings, and colorings in regular graphs. The method is based on optimizing various observables in relevant probabilistic models from statistical physics (e.g., the hard-core, monomer-dimer, and Potts models) via linear programming relaxations. No previous knowledge of statistical physics is needed for the talk, and I will present many related open problems. Based on joint work with E. Davies, M. Jenssen, and B. Roberts.

13 Jan: Christoph Koch (Warwick) Jigsaw percolation on random hypergraphs

Jigsaw percolation was introduced by Brummit, Chatterjee, Dey, and Sivakoff as a model for interactions within a social network. It was inspired by the idea of collectively solving a puzzle. The premise is that each individual of a group of people has a piece of a puzzle all of which must be combined in a certain way to solve the puzzle. The compatibility of different puzzle pieces and the information which pairs of people meet are stored in two graphs (on a common vertex set), the puzzle graph and the people graph. Bollobás, Riordan, Slivken, and Smith studied the process when both graphs are given by independent binomial random graphs. More abstractly the process can be seen as a notion of simultaneous connectedness of a pair of (random) graphs. We transfer the process to hypergraphs in the context of high-order connectedness. We provide the asymptotic order of the critical threshold probability for percolation when both hypergraphs are chosen binomially at random, extending the result of Bollobás, Riordan, Slivken, and Smith. The evolution of the process is closely related to the presence of traversable triples in the pair of random hypergraphs.

This is joint work with Béla Bollobás, Oliver Cooley, and Mihyun Kang.