Combinatorics Seminar

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

28 Oct

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

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.