Skip to main content

Extremal Combinatorics

This is the webpage of the ERC Starting Grant No. 306493 "Extremal Combinatorics" (http://warwick.ac.uk/go/extrcomb).

Overview

A typical problem of extremal combinatorics is to maximise or minimise a certain parameter given some combinatorial restrictions. The project will concentrate on problems of this type, with the main directions being the Turan function (maximising the size of a hypergraph without some fixed forbidden subgraphs), the Rademacher–Turan problem (minimising the density of F-subgraphs given the edge density), and Ramsey numbers (quantitative bounds on the maximum size of a monochromatic substructure that exists for every colouring). These are fundamental and general questions that go back at least as far as the 1940s, many of which remain wide open despite decades of active attempts. During attacks on these notoriously difficult problems, mathematicians developed a number of powerful general methods. The project team will work on extending and sharpening these techniques as well as on finding ways of applying the recently introduced concepts of (hyper)graph limits and flag algebras to concrete extremal problems. Since these concepts deal with some approximation to the studied problem, one important aspect of the project is to develop methods for obtaining exact results from asymptotic calculations (for example, via the stability approach).

Current and Past Group Members

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. D.Kral' and OP: Quasirandom Permutations Are Characterized by 4-Point Densities, Geometric Funct Analysis, 23 (2013) 570-579.
  2. OP: On Possible Turan Densities, Israel J Math, 201 (2014) 415-454.
  3. J.Hladky, A.Mathe, V.Patel and OP: Poset limits can be totally ordered, Trans Amer Math Soc, 367 (2015) 4319-4337.
  4. OP and E.R.Vaughan: Minimum Number of k-Cliques in Graphs with Bounded Independence Number, Combin Prob Comput, 22 (2013) 910-934.
  5. C.G.Heise, K.Panagiotou OP and A.Taraz, Coloring d-Embeddable k-Uniform Hypergraphs, Discr Comput Geometry 52 (2014) 663-679.
  6. Tao Jia, Yang-Yu Liu, E Cs, Márton Pósfai, Jean-Jacques Slotine, Albert-László Barabási: Emergence of Bimodality in Controlling Complex Networks, Nature communications 4 (2013)
  7. KT, On colorings of variable words, Discrete Math, 338 (2015) 1025-1028.
  8. B. Sari, KT, On the structure of the set of higher order spreading models, Studia Mathematica, 223 (2014) 149–173.
  9. ŁG, Vanishing of l2-cohomology as a computational problem, Bull. Lond. Math. Soc. 47(2):233-247, 2015.
  10. J.Balogh, P.Hu, B.Lidicky, OP, B.Udvari, J.Volec, Minimum number of monotone subsequences of length 4 in permutations, Combin Prob Comput, 24 (2015) 658-679.
  11. ŁG, Group ring elements with large spectral density, Math. Ann., October 2015, Volume 363, Issue 1, pp 637-656
  12. ŁG, Irrational l2-invariants arising from the lamplighter group, to appear in Groups Geom. Dyn.
  13. ECs, B Gerencsér, V Harangi, B Virág: Invariant Gaussian processes and independent sets on regular graphs of large girth, Random Structures and Algorithms, doi: 10.1002/rsa.20547, 2014
  14. H.Liu, OP, T.Sousa, Monochromatic Clique Decompositions of Graphs, J Graph th, 80 (2015) 287-298.
  15. KT, Primitive recursive bounds for the finite version of Gowers' c0 theorem, Mathematika, to appear, 22pp.
  16. V.Falgas-Ravry, E.Marchant, OP and E.Vaughan, The codegree threshold for 3-graphs with independent neighbourhoods,SIAM J Discr Math, 23 (2015) 1504-1539 .
  17. H.Naves, OP, A.Scott: How unproportional must a graph be?, submitted, arXiv:1404.1206, 14pp
  18. ECs, G.Lippner and OP: Kőnig's Line Coloring and Vizing's Theorems for Graphings, Forum of Mathematics, Sigma, 4 (2016) 40pp.
  19. OP, A.Razborov, Asymptotic Structure of Graphs with the Minimum Number of Triangles, Combin Prob Comput, 26 (2017) 138-160.
  20. OP, Z.Yilma: Supersaturation Problem for Color-Critical Graphs, J Comb Th (B), 123 (2017) 148-185.
  21. E.DeCorte, OP: Spherical sets avoiding a prescribed set of angles, to appear in International Math Research Notices, 2016 (2016) 6095-6117.
  22. OP, The maximal length of a gap between r-graph Turan densities, Electr J Combin, 22 (2015) 7pp.
  23. G. Glauberman, ŁG, Groups with Identical k-Profiles, Theory of Computing, Volume 11 (2015), pp. 395-401.
  24. ECs: On the graph limit question of Vera T. Sós, J Comb Th (B) 116 (2016) 306-311.
  25. ECs, Szabolcs Mészáros: Generalized solution for the Herman Protocol Conjecture, submitted, arXiv:1504.06963, 13pp.
  26. ECs: Limits of some combinatorial problems, Electronic Notes in Discrete Mathematics, 49 (2015) 577–581.
  27. P.Dodos, V.Kanellopoulos and KT: A concentration inequality for product spaces, J Func Anal 270 (2016) 609–620
  28. ECs, I.Lo, S.Norin, H.Wu, L.Yepremyan: The extremal function for disconnected minors, arXiv:1509.01185, to appear in JCTB
  29. ECs, T.Lidbetter: The solution to an open problem for a caching game, Naval Research Logistics, 63 (2016) 23-31, arXiv:1507.08425
  30. LG, A.Mathe, OP: Measurable circle squaring, Annals of Mathematics, 185 (2017) 671-710.
  31. LG, A.Mathe, OP: Measurable equidecompositions for group actions with an expansion property, arXiv:1601.02958
  32. ECs: Independent sets and cuts in large-girth regular graphs, arxiv:1602.02747
  33. ECs, LG, A.Mathe, OP, KT: Borel version of the Local Lemma, arXiv:1605.04877
  34. HL, R.Montgomery: A proof of Mader's conjecture on large clique subdivisions in C_4-free graphs, J. Lond. Math. Soc., 95 (2017) 203–222.
  35. OP, KS, Z.Yilma: The Erdős-Rothschild problem on edge-colourings with forbidden monochromatic cliques, arXiv:1605.05074, to appear in Math. Proc Cambridge Phil. Soc., 16pp.
  36. J.Balogh, HL, M.Sharifzadeh: On two problems in Ramsey-Turán theory, arXiv:1607.06393
  37. MF, Rational exponents for hypergraph Turan problems, arXiv:1607.05788
  38. A.Geogakopoulos, KT, The Bradley-Terry condition is L1-testable, arXiv:1609.05194
  39. HL, MSh, KS, Local conditions for exponentially many subdivisions, to appear in Combin. Prob. Comput., 8pp.
  40. KS, A.Treglown, On degree sequences forcing the square of a Hamilton cycle, to appear in SIAM J. Discrete Math., 50pp.
  41. R.Hancock, KS, A.Treglown, Independent sets in hypergraphs and Ramsey properties of graphs and the integers, arXiv:1701.04754
  42. J.Kim, HL, MSh, KS, Proof of Koml\'os's conjecture on Hamiltonian subsets, Proc. London Math. Soc (2017), arXiv:1701.06784
  43. HL, OP, MSh: Edges not in any monochromatic copy of a fixed graph, arXiv:1705.01997
  44. HL, MSh, KS, On the maximum number of integer colourings with forbidden monochromatic sums, arXiv:1709.09589
  45. OC, OP, KS, Minimum number of additive tuples in groups of prime order, arXiv:1710.01936

Talks Given

  • 20 Nov 2012: OP, Seminar, Royal Holloway
  • 17 Dec 2012: OP, Seminar, L'viv State University, Ukraine
  • 25 Feb 2013: ECs, Large Networks Seminar, Eötvös University, Budapest, Hungary
  • 26 Feb 2013: OP, Combinatorial Theory Seminar, Oxford
  • 28 Feb 2013: OP, Combinatorics Seminar, Bristol
  • 1 Apr 2013: OP, Study group "Limits of Discrete Structures", Oberwolfach
  • 2 Apr 2013: ECs, Study group "Limits of Discrete Structures", Oberwolfach
  • 13 May 2013: ECs, Graphs, Groups Research Group Seminar, MTA Rényi Institute, Budapest, Hungary
  • 16 May 2013: ECs, Large Networks Seminar, Eötvös University, Budapest, Hungary
  • 30 May 2013: OP, Seminar on Discrete Mathematics and Game Theory, LSE
  • 2 Jul 2013: OP, Erdős Centennial Conference, Budapest
  • 18 Jul 2013: OP, seminar, TU-Munich
  • 8 Aug 2013: OP, Plenary talk, Conference "Random Structures and Algorithms", Poznan
  • 10 Sep 2013: OP, Plenary talk, Workshop "Cycles and Colourings 2013", Novy Smokovec
  • 11 Sep 2013: ECs, Eurocomb, Pisa
  • 10 Jan 2014: OP, Workshop "Probability and Graphs", Eurandom, Eindhoven
  • 16 Jan 2014: OP, Seminar, Mittag-Leffler Institute, Stockholm
  • 17 Jan 2014, ŁG, Topology Seminar, Edinburgh
  • 29 Jan 2014: OP, Seminar, KTH, Stockholm
  • 10 Mar 2014: ECs, Graphs, Groups Research Group Seminar, MTA Rényi Institute, Budapest, Hungary
  • 12 Mar 2014: ECs, Large Networks Seminar, Eötvös University, Budapest, Hungary
  • 12 Mar 2014: ŁG, Random walks seminar during the program Marches Aléatoires et Géométrie Asymptotique des Groupes, Paris
  • 17 Mar 2014: ECs, Discrete Mathematics Workshop, Queen Mary University of London
  • 8 Apr 2014: OP, British Mathemaical Colloquim, Queen Mary University of London
  • 24 Apr 2014: ECs, Combinatorics Seminar, Rényi Alfréd Institute of Mathematics, Hungarian Academy of Sciences
  • 12 May 2014: ŁG, Analysis Seminar, Bristol
  • 29 May 2014: OP, Combinatorics seminar, Bristol
  • 4 Jun 2014: OP, CMI Worskhop "Extremal and Probabilistic Combinatorics", Oxford
  • 29 Jun 2014: OP, Workshop "Graph limits, groups and stochastic processes", Budapest
  • 9 July 2014: ECs, Summit240 Conference, Budapest
  • 17 July 2014: ECs, Extremal combinatorics workshop, Edinburgh
  • 29 July 2014: ECs, Midsummer Combinatorial Workshop XX, Prague
  • 1 Aug 2014: OP, Midsummer Combinatorial Workshop XX, Prague
  • 11 Sep 2014: ECs, BarabásiLab Seminar, Northeastern University, Boston
  • 12 Sep 2014: ECs, Channing Network Science Seminar, Northeastern University, Boston
  • 12 Sep 2014: KT, Set Theory Seminar, University of Toronto
  • 18 Sep 2014: OP, Seminar, IMA, Minneapolis
  • 19 Sep 2014: KT, Tutte Seminar, University of Waterloo
  • 22 Sep 2014: ECs, Graphs and Groups Seminar, Rényi Institute, Budapest
  • 25 Sep 2014: OP, ACO Seminar, CMU, Pittsburgh
  • 11 Nov 2014: ŁG, Algebra Seminar, Oxford
  • 14 Nov 2014: KT, Combinatorics seminar, University of Warwick
  • 21 Nov 2014: ŁG, Pure Mathematics Colloquium, Southampton
  • 21 Nov 2014: OP, Combinatorics Seminar, Queen Mary University of London
  • 21 Jan 2015: ŁG, Oberwolfach "Geometric Topology"
  • 27 Jan 2015: OP, Analysis Seminar, Institute for Math, Czech Academy of Sciences
  • 11 Feb 2015: OP, Workshop "Crystals, Quasicrystals and Random Networks", ICERM, Providence, RI
  • 18 Feb 2015: ECs, Stochastic Processes Seminar, University College London
  • 27 Feb 2015: KS, Combinatorics Seminar, University of Warwick
  • 19 Mar 2015: OP, Seminar, University of Birmingham
  • 19 Mar 2015: KS, Combinatorics Seminar, Bristol
  • 23 Mar 2015: OP, Workshop on Homomorphisms and Graph Limits III, Hranicny Zamecek
  • 24 Mar 2015: ECs, Workshop on Homomorphisms and Graph Limits III, Hranicny Zamecek
  • 2 Apr 2015: KT, Forcing and its Applications Retrospective Workshop, Fields Institute
  • 13 Apr 2015: JS, Post-graduate Combinatorial Conference, Queen Mary, London
  • 28 Apr 2015: OP, Colloquium, Iowa State University, Ames
  • 12 May 2015: OP, Combinatorial Theory Seminar, Oxford
  • 15 May 2015: ŁG, Grous and Geometry in the South East, Oxford
  • 27 May 2015: OP, Seminar, TU-Delft
  • 5 June 2015: ECs, Combinatorics Seminar, University of Warwick
  • 6 Jul 2015: JS, British Combinatorial Conference, University of Warwick
  • 6 July 2015: KS, British Combinatorial Conference, University of Warwick
  • 7 July 2015: ECs, British Combinatorial Conference, University of Warwick
  • July 2015: ŁG, British Combinatorial Conference, University of Warwick
  • 31 July 2015: ECs, Midsummer Combinatorial Workshop XXI, Prague
  • 27 Aug 2015: OP, Workshop "Methods and Challenges in Extremal and Probabilistic Combinatorics", Banff
  • 1 Sep 2015: ECs, EuroComb, Bergen, Norway
  • 4 Sep 2015: ECs, EuroComb, Bergen, Norway
  • 4 Sep 2015: KS, EuroComb, Bergen, Norway
  • 20 Sep 2015: ECs, LMS/EMS Joint Anniversary Mathematical Weekend, Birmingham
  • 21 Sep 2015: OP, Workshop "Probabilistic and Extremal Combinatorics", Birmingham
  • 20 Oct 2015: OP, talk at Warwick Maths Society
  • 26 Nov 2015, ŁG, London Algebra Colloquium, Queen Mary University of London
  • 3 Dec 2015: OP, seminar, Cambridge University
  • 5 Feb 2016: HL, seminar, U of Warwick
  • 23 Mar 2016: KS, speed talk, British Mathematical Colloquium, Bristol
  • 23 Mar 2016: HL, British Mathematical Colloquium, Bristol
  • 24 Mar 2016: OP, Discrete Math Seminar, LSE
  • 20 Apr 2016: KS, Young Mathematicians' Colloquium, Birmingham
  • 25 Apr 2016: HL, seminar, Czech Academy of Sciences, Prague
  • 4 May 2016: KS, seminar, Freie Universität, Berlin
  • 9 May 2016: OP, BMS seminar, Berlin
  • 24 May 2016: OP, Workshop "Probabilistic and Extremal Combinatorics", ETH Zurich
  • 22, 28 June 2016: HL, seminar, IPM, Tehran
  • 7 July 2016: HL, Bristol-Oxford Additive Combinatorics meeting, Oxford
  • 8 Aug 2016: OP, Conference "Extremal Combinatorics at Illinois 3", Chicago
  • 30 Aug 2016: OP, Workshop "Measured Group Theory", Oberwolfach, Germany
  • 5 Sep 2016: OP, Topology Seminar, Lviv State University
  • 8 Sep 2016: OP, Topological Algebra Seminar, Lviv State University
  • 22 Sep 2016: MF, 6th Polish Combinatorial Conference, Bedlewo
  • 29 Sep 2016: OP, Conference dedicated to the 120-th anniversary of Kazimierz Kuratowski, Lviv
  • 11 Oct 2016: OP, Seminar, TU-Graz
  • 4 Nov 2016: KS, Seminar, University of Warwick
  • 21 Nov: OP, Future Directions in Network Mathematics, Newton Institute Satellite Workshop, London
  • 25 Nov: OP, DIAMANT Symposium, Netherlands
  • 28 Dec 2016: MSh, Winter Seminar Series, Sharif University of Technology, Iran
  • 31 Jan 2017: KS, Pure and Applied Mathematics Colloquium, Open University, Milton Keynes
  • 16 Mar 2017: MSh, Seminar, University of Birmigham
  • 23 Mar 2017: MSh, Seminar, LSE
  • 23 Mar 2017: OP, Workshop "Analytic combinatorics", Zamecek, Czech Republic
  • 19 Apr 2017: OP, Seminar, Goethe University, Frankfurt
  • 20 Apr 2017: OP, Colloquium, University of Muenster
  • 18 May 2017: KS, Seminar, University of Cambridge
  • 19 June 2017: OP, Seminar, Lancaster University
  • 30 June 2017: OP, Workshop "Interactions with Combinatorics", Birmingham
  • 13 July 2017: OP, Foundations of Computational Mathematics FoCM 2017, Barcelona
  • 11 July 2017: MSh, Frontiers in Mathematical Sciences conference, Tehran, Iran
  • 17 July 2017: KS, Workshop NSFOCS, Novi Sad, Serbia
  • 20 July 2017: OP, Workshop NSFOCS, Novi Sad, Serbia
  • 26 Sep 2017: OP, seminar, TU-Graz
  • 5 Oct 2017: OP, colloquium, University of Innsbruck

Flagmatic

Flagmatic is a package originally developed by Emil Vaughan to automatically prove asymptotic estimates for a wide range of extremal problems for graphs, directed graphs and 3-uniform hypergraphs, using the flag algebra SDP approach of Razborov. Some extra functionality has been added by group's member Jakub Sliacan. Namely, one can now specify "rooted" assumptions (such as, for example, that every vertex has degree at least d or the number of triangles per each edge is at most t, etc).

This is still under development. The latest version can be downloaded from: https://github.com/jsliacan/flagmatic-dev. Associated user's guide is located in the flagmatic-dev/doc folder or linked here: Flagmatic-dev User's Guide. The documentation will be updated as features are added. Flagmatic has been tested on Sage-6.4 and you can have the source from SageMath website. Flagmatic installation instructions (once you have Sage 6.4) are in the User's Guide or the README file.

There is still the option of running Emil Vaughan's original Flagmatic-2.0. It has been modified to reflect the changes in Sage but no changes were made to the functionality. You can have it from: https://github.com/jsliacan/flagmatic-2.0. Follow the installation instructions in the README file or Flagmatic-dev User's Guide linked above (with appropriate changes).

Some News

  • 2012/3: OP and J.Stacho organise Warwick's Combinatorics Seminar
  • Jan 2013: OP becomes a member of the Editorial Board of "Discrete Mathematics"
  • Jan-Mar 2013: OP organises "Problem-solving seminar for undergraduates" (Warwick's team comes 37th in 2013 IMC)
  • Feb 2013: ECs successfully defends his PhD thesis "Sampling and local algorithms in large graphs". Congratulations!!!
  • Mar 2013: OP becomes an editor of "Mathematical Proceedings of Taras Shevchenko Scientific Society"
  • Apr 2013: Toby Allen (supervised by OP) successfully defends his MSc thesis "Applications of entropy in combinatorics". Congratulations!!!
  • Jul-Sep 2013: OP visits TU-Munich as a Humboldt Fellow
  • 2013/4: OP and A.Georgakopoulos organise Warwick's Combinatorics Seminar
  • 15 Oct - 3 Dec 2013: OP lectures a TCC course "Graph Limits"
  • Jan-Mar 2014: Tomasz Tkocz and OP organise "Problem-solving seminar for undergraduates" (Warwick's team comes 39th in 2014 IMC)
  • 5-9 May 2014: A.Coja-Oghlan, M.Jerrum, OP and G.Sorkin organise workshop "Phase transitions in discrete structures and computational problems", University of Warwick
  • 7-10 Jul 2014: E.Cancellero, D.Falik, A.Liebenau, V.Patel and JS organise QMUL-Warwick Alliance open problems workshop in combinatorics and graph theory, Cotswolds
  • 14-18 Jul 2014: P.Keevash, D.Kral' and OP organise ICMS Workshop on Extremal Combinatorics, Edinburgh
  • 2014/5: OP and A.Georgakopoulos organise Warwick's Combinatorics Seminar
  • Jan-Mar 2014: Tomasz Tkocz, Rosemberg Toala, Myhaylo Poplavsky and OP organise "Problem-solving seminar for undergraduates" (with competition taking place in August 2015)
  • 19 Mar 2015: KS successfully defends her PhD thesis ''Robust expansion and Hamiltonicity''. Congratulations!!!
  • 1-5 July 2015: P.Keevash, D.Kral', OP and N.Woodhouse organise Summer School "Regularity and Analytic Methods in Combinatorics", University of Warwick
  • 6-10 July 2015: A.Czumaj, A.Georgakopoulos, D.Kral', V.Lozin and OP are the local organisers of the 25th British Combinatorial Conference, University of Warwick
  • 31 Aug - 4 Sep 2015: R.Kang, T.Muller, J.van Oosten, OP and A.Taraz organise Workshop "Logic and Random Graphs", Lorentz Center at Oort
  • 14-16 Sep 2015: OP and KT organise workshop "Non-Combinatorial Combinatorics", University of Warwick
  • 4-5 Nov 2015: Petter Brändén (KTH Stochholm) gives a mini-course "Combinatorics and geometry of hyperbolic and stable polynomials"
  • Apr 2016: Josh Brown (supervised by KS) and George Witty (supervised by OP) successfully defend their 4-th year projects. Congratulations!
  • 23 Sep 2016: OP gives Tutorial "Measurable Combinatorics" at the 6th Polish Comb Conference, Bedlewo
  • 27 Sep - 1 Oct 2016: OP is on the Scientific Committee of Conference dedicated to the 120-th anniversary of Kazimierz Kuratowski, Lviv
  • May 2017: Henry Dai (supervised by KS), Asher Ehlers and Arun Krishnamoorthy (supervised by OP) successfully defend their 4-th year projects. Congratulations!
  • 9 June 2017: OP & KS organise "One Day Birmingham-Warwick Combinatorics Meeting"
  • 18-22 Sep 2017: OP & KS organise conference "Extremal Combinatorics"
  • 8-9 Nov 2017: Christian Reiher (Hamburg) gives a mini-course "Clique densities"

Visitors

  • 5-9 Nov 2012: Matthew Yancey (UIUC)
  • 20-24 Nov 2012: Oleg Verbitsky (HU-Berlin)
  • 5-8 Feb 2013: Teresa Sousa (New University of Lisbon)
  • 15-25 Nov 2013: Evan DeCorte (TU-Deflt)
  • 23 Feb - 1 Mar 2014: Humberto Naves (ETH Zurich)
  • 12-19 Oct 2014: Felix Lazebnik (U of Delaware)
  • 15-30 Oct 2014: Swiatoslaw Gal (Wroclaw)
  • 23 Nov - 2 Dec 2014: Balazs Udvari (Szeged)
  • 13-22 July 2015: Evan DeCorte (Hebrew U of Jerusalem)
  • 18-29 Jan 2016: Jan Volec (ETH Zurich)
  • 12 Jul - 7 Sep 2016: Maryam Sharifzadeh (UIUC)
  • 9-12 Nov 2016: Alexey Pokrovskiy (ETH Zurich)
  • 17-21 Jan 2017: Mihyun Kang (TU-Graz)
  • 29 Jan - 4 Feb 2017: Tamas Makai (TU-Graz)
  • 2-5 May 2017: Lukasz Grabowski (Lancaster)
  • 16-19 May 2017: Hao Huang (Emory)
  • 29 May - 3 June 2017: Evan DeCorte (McGill)
  • 25-28 June 2017: Mohammad Bardestani (Münster)
  • 7-10 Nov 2017: Christian Reiher (Hamburg)
eu flag

This project has received funding from the European Union’s Seventh Framework Programme for research, technological development and demonstration under grant agreement no 306493.