Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, March 06, 2018, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Istvan Tomon (EPFL)
Two subsets A,B of an n-element ground set X are said to be crossing if none of the four sets A\cap B, A\B, B\A and X-(A\cup B) are empty. It was conjectured by Karzanov and Lomonosov forty years ago that if a family F of subsets of X does not contain k pairwise crossing elements, then |F|=O(kn). For k=2,3, the conjecture is true, but for larger values of k the best known upper bound is O(knlog n). We improve this bound by showing that |F|=O_k(nlog*n) also holds. This is joint work with Andrey Kupavskii and Janos Pach.
Automatic MiSe System Software Version 1.4803M | admin login