Skip to main content

Combinatorics Seminar

The seminars are held on Friday at 2pm-3pm


Agelos Georgakopoulos
Oleg Pikhurko

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}s-Ko-Rado 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}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.

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.