Aris Papadopoulos (University of Leeds)
- Date
- Wednesday 13 March 2024, 1.00 PM
- Location
- MALL
Zarankiewicz’s Problem and Model Theory
Note: this is a 2-hour seminar for both model and set theorists.
A shower thought that anyone interested in graph theory must have had at some point in their lives is the following: `How “sparse" must a given graph be, if I know that it has no “dense” subgraphs?’. This curiosity definitely crossed the mind of Polish mathematician K. Zarankiewicz, who asked a version of this question formally in 1951. In the years that followed, many central figures in the development of extremal combinatorics contemplated this problem, giving various kinds of answers. Some of these will be surveyed in the first part of my talk.
So far so good, but this is a model (and set) theory seminar and the title does include the words “Model Theory"… In the second part of my talk, I will discuss how the celebrated Szemerédi-Trotter theorem gave a starting point to the study of Zarankiewicz’s problem in “geometric” contexts, and how the language of model theory has been able to capture exactly what these contexts are. I will then ramble about improvements to the classical answers to Zarankiewicz’s problem when we restrict our attention to one of: (a) semilinear/semibounded o-minimal structures; (b) Presburger arithmetic, and (c) various kinds of Hrushovski constructions. The second hour of the talk will essentially be devoted to proofs. Which of (a),(b), or (c) will occupy the second hour will depend on input from the audience.
The new results appearing in the talk were obtained jointly with Pantelis Eleftheriou.