Discrete Geometry and Combinatorics Seminar Autumn 2018

All seminars (unless otherwise stated) will take place on Tuesdays at 5pm in Maths Room 707 (25 Gordon Street) - see the map for further details. If you require any more information on the Discrete Geometry and Combinatorics seminars, please contact Dr John Talbot (e-mail: j.talbot AT ucl.ac.uk or tel: 020-7679-4102).

23 Oct 2018

Speaker: Dr Liana Yepremyan (University of Oxford)

Title: On the number of symbols that forces a transversal

Akbari and Alipour conjectured that any Latin array of order $n$ with at least $n^2/2$ symbols contains a transversal, or equivalently, every  proper-edge coloring of the complete bipartite graph $K_{n,n}$  with n^2/2 colours contains a rainbow perfect matching. In this talk we will present a proof of this conjecture in a stronger sense: we show that $n^{399/200}$ colours suffice. This is joint work with Peter Keevash.

30 Oct 2018

Speaker: Dr Andrey Kupavskii (University of Birmingham)

Title: Crossing Tverberg theorem

The famous Tverberg theorem states that, given a family of (d+1)n points in R^d in general position, one can find n vertex-disjoint d-simplices with vertices in P that all share a common point. We show that we can choose these simplices in such a way that, additionally, their boundaries mutually intersect. In particular, on any 3n points in general position on the plane one can find n mutually crossing triangles. Joint work with R. Fulek, B. Gartner, P. Valtr and U. Wagner.

Wed 28 Nov 2018 at 5pm in Room 706

Speaker: Oleg Pikhurko (University of Warwick)

Title: Measurable equidecomposition via augmenting paths

Two subsets A,B of R^n are called equidecomposable if one can partition A into finitely many parts and move them using isometries to form a partition of B. One example is the famous Banach-Tarski Paradox that a unit ball can be doubled if the dimension n is at least 3.

We present a sufficient criterion for the existence of equidecompositions with Lebesgue measurable parts, by running an analytic version of the augmenting path algorithm. Our criterion is strong enough to characterise all subsets of R^n for n at least 3 which are measurably equidecomposable to, for example, a cube.

Joint work with András Máthé and Łukasz Grabowski

04 Dec 2018

Speaker: Nora Frankl (LSE)

Title: Bounding the number of unit simplices determined by a set of n points in R^d


We give general upper bounds on the maximum number of regular unit simplices with k vertices determined by a set P of n points in R^d. For each d>3 we determine the order of magnitude for the smallest k for which the problem is non-trivial. We also study the specific case when P is of diameter one, derive stronger bounds and determine the right order of magnitude in the smallest open case. Joint work with Andrey Kupavskii and Alexandr Polyanskii.