Research Experience for Undergraduates (REU) 2023 will continue in Prague starting from 24.7.2023. The event is supported by CoSP project, which received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie action. The programme will take place at the premises of Charles University, Malostranské náměstí 2/25, Prague 1.
24.7.2023 Monday
10:00 Jan Kynčl: On Erdos-Szekeres Theorem
(lecture and presentation of the problems to work on)
Afternoon: Work on the problems followed by solutions and discussion
25.7.2023 Tuesday
10:00 Martin Balko: Annoying (but beautiful) visibility problems
(lecture and presentation of the problems to work on)
Abstract: In this talk, we will survey and explore known problems and conjectures about visibility in point sets in the plane. Here, two points p and q are visible in a planar point set P if there is no point of P lying between p and q on the line segment pq. All these problems have couple of things in common: they are easy to state but, somewhat annoyingly, are also very difficult to solve and most of them remain open. To give an example, we will discuss the Blocking conjecture about placing n points in the plane in general position with the smallest number m of blocking points between them so that no two of the n points are visible in the resulting set of n+m points.
Afternoon: Work on the problems followed by solutions and discussion
26.7.2023 Wednesday
10:00 Jan Volec: Lopsided Lovasz Local Lemma
(lecture and presentation of the problems to work on)
Abstract: In the first part, we are going to recall the so-called first moment method and Markov's inequality, and apply them to a few problems in combinatorics and number theory.
In the second part, we introduce symmetric, general and lopsided variants of Lovasz Local Lemma, and use the lemma to improve some of the results from the first part.
We conclude by presenting the framework of Lu and Szekely on applying the Lopsided Lovasz Local Lemma in the setting of random injections, and use it to prove the following: if the edges of K_n are colored in such a way that every vertex sees every color on its incident edges at most n/100 times, then the coloring contains a properly colored Hamilton cycle.
Afternoon: Work on the problems followed by solutions and discussion
27.7.2023 Thursday - CoSP student workshop
10:00 - 10:45 Guillermo Gamboa: Sparse metric hypergraphs
Abstract: Given a metric space (X,d), we say y is between x and z if d(x,z)=d(x,y)+d(y,z). A metric space gives rise to a 3-uniform hypergraph that has as hyperedges those triples {x,y,z}, where y is between x and z. Such hypergraphs are called metric. In this talk, we will consider the other direction: Is any given a 3-uniform hypergraph metric? We will present some examples of metric and non metric 3-uniform hypergraphs, as well as introduce a notion of sparsity for these. Finally, we will prove that such sparse 3-uniform hypergraphs are metric.
10:45 - 11:30 Caleb Fong: Compactness in Combinatorics
Abstract: For many combinatorial problems which have been resolved in the finite setting, a natural question is whether similar results hold in the infinite setting. For these questions, the compactness theorem from first-order logic sometimes comes in handy. In this mostly expository talk, we will explain this theorem, talk about its applications and deficiencies, and (if time permits) talk about a research problem which made me care about compactness in the first place.
11:30 - 12:15 Sumi Vora: A Theoretical Survey of Graph Neural Networks (GNNs)
Abstract: Graph Neural Networks (GNNs) are a type of deep learning model that can operate on graph structured data. In this talk we provide a survey of the theoretical foundations for graph neural networks, deriving the necessary formulas for updating node embeddings and minimizing loss. We’ll conclude with a discussion of algorithms for fairness and explainability for GNNs.
12:15 - 14:00 Lunch break
14:00 - 14:45 Jakub Petr: Automorphisms of the Symmetric Groups
Abstract: We will go over the basics of Group Theory and get to know the notion of automorphisms. At last, we will show why S_6 is the only symmetric group that can have an outer automorphism.
14:45 - 15:30 Gaurav Kucheriya: Turán-type problems in edge-ordered graphs
Abstract: The main objective of Turán-type graph problems is to maximize the number of edges a graph can have under certain (forbidding) conditions. This talk will give an overview of some popular results in this field. In particular, we will also see the extension of this problem to edge-ordered graphs. Joint work with Gabor Tardos.
28.7.2023 Friday
10:00 David Sychrovský: Algorithmic Game Theory
(lecture and presentation of the problems to work on)
In many real world situations, like minor traffic offenses in big cities, a central authority is tasked with periodic administering punishments to a large number of individuals. Common practice is to give each individual a chance to suffer a smaller fine and be guaranteed to avoid the legal process with probable considerably larger punishment. However, thanks to the large number of offenders and a limited capacity of the central authority, the individual risk is typically small and a rational individual will not choose to pay the fine. We will show that if the central authority processes the offenders in a publicly known order, it properly incentives the offenders to pay the fine. Moreover, the same holds for an arbitrary coalition.
Afternoon: Work on the problems followed by solutions and discussion
31.7.2023 Monday - 4.8.2023 Friday
Midsummer Combinatorial Workshop
MCW website: https://www.mff.cuni.cz/en/kam/events/mcw/mcw-2023
Posted on 2023-07-18