Combinatorics Seminar
The seminars are held on Friday at 2pm3pm 
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}sKoRado type problems 
21 Oct  Maryam Sharifzadeh (Warwick) 
RamseyTurantype of extremal problems 
28 Oct  Ping Hu (Warwick) 

4 Nov  Katherine Staden (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) 
Term 2 2016/17  Room MS.04
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 realworld settingshardly any realworld network exhibits these stricter
notions of structural sparseness.
In this talk we will explore a notion of sparseness (socalled bounded expansion
classes introduced by Nesetril and Ossona de Mendez) that is general enough
to hold in realworld settings while still providing use with a rich algorithmic
toolkit. In particular, we will see a novel characterisation of bounded expansion
classes by 'neighbourhood complexity' that adds to the already diverse framework
of structurally sparse graphs.
14 Oct: David Ellis (QMUL) Some applications of the $p$biased measure to Erd\H{o}sKoRado type problems
Erd\H{o}sKoRado type problems' are wellstudied 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 powerset 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 FriedgutKalai 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}sKoRado type problems. We will discuss some of these, including a recent proof of an old conjecture of Frankl that a symmetric threewise 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) RamseyTurantype of extremal problems
Motivated by the fact that the extremal example for Tur\'an theorem has linearsized independent sets, Erd\H os and S\'os initiated the socalled RamseyTur\'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 RamseyTur\'an variation of some classical results, whose extremal graphs are close to the Tur\'an graph, including Corr\'adiHajnal theorem on triangle factors in graphs and Erd\H osRothschild problem on the number of edgecolorings 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 coNPhard. 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.