Reading group

Webpage of GAPCOMB's reading group

We organize a weekly reading group joint with the research team of Prof. Albert Atserias from the computer science department in order to cover some hot topics in the interaction of theoretical computer science and combinatorics.

In Autumn term 2020-21 we run the following reading group on Wednesdays online:

RECENT TRENDS IN DISCRETE MATHEMATICS

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

The previous sessions of this reading group are the following: