# Finite and Descriptive Combinatorics

This is the webpage (warwick.ac.uk/meascombLink opens in a new window) of the research group "Finite and Descriptive Combinatorics" whose activities are, in particular, supported by the Leverhulme Research Project Grant RPG-2018-424 "Measurable Combinatorics" (1 October 2019 - 30 September 2023) and the ERC Advanced Grant 101020255 "Finite and Descriptive Combinatorics" (1 January 2022 - 31 December 2026).

## Overview

In addition to the classical directions of extremal and probabilistic combinatorics (Turan function, Ramsey theory, etc), the group also explores emerging deep connections between combinatorics and other fields such as analysis, descriptive set theory, measured group theory, etc, with applications going both ways. One way of applying analytic techniques to finite graphs will be by means of graph limits (analytic objects of bounded complexity that capture asymptotic properties of large graphs). In the other direction, combinatorial techniques will be applied in search of "constructive'' solutions to some foundational mathematical problems, in particular building upon the recent remarkable results that one can split a 2-dimensional disk into ``definable'' pieces and re-arrange them to form a square.

## Group Members

- Irene Gil Fernandez (since 10/2020) *
- Jan Grebik (since 10/2019)
- Joseph Hyde (since 1/4/2022)
- Xizhi Liu (since 1/4/2022)
- Matteo Mazzamurro (since 02/2022) *
- Oleg Pikhurko (PI)
- Zhuo Wu (since 10/2021) *

* = co-advised PhD student

## News

- 20-24 Mar'23: Damien Gaboriau, Andrew Marks, OP and Anush Tserunyan organise Workshop on Borel and Measurable Combinatorics in Algebra and Dynamics, Fields Institute, Toronto
- May'22: group's work on circle squaring is mentioned in "Mathematics News Flash" of LMS Newsletter
- Mar'22: El Periodico publishes an article about group's work on circle squaring
- 10 Mar'22: OP serves on PhD committee of Xizhi Liu, who successfully defended his thesis "Extremal Hypergraph Problems". Congratulations, Xizhi!
- Feb'22: OP serves as reviewer of membership applications for IMTech
- Feb'22: Quanta publishes an article about some work done by the group
- 13-19 Feb'22: JG, OP and Anush Tserunyan organise Oberwolfach Mini-Workshop "Descriptive Combinatorics, LOCAL Algorithms and Random Processes"
- 3-4 Feb'22: OP serves on the Mathematics Review Panel of the Academy of Finland
- Jan'22: Some results co-authored by group members are mentioned in Bogdan Grechuk's new book "Landscape of 21st Century Mathematics: Selected Advances, 2001-2020"
- Dec'21: OP serves as expert evaluator for Postdoctoral Junior Leader Fellowships of the “la Caixa” Foundation
- 12 Oct - 7 Dec'21: JG lectures mini-course "Distributed computing, random processes and Borel combinatorics"
- JG and OP organise 2021-22 Warwick's Combinatorics Seminar
- 2-7 Aug'21: OP is a team leader of Warwick's team at the 28th International Mathematics Competition
- 14 Jul'21: OP was the internal examiner of Bogdan Alecu's PhD thesis that was successfully defended. Congratulations, Bogdan!
- Jul'21: JG was awarded Warwick's Faculty of Science Postdoctoral Prize. Congratulations, Jan!
- Apr'21: OP was awarded a 5-year ERC Advanced Grant for €1.58m
- Dec'20: OP appointed to the Program Committee of Eurocomb 2021
- 1 Dec'20: OP was the internal examiner of Yani Pehova's PhD thesis that was successfully defended. Congratulations, Yani!
- Nov'20: OP appointed to the Scientific Advisory Board of IMTech
- JG and OP organise 2020-21 Warwick's Combinatorics Seminar
- 25-30 Jul'20: George Kontogeorgiou and OP are team leaders of Warwick's team at the 27th International Mathematics Competition
- 2 Jul'20: OP was an external examiner of Jan Corsten's PhD thesis at LSE, that was successfully defended. Congratulations, Jan!
- 5 May'20: Jan Grebik successfully defended his PhD thesis "Definable graphs". Congratulations!
- 1 Jan'20: OP appointed to the Editorial Board of "Random Structures and Algorithms"
- 4 Nov'19: OP was an external examiner of François Pirot's PhD thesis at Radboud University, Nijmegen, that was successfully defended. Congratulations, François!

## Papers

All papers (pre-publication versions) should be freely available from arxiv.org. Please contact one of the authors if you have difficulty accessing them.

- L.Grabowski, A.Mathe, OP: Measurable equidecompositions for group actions with an expansion property, accepted by J Eur Math Soc, 48 pages.
- A.Blumenthal, B.Lidicky, Y.Pehova, F.Pfender, OP and J.Volec: Sharp bounds for decomposing graphs into edges and triangles, Combin Prob Comput, 30 (2021) 271-287
- H.Liu, OP and K.Staden: The exact minimum number of triangles in graphs of given order and size, Forum of Math, Pi 8 (2020) 144pp.
- M.Kang, T.Makai and OP: Supersaturation Problem for the Bowtie, European J Comb 88 (2020) 103107.
- JG and OP: Measurable versions of Vizing's theorem, Advances in Mathematics, 374 (2020) paper 107378, 40pp
- J.Kim, H.Liu, OP and M.Sharifzadeh: Asymptotic Structure for the Clique Density Theorem, Discrete Analysis (2020) Paper 19, 26pp
- OP: Borel Combinatorics of Locally Finite Graphs, in "Surveys in Combinatorics 2021" (edited by K.K.Dabrowski et al), the invited volume of the 28th British Combinatorial Conference, pages 267-319
- C.T.Conley, JG and OP: Divisibility of Spheres with Measurable Pieces, 31pp
- H.Liu, OP, M.Sharifzadeh and K.Staden: Stability from graph symmetrisation arguments with applications to inducibility, 41pp
- JG and I. Rocha: Fractional Isomorphism of Graphons, accepted to Combinatorica, 24pp
- JG: Approximate Schreier decorations and approximate Konig line coloring theorem, accepted by AHL, 11pp
- JG and Z. Vidnyánszky: Tall F
_{σ}subideals of tall analytic ideals, accepted to PAMS, 5pp - JG and OP: Large Deviation Principles for Block and Step Graphon Random Graph Models, 17pp
- O.Cooley, M.Kang and OP: On a question of Vera T. Sos about size forcing of graphons, 22pp
- JG and Vasek Rozhon: Local Problems on Grids from the Perspective of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics (previous, now irrelevant, title: Of Toasts and Tails), 48pp
- JG and V.Rozhon: Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics, extended abstract accepted at EUROCOMB2021, 34pp
- OP and K.Staden Stability for the Erdos-Rothschild problem, 50pp
- OP and K.Staden Exact solutions for the Erdos-Rothschild problem, 53pp
- S. Brandt, Y. Chang, JG, C. Grunau, V. Rozhoň, Z. Vidnyánszky Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics, accepted at ITCS, 72pp
- I.Gil Fernandez, J.Kim, H.Liu, OP New lower bounds on kissing numbers and spherical codes in high dimensions, 20pp
- S. Brandt, Y. Chang, JG, C. Grunau, V. Rozhoň, Z. Vidnyánszky On Homomorphism Graphs, 21pp
- V.Falgas-Ravry, OP, E.Vaughan, J.Volec The codegree threshold of K4-, 31 pages
- A.Mathe, J.Noel, OP Circle Squaring with Pieces of Small Boundary and Low Borel Complexity, 49 pages
- E.Csoka, L.Grabowski, A.Mathe, OP, K.Tyros Moser-Tardos Algorithm with small number of random bits, 31pp.
- JG, R. Greenfeld, V. Rozhoň, T. Tao Measurable tilings by abelian group actions, 25pp.
- S. Brandt, Y. Chang, JG, C. Grunau, V. Rozhoň, Z. Vidnyánszky Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees, 47pp.
- I.Gil Fernandez, J.Hyde, H.Liu OP, Z.Wu Disjoint isomorphic balanced clique subdivisions, 17pp.

## Talks Given/Forthcoming

2019

- 11 Oct: OP, Workshop "Measurable, Borel, and Topological Dynamics", CIRM
- 4 Nov: OP, Workshop "Structure, Sparsity and Randomness", Radbound University, Nijmegen
- 6 Nov: OP, Old Codger's One-Day Combinatorics Colloquium, Reading
- 21 Nov: OP, 3in1 Workshop on Graph Theory, Doslonce, Poland
- 18 Dec: JG, Seminar on Reckoning, Institute of Mathematics of the Czech Academy of Sciences, Prague
- 20 Dec: JG, Combinatorial group seminar, Institute of Computer Science of the Czech Academy of Sciences, Prague

2020

- 7 Jan: JG, DIMAP seminar, Warwick University
- 14 Jan: OP, Warwick Maths Society
- 30 Jan: OP, ACO Seminar, Carnegie Mellon University
- 11 Feb: OP, seminar, Adam Mickiewicz University, Poznan
- 11 Feb: JG, STUK5 mini-talk, Royal Society building, London
- 17 Feb: OP, Krakow Combinatorics Seminar
- 11 Mar: JG, Algebra and Geometry Seminar, Lancaster University
- 20 May: JG, Caltech logic (online) seminar, Caltech
- 27 Jul: OP, Extremal and Probabilistic Combinatorics Webinar
- 4 & 7 Aug: JG, Midsummer Combinatorial Workshop XXIV, Charles University, Prague
- 21 Oct: JG, Probability seminar (online), UBC
- 10 Nov: OP, UIUC Graph Theory and Combinatorics Seminar
- 23 Nov: JG, Extremal and Probabilistic Combinatorics Webinar
- 27 Nov: OP, TU Graz Combinatorics and Optimization Seminar
- 18 Dec: OP, Combinatorics Seminar of Shandong University

2021

- 11 Jan: OP, Combinatorics Seminar, Hebrew University of Jerusalem
- 22 Feb: OP, Caltech Logic Seminar
- 10 March: JG, UBC probability seminar
- 1 June: JG, Florida Logic seminar
- 21 Jun: OP, Colloquium Discrete Mathematics and Probability, TU-Graz
- 23 Jun: OP, Mini-symposium on Extremal and Probabilistic Combinatorics, 8th European Congress of Mathematics
- 5-9 Jul: OP, the Richard Rado Lecture at the 28th British Combinatorial Conference
- 6-10 Sep: JG, EUROCOMB 2021
- 11 Oct: JG, DIMAP seminar, Warwick University
- 8 Nov: JG, Descriptive Dynamics and Combinatorics Seminar, McGill University
- 30 Nov: OP, Warwick Maths Society

2022

- 12 Jan: JG, Combinatorial group seminar, Institute of Computer Science of the Czech Academy of Sciences, Prague
- 7-11 Feb: OP, Workhop "Logic and Random Discrete Structures", Dagstuhl
- 3 Mar: JG, Algorithms Seminar, Oxford
- 4-6 Apr: OP, IBS ECOPRO Opening Conference, Daejeon, Korea
- 16-20 May: OP, Workshop "Graphs, Groups, Stochastic Processes", Budapest
- 27 Jun - 1 Jul: OP, Third Southwestern German Workshop on Graph Theory, Heildelberg
- 8-12 Aug: OP, Combinatorics Workshop, Ascona