Recent topics in Discrete Mathematics

Reading group on recent topics in the area, Autumn 2020.

Date: Wednesday 18 November 2020, 12:15 

Topic: On the Erdos-Szekeres problem (by Andrew Suk)

Speaker: Lluís Vena

Abstract: The Erdös-Szekeres problem asks for the minimum number of points ES(n) on the plane, in general position, that ensures n of those
points to be in convex position. In 1935, Erd\Hos and Szekeres showed that 2^{n-2}+1\leq ES(n) \leq \binom{2n-4}{n-2}+1 \approx 4^n/\sqrt{n} The true value is conjectured to be closer to the lower bound. Some improvements in the upper bound were made over the years, but not in the asymptotics behaviour. We will explain the result by Suk, that tightens the upper bound  to 2^{n+o(n)}.

Link: https://us02web.zoom.us/j/85860866036?pwd=cmJtL0xlOWgzSEw2RWxFcnk0aVIxQT09

Slides: here

Video: here

Date: Wednesday 4 November 2020, 12:15 

Topic: Introduction to Quasi-random groups, based on the work of Gowers (Part 2)

Speaker: Juanjo Rué

Abstract: In this session we will finith Gowers proof to show that there are small sets in SL2(p) which are product-free, and we will use the notion of quasi-random graph to define the notion of quasi-random group

Link: https://us02web.zoom.us/j/85860866036?pwd=cmJtL0xlOWgzSEw2RWxFcnk0aVIxQT09

Slides available here

Video: here (UPC login required) 

 Date: Wednesday 28 October 2020, 12:15 

Topic: Introduction to Quasi-random groups, based on the work of Gowers (Part 1)

Speaker: Juanjo Rué

Abstract: It is an easy exercise to show that the maximal size of a sum-free set in the integers [n] is equal to n/2. We will show that when dealing with the same question in other ambient groups the answer could be completely different. For instance, we will show that linear-size sets on SL_2(p) cannot be product-free. In order to understand what is happening, we will develop a little on representation theory of linear groups, as well as spectral theory for bipartite graphs. All of this will let us arrive at the notion of quasi-random group, introduced by Gowers. If time permits, we will link this notion with quasi-randomness in graphs.

Link: https://us02web.zoom.us/j/85860866036?pwd=cmJtL0xlOWgzSEw2RWxFcnk0aVIxQT09

Video: here (UPC login required) 

Date: Wednesday 7 October 2020, 12:15 

Topic: Paper presentation of D. Conlon and A. Ferber, Lower bounds for multicolor Ramsey numbers (2020)

Speaker: Matthew Coulson

Meet Link: https://us02web.zoom.us/j/85860866036?pwd=cmJtL0xlOWgzSEw2RWxFcnk0aVIxQT09

Slides: here

Video (UPC login required): here