# 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
Ramsey-Turan-type of extremal problems
28 Oct Ping Hu (Warwick)

11 Nov Alexey Pokrovskiy (ETH)
18 Nov Agnes Backhausz (Eötvös Loránd University)
25 Nov Richard Montgomery (Cambridge)
2 Dec Tim Netzer (Innsbruck)
Checking Inclusion of Polytopes and Spectrahedra
9 Dec Andrew Granville (UCL)

Date Name Title
13 Jan
20 Jan
27 Jan
3 Feb
10 Feb
17 Feb
24 Feb
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
30 June

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.

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.