Skip to main content Skip to navigation

Mathematics Institute

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", currently supported by 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

* = co-advised PhD student

News

  • 15 Nov'24: Irene Gil Fernandez successfully defends her PhD thesis "Finding constrained sparse subgraphs via sublinear expansion". Congratulations, Irene!
  • Oct-Nov'24: OP serves on the mathematics panel of the MSCA4Ukraine2 programme
  • 7 Oct'24: Levente Bodnar successfully defends his PhD thesis "Low-Depth Circuit Size Bounds Using Combinatorial Methods". Congratulations, Levente!
  • 24 Sep'24: OP serves as an extermal examiner at Aranka Hruskova's PhD defense that was successfully defended. Congratulations, Aranka!
  • Jan-Jun'24: JG, Alexander Kechris, OP, Stevo Todorcevic, and Zoltán Vidnyánszky organise Semester "Measurable Combinatorics", Erdos Center, Budapest, including
  • 19 Jun'24: LB gives a mini-course on his flag algebras package
  • 27 Jan - 3 Feb, 2024 JG is a co-organizing Winter School in Abstract Analysis 2024
  • 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
  • Feb-Mar'23: OP serves on the Program Committee of Digital Theme UK-Ukraine Research Twinning Conference
  • 28 Jan - 3 Feb, 2023 JG is a co-organizing Winter School in Abstract Analysis 2023
  • Jan'23-May'24: OP teaches at the weekly Math Challenge Club at St Augustine's Catholic Primary School, Kenilworth
  • 26-27 Jan'23: OP serves on the Mathematics Review Panel of the Academy of Finland
  • 18 Jan'23: Matteo Mazzamurro successfully defends his PhD thesis "Structure, Entropy and Evolution of Systems of Cities". Congratulations, Matteo!
  • Dec'22-Feb'23: OP serves on the Selection Committee of the MSCA4Ukraine programme
  • Dec'22: Discovery magazine publishes an article about group's work on circle squaring
  • Oct'22: JG wins the 2022 Mary Ellen Rudin Young Researcher Award. Congratulations, Jan!
  • 14 Jun'22: JH organises Birmingham-Warwick One-Day Combinatorics Meeting
  • Jun-Jul'22: OP serves on the hiring panel for the Professor Post in Discrete Maths and Computer Science at Warwick
  • May'22- : OP serves on the committee of INI's programme "Solidarity for mathematicians: refugees of war"
  • 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 group's work on circle squaring
  • 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
  • 29 Jan - 5 Feb, 2022 JG is a co-organizing Winter School in Abstract Analysis 2022
  • Jan'22: Some results co-authored by grouthere isp 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 (see also Warwick News, Ukraine Network)
  • Dec'20-Aug'21: OP serves at 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!
  • 25 Jan - 1 Feb, 2020 JG is a co-organizing Winter School in Abstract Analysis 2020
  • 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.

  1. L.Grabowski, A.Mathe, OP: Measurable equidecompositions for group actions with an expansion property, Journal of Eur Math Soc 24 (2022) 4277-4326.
  2. 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
  3. 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.
  4. M.Kang, T.Makai and OP: Supersaturation Problem for the Bowtie, European J Comb 88 (2020) 103107.
  5. JG and OP: Measurable versions of Vizing's theorem, Advances in Mathematics, 374 (2020) paper 107378, 40pp
  6. J.Kim, H.Liu, OP and M.Sharifzadeh: Asymptotic Structure for the Clique Density Theorem, Discrete Analysis (2020) Paper 19, 26pp
  7. 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
  8. C.T.Conley, JG and OP: Divisibility of Spheres with Measurable Pieces, L'Enseignement Mathematique, 70 (2024) 25-59
  9. H.Liu, OP, M.Sharifzadeh and K.Staden: Stability from graph symmetrisation arguments with applications to inducibility, accepted by J London Math Soc, 41 pages
  10. JG and I. Rocha: Fractional Isomorphism of Graphons, Combinatorica, 42 (2022) 365–404
  11. JG: Approximate Schreier decorations and approximate Konig line coloring theorem, Annales Henri Lebesgue, 5 (2022) 303-315.
  12. JG and Z. Vidnyánszky: Tall Fσ subideals of tall analytic ideals, accepted to PAMS, 5pp
  13. JG and OP: Large Deviation Principles for Block and Step Graphon Random Graph Models, 17pp
  14. O.Cooley, M.Kang and OP: On a question of Vera T. Sos about size forcing of graphons, Acta Mathematica Hungarica 168 (2022) 1-26
  15. JG and Vasek Rozhon: Local Problems on Grids from the Perspective of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics, 48pp
  16. JG and V.Rozhon: Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics, extended abstract accepted at EUROCOMB2021, 34pp
  17. OP and K.Staden Stability for the Erdos-Rothschild problem, Forum of Math, Sigma 11 (2023) Paper e23, 43 pages
  18. OP and K.Staden Exact solutions for the Erdos-Rothschild problem, Forum of Math Sigma, 12 (2024) Paper e8, 45 pages
  19. 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, 13th Innovations in Theoretical Computer Science Conference, Art. No. 29, 26 pp., LIPIcs. Leibniz Int. Proc. Inform., 215, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022.
  20. IGF, J.Kim, H.Liu, OP New lower bounds on kissing numbers and spherical codes in high dimensions, 20pp
  21. S. Brandt, Y. Chang, JG, C. Grunau, V. Rozhoň, Z. Vidnyánszky On Homomorphism Graphs, 21pp
  22. V.Falgas-Ravry, OP, E.Vaughan, J.Volec The codegree threshold of K4-, J London Math Soc 107 (2023) 1660-1691
  23. A.Mathe, J.Noel, OP Circle Squaring with Pieces of Small Boundary and Low Borel Complexity, 49 pages
  24. E.Csoka, L.Grabowski, A.Mathe, OP, K.Tyros Moser-Tardos Algorithm with small number of random bits, 31pp.
  25. JG, R. Greenfeld, V. Rozhoň, T. Tao Measurable tilings by abelian group actions, accepted by IMRN, 25pp.
  26. S. Brandt, Y. Chang, JG, C. Grunau, V. Rozhoň, Z. Vidnyánszky Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees, 47pp.
  27. IGF, JH, H.Liu OP, ZW Disjoint isomorphic balanced clique subdivisions, J Comb Th (B) 161 (2023) 417-436
  28. J. Hou, H. Li, XL, D. Mubayi, Y. Zhang Hypergraphs with infinitely many extremal constructionsLink opens in a new window, Discrete Analysis 2023:18, 34 pp
  29. XL, S. Mukherjee Tight query complexity bounds for learning graph partitionsLink opens in a new window, 35th Annual Conference of Learning Theory (COLT), 2022, 12pp
  30. JH Towards the 0-statement of the Kohayakawa-Kreuter conjecture, Combinatorics, Probability and Computing 23 (2023) 225–268
  31. XL and OP Hypergraph Turan densities can have arbitrarily large algebraic degree, J Comb Th (B) 161 (2023) 407-416
  32. S.Cambie, Y.Dong and MM Extremal values of degree-based entropies of bipartite graphs, 13pp
  33. S.Cambie and MM Resolution of Yan's conjecture on entropy of graphs, accepted by MATCH, 9pp
  34. S.Cambie and MM Extremal entropy for graphs with given size, 8pp.
  35. IGF and H.Liu How to build a pillar: a proof of Thomassen's conjecture, 16pp
  36. IGF, J.Kim, Y.Kim, H.Liu Nested cycles with no geometric crossings, to appear in Proceedings of the American Mathematical Society, 10pp
  37. JG, Z. Vidnyánszky Ramsey, expanders, and Borel chromatic numbers, 11pp
  38. S.Glock, F.Joos, J.Kim, M.Kuhn, L.Lichev and OP On the (6,4)-problem of Brown, Erdos and Sos, Proc Amer Math Soc Series B, 11 (2024) 173-186
  39. OP and XL Finite Hypergraph Families with Rich Extremal Turan Constructions via Mixing Patterns, 57pp
  40. ZW Positive co-degree Turan number for C5 and C5- , 8 pages
  41. OP On the limit of the positive l-degree Turan problem, Electronic J Comb 30 (2023) Paper 3.25, 15pp
  42. J. Hou, H. Li, XL, L.-T. Yuan, and Y. Zhang A step towards a general density Corradi–Hajnal TheoremLink opens in a new window, 32pp
  43. A.Grzesik, D.Kral and OP Forcing Generalized Quasirandom Graphs Efficiently, accepted by Combin Prob Comput, 20pp (Extended abstract)
  44. JG Measurable Vizing's theorem, 25pp.
  45. SS Tilings in quasi-random k-partite hypergraphs, 22pp
  46. C.T.Conley, JG and OP Local version of Vizing's theorem for multi-graphs, 9pp
  47. Y. Chen, XL, J. Nie, and J. Zeng, Random Turan and counting results for general position sets over finite fields, 28pp
  48. XL and J. Song, Exact results for some extremal problems on expansions I,Link opens in a new window 33pp+appendix
  49. XL and J. Song, Hypergraph anti-Ramsey theorems,Link opens in a new window 14pp
  50. J. Hou, C. Hu, H. Li, XL, C. Yang, and Y. Zhang, Toward a density Corradi-Hajnal theorem for degenerate hypergraphs, 37pp
  51. J. Hou, C. Hu, H. Li, XL, C. Yang, and Y. Zhang, Many vertex-disjoint even cycles of fixed length in a graph, 12pp
  52. XL and OP, A note on extremal constructions for the Erdos-Rademacher problem, 13pp
  53. JG and OP, Large deviation principles for graphon sampling, 42pp.
  54. J. Hou, XL, and H. Zhao Faster coloring and embedding in dense hypergraphs via stabilityLink opens in a new window, 21pp.
  55. C. Helliar and XL A generalized Turan extension of the Deza-Erdos-Frankl Theorem, 12pp.
  56. J.Yan and XW, Distribution of colours in rainbow H-free colourings, 15pp
  57. Jun Gao, ZW, Yisai Xue, Counting cliques without generalized theta graphs, 15pp
  58. IGF, J.Kim, H.Liu and OP, New lower bound on ball packing density in high-dimensional hyperbolic spaces, 18pp.
  59. S.Glock, J.Kim, L.Lichev, OP and SS, On the (k+2,k)-problem of Brown, Erdos and Sos for k=5,6,7, 44pp
  60. IGF, J.Kim, H.Liu and OP, New lower bound on ball packing density in high-dimensional hyperbolic spaces, 18pp
  61. OP, Constructions of Turan systems that are tight up to a multiplicative constant, 10pp
  62. WC, D.Ilkovic, JL, OP, XL Nondegenerate Turan problems under (t,p)-norms, 46pp.
  63. ZW, Positive co-degree Tur\'an number for C5 and
  64. ZW and J.Yan, Distribution of colours in rainbow H-free colourings, 15pp
  65. J.Gao, ZW, Y.Xue, Counting cliques without generalized theta graphs, 15pp
  66. A.Lamainson and ZW, The Uniform Tur\'an density of stars, 10pp
  67. T-W.Chao, Z.Dong and ZW, Empty red-red-blue triangles, 9pp
  68. D.Bradac, H.Liu, ZW and Z.Xu, Clique density vs blowups, 22pp
  69. W. Chen, XL, Strong stability from vertex-extendability and applications in generalized Turan problemsLink opens in a new window, 30pp.
  70. J. Deng, J. Hou, XL, and C. Yang, Tight bounds for rainbow partial F-tiling in edge-colored complete hypergraphsLink opens in a new window, 19pp.
  71. J. Hou, C. Hu, H. Li,, XL, C. Yang, and Y. Zhang, On the boundedness of degenerate hypergraphsLink opens in a new window, 19pp.
  72. XL, J. Ma, T. Wang, and T. Zhu, Uniquely colorable hypergraphsLink opens in a new window, 29pp.
  73. Z. Chen, J. Hou, C. Hu, and XL, Generalized Andrasfai-Erdos-Sos theorems for odd cyclesLink opens in a new window, 7pp.
  74. XL, S. Ren and J. Wang, Andrasfai-Erdos-Sos theorem for the generalized triangleLink opens in a new window, 22pp.
  75. XL, S. Ren and J. Wang, Positive codegree Andrasfai-Erdos-Sos theorem for the generalized triangleLink opens in a new window, 9pp.

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 Mar: JG, UBC probability seminar
  • 5 May: IGF, LIMDA Seminar, Universitat Politècnica de Catalunya, Spain
  • 19 May: IGF, Warwick Postgraduate Seminar
  • 1 Jun: JG, Florida Logic seminar
  • 7 Jun: IGF, (Online) Young Researchers in Mathematics Conference, UK
  • 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
  • 26 Jul: IGF, Summer school "Matemáticas: mucho más que números", Universidad de Santiago de Compostela, Spain
  • 6-10 Sep: JG, EUROCOMB 2021, Barcelona
  • 7 Sep: IGF, EUROCOMB 2021, Barcelona
  • 11 Oct: JG, DIMAP seminar, Warwick University
  • 14 Oct: IGF, Discrete Seminar, Umeå University, Sweden
  • 26 Oct: IGF, First Workshop on Developments in Combinatorics, Shandong University, China
  • 8 Nov: JG, Descriptive Dynamics and Combinatorics Seminar, McGill University
  • 12 Nov: IGF, PhD Seminar on Combinatorics, Games and Optimisation, London School of Economics
  • 30 Nov: OP, Warwick Maths Society

2022

2023

2024

2025

Research visitors

  • 9-12 November 2021: Łukasz Grabowski (Lancaster University)
  • 10-12 May 2022: Péter Pál Pach (Budapest University of Technology and Economics)
  • 16-22 October 2022: Dan Kral' (Masaryk University)
  • 16-22 October 2022: Daniel Ilkovic (Masaryk University)
  • 15-20 January 2023: Jan Volec (Technical University Prague)
  • 4-18 February 2023: Clinton Conley (Carnegie Mellon University)
  • 18-21 February 2023: Mihyun Kang (TU-Graz)
  • 13-26 April 2024: Jun Gao (IBS Korea)
  • 9-23 September 2024: Dorde Stefanovic (Ljubljana)