Below you'll find an overview of the past seminars in this series from 2016. The seminars are listed in reverse chronological order, most recent first.
Thursday 24 March - Oleg Pikhurko (Warwick)
Measurable circle squaring
In 1990 Laczkovich proved that one can split a disk into finitely many parts and move them to form a partition of a square, thus solving the long-standing Tarski's circle squaring problem. I will discuss our result with András Máthé and Łukasz Grabowski that, additionally, all parts can be made Lebesgue measurable. This is achieved by showing that some analytic version of the augmenting path algorithm stabilises almost everywhere.
Thursday 17 March - Emilio Pierro (LSE)
Quantities associated to the subgroup lattice of a finite group.
We begin by discussing the Möbius function of a finite group G. This function is primarily used to determine enumerative functions associated to G, such as the number of ordered generating pairs of elements of G. We illustrate this method in the specific case of the small Ree groups by using their natural 2-transitive permutation representation. We also give some results on the generation and asymptotic generation of the small Ree groups. Finally, we will describe the connection between the Möbius function and the topology of the subgroup lattice regarded as a simplicial complex.
Thursday 10 March - Márton Naszódi (Budapest)
Proof of a conjecure of Bárány, Katchalski, and Pach
Bárány, Katchalski, and Pach proved the following quantitative form of Helly's theorem: If the intersection of a family of convex sets in Euclidean d-space is of volume one, then the intersection of some subfamily of at most 2d members is of volume at most some constant v(d). They gave the bound v(d) < d^{2d^2}, and conjectured that v(d) < d^{cd} holds. We present a proof of this conjecture, and some related results.
Thursday 25 February - Diana Piguet (Prague)
Tilings in graphons
In the talk we shall discuss the notion of tiling, vertex-cover and LP duality in graphons. Joint work with J. Hladky and P. Hu
Thursday 18 February - Nick Day (QMUL)
Colourings with no Short Odd Cycles
We show that for any positive integer r there exists an integer k and a k-colouring of the complete graph K_{2^{k} + 1} such that the colouring contains no monochromatic odd cycle of length less than r. This answers a question of Erdős and Graham. We use these colourings to give new lower bounds on the k-colour Ramsey number of the odd cycle and prove that, for all odd r and all k sufficiently large, there exists a constant c = c(r) > 0 such that the k-colour Ramsey number of C_{r} is at least (r-1)(2+c)^{k-1}.
This is joint work with Robert Johnson.
Seminar jointly hosted by Discrete Mathematics and Game Theory and Operations Research
Thursday 11 February - Christoph Dürr (Paris)
Online Algorithms for Multi-Level Aggregation
Online algorithms receive their input in form of request sequences and need to make irrevocable decisions at each request. A classical example is the paging problem. We introduce standard techniques used to design online algorithms and their analysis, for the ski rental problem, the cow path problem and load balancing. Finally we talk about a personal work on the multi-level aggregation problem.
This is a joint work with Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, Pavel Veselý.
Thursday 4 February - Iskander Aliev (Cardiff)
Lattice programming gaps, quotient lattice graphs and Frobenius numbers.
We will consider a lattice problem that takes its origin in integer programming. Let L be a full-dimensional sublattice of Z^n and r be an integer n-dimensional vector. We are interested in the minimum of a linear objective function cx over all non-negative points of the affine lattice r+L. Given L and c, the worst-case scenario in this problem is described by the lattice programming gap gap(L, c) - the largest value of such minima as r varies over Z^n.
Hosten and Sturmfels proved in 2007 (in a more general setting) that gap(L, c) can be computed in polynomial time when the dimension n is fixed. We will show that computing the lattice programming gap is NP-hard when n is a part of input. We also discuss lower and upper bounds for gap(L, c) in terms of c and the determinant of L.
The proofs are based on a connection between the lattice programming gaps, quotient lattice graphs and Frobenius numbers.
Thursday 28 January - Alexandr Polyanskii (Haifa)
On the odd area
Let F be a family that consists of an odd number of parallel translates of a given (compact and with positive measure) set S in the plane. We are interested in the area of those points in the plane that belong to an odd number of sets in F. The minimum (infimum) possible such area is called the odd area of S. We will present known results for different S and discuss a recent result dealing with the odd area of the unit disc.
This talk is based on joint work with Rom Pinchasi.
Thursday 14 January - Elisabetta Candellero (Warwick)
Percolation and isoperimetric inequalities
In this talk we will discuss some relations between percolation on a given graph G and its geometry.There are several interesting questions relating various properties of a graph, such as growth or dimension, and the process of percolation on it. In particular we will look for conditions under which its critical percolation threshold is non-trivial, that is: p_c(G) is strictly between zero and one. In a very influential paper on this subject, Benjamini and Schramm asked whether it was true that for every graph satisfying dim(G) > 1, one has p_c(G) < 1. We will explain this question in detail and present some recent results that have been obtained in this direction.
This talk is based on a joint work with Augusto Teixeira (IMPA, Rio de Janeiro, Brazil).