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) 

14 Oct  David Ellis (QMUL) 
Some applications of the $p$biased measure to Erd\H{o}sKoRado type problems 
21 Oct  Maryam Sharifzadeh (Warwick) 

28 Oct  
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 
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.
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.