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 Fsubgraphs 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
 Endre Csoka (Research Fellow, 1 February 2013  30 September 2015)
 Matthew Fitch (PhD student from 1 October 2014)
 Lukasz Grabowski (EPSRCfunded Research Fellow, 1 December 2013  30 April 2016)
 Hong Liu (Research Fellow, 1 February  30 August 2016)

Oleg Pikhurko (PI)
 Maryam Sharifzadeh (Research Fellow, from 13 October 2016)
 Jakub Sliacan (MPhil student, 1 October 2013  30 September 2015)
 Katherine Staden (Research Fellow, 1 February 2015  31 December 2017)
 Konstantinos Tyros (Research Fellow, 1 July 2014  30 August 2016)
Papers
All papers (prepublication versions) should be freely available from arxiv.org. Please contact one of the authors if you have difficulty accessing them.
 D.Kral' and OP: Quasirandom Permutations Are Characterized by 4Point Densities, Geometric Funct Analysis, 23 (2013) 570579.
 OP: On Possible Turan Densities, Israel J Math, 201 (2014) 415454.
 J.Hladky, A.Mathe, V.Patel and OP: Poset limits can be totally ordered, Trans Amer Math Soc, 367 (2015) 43194337.
 OP and E.R.Vaughan: Minimum Number of kCliques in Graphs with Bounded Independence Number, Combin Prob Comput, 22 (2013) 910934.
 C.G.Heise, K.Panagiotou OP and A.Taraz, Coloring dEmbeddable kUniform Hypergraphs, Discr Comput Geometry 52 (2014) 663679.
 Tao Jia, YangYu Liu, E Cs, Márton Pósfai, JeanJacques Slotine, AlbertLászló Barabási: Emergence of Bimodality in Controlling Complex Networks, Nature communications 4 (2013)
 KT, On colorings of variable words, Discrete Math, 338 (2015) 10251028.
 B. Sari, KT, On the structure of the set of higher order spreading models, Studia Mathematica, 223 (2014) 149–173.
 ŁG, Vanishing of l2cohomology as a computational problem, Bull. Lond. Math. Soc. 47(2):233247, 2015.
 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) 658679.
 ŁG, Group ring elements with large spectral density, Math. Ann., October 2015, Volume 363, Issue 1, pp 637656
 ŁG, Irrational l2invariants arising from the lamplighter group, to appear in Groups Geom. Dyn.
 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
 H.Liu, OP, T.Sousa, Monochromatic Clique Decompositions of Graphs, J Graph th, 80 (2015) 287298.
 KT, Primitive recursive bounds for the finite version of Gowers' c0 theorem, Mathematika, to appear, 22pp.
 V.FalgasRavry, E.Marchant, OP and E.Vaughan, The codegree threshold for 3graphs with independent neighbourhoods,SIAM J Discr Math, 23 (2015) 15041539 .
 H.Naves, OP, A.Scott: How unproportional must a graph be?, submitted, arXiv:1404.1206, 14pp
 ECs, G.Lippner and OP: Kőnig's Line Coloring and Vizing's Theorems for Graphings, Forum of Mathematics, Sigma, 4 (2016) 40pp.
 OP, A.Razborov, Asymptotic Structure of Graphs with the Minimum Number of Triangles, Combin Prob Comput, 26 (2017) 138160.
 OP, Z.Yilma: Supersaturation Problem for ColorCritical Graphs, J Comb Th (B), 123 (2017) 148185.
 E.DeCorte, OP: Spherical sets avoiding a prescribed set of angles, to appear in International Math Research Notices, 2016 (2016) 60956117.
 OP, The maximal length of a gap between rgraph Turan densities, Electr J Combin, 22 (2015) 7pp.
 G. Glauberman, ŁG, Groups with Identical kProfiles, Theory of Computing, Volume 11 (2015), pp. 395401.
 ECs: On the graph limit question of Vera T. Sós, J Comb Th (B) 116 (2016) 306311.
 ECs, Szabolcs Mészáros: Generalized solution for the Herman Protocol Conjecture, submitted, arXiv:1504.06963, 13pp.
 ECs: Limits of some combinatorial problems, Electronic Notes in Discrete Mathematics, 49 (2015) 577–581.
 P.Dodos, V.Kanellopoulos and KT: A concentration inequality for product spaces, J Func Anal 270 (2016) 609–620
 ECs, I.Lo, S.Norin, H.Wu, L.Yepremyan: The extremal function for disconnected minors, arXiv:1509.01185, to appear in JCTB
 ECs, T.Lidbetter: The solution to an open problem for a caching game, Naval Research Logistics, 63 (2016) 2331, arXiv:1507.08425
 LG, A.Mathe, OP: Measurable circle squaring, Annals of Mathematics, 185 (2017) 671710.
 LG, A.Mathe, OP: Measurable equidecompositions for group actions with an expansion property, arXiv:1601.02958
 ECs: Independent sets and cuts in largegirth regular graphs, arxiv:1602.02747
 ECs, LG, A.Mathe, OP, KT: Borel version of the Local Lemma, arXiv:1605.04877
 HL, R.Montgomery: A proof of Mader's conjecture on large clique subdivisions in C_4free graphs, J. Lond. Math. Soc., 95 (2017) 203–222.
 OP, KS, Z.Yilma: The ErdősRothschild problem on edgecolourings with forbidden monochromatic cliques, arXiv:1605.05074, to appear in Math. Proc Cambridge Phil. Soc., 16pp.
 J.Balogh, HL, M.Sharifzadeh: On two problems in RamseyTurán theory, arXiv:1607.06393
 MF, Rational exponents for hypergraph Turan problems, arXiv:1607.05788
 A.Geogakopoulos, KT, The BradleyTerry condition is L1testable, arXiv:1609.05194
 HL, MSh, KS, Local conditions for exponentially many subdivisions, to appear in Combin. Prob. Comput., 8pp.
 KS, A.Treglown, On degree sequences forcing the square of a Hamilton cycle, to appear in SIAM J. Discrete Math., 50pp.
 R.Hancock, KS, A.Treglown, Independent sets in hypergraphs and Ramsey properties of graphs and the integers, arXiv:1701.04754
 J.Kim, HL, MSh, KS, Proof of Koml\'os's conjecture on Hamiltonian subsets, Proc. London Math. Soc (2017), arXiv:1701.06784
 HL, OP, MSh: Edges not in any monochromatic copy of a fixed graph, arXiv:1705.01997
 HL, MSh, KS, On the maximum number of integer colourings with forbidden monochromatic sums, arXiv:1709.09589
 OC, OP, KS, Minimum number of additive tuples in groups of prime order, arXiv:1710.01936
 HL, OP, KS, The exact minimum number of triangles in a graph of given order and size, arXiv:1712.00633
 J.Balogh, S.Das, HL, MSh, T.Tran, Structure and Supersaturation for Intersecting Families, arXiv:1802.08018
 MF, Implicit representation conjecture for semialgebraic graphs, arXiv:1803.01882
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, TUMunich
 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, MittagLeffler 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, Postgraduate 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, TUDelft
 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, BristolOxford 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 120th anniversary of Kazimierz Kuratowski, Lviv
 11 Oct 2016: OP, Seminar, TUGraz
 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, TUGraz
 5 Oct 2017: OP, colloquium, University of Innsbruck
 1 Feb 2018: OP, Workshop "Graph Limits", ENS, Lyon
 15 Feb 2018: OP, Combinarorics Seminar, Cambridge
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 3uniform 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/flagmaticdev. Associated user's guide is located in the flagmaticdev/doc folder or linked here: Flagmaticdev User's Guide. The documentation will be updated as features are added. Flagmatic has been tested on Sage6.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 Flagmatic2.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/flagmatic2.0. Follow the installation instructions in the README file or Flagmaticdev 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"
 JanMar 2013: OP organises "Problemsolving 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!!!
 JulSep 2013: OP visits TUMunich 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"
 JanMar 2014: Tomasz Tkocz and OP organise "Problemsolving seminar for undergraduates" (Warwick's team comes 39th in 2014 IMC)
 59 May 2014: A.CojaOghlan, M.Jerrum, OP and G.Sorkin organise workshop "Phase transitions in discrete structures and computational problems", University of Warwick
 710 Jul 2014: E.Cancellero, D.Falik, A.Liebenau, V.Patel and JS organise QMULWarwick Alliance open problems workshop in combinatorics and graph theory, Cotswolds
 1418 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
 JanMar 2014: Tomasz Tkocz, Rosemberg Toala, Myhaylo Poplavsky and OP organise "Problemsolving seminar for undergraduates" (with competition taking place in August 2015)
 19 Mar 2015: KS successfully defends her PhD thesis ''Robust expansion and Hamiltonicity''. Congratulations!!!
 15 July 2015: P.Keevash, D.Kral', OP and N.Woodhouse organise Summer School "Regularity and Analytic Methods in Combinatorics", University of Warwick
 610 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
 1416 Sep 2015: OP and KT organise workshop "NonCombinatorial Combinatorics", University of Warwick
 45 Nov 2015: Petter Brändén (KTH Stochholm) gives a minicourse "Combinatorics and geometry of hyperbolic and stable polynomials"
 Apr 2016: Josh Brown (supervised by KS) and George Witty (supervised by OP) successfully defend their 4th 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 120th anniversary of Kazimierz Kuratowski, Lviv
 May 2017: Henry Dai (supervised by KS), Asher Ehlers and Arun Krishnamoorthy (supervised by OP) successfully defend their 4th year projects. Congratulations!
 9 June 2017: OP & KS organise "One Day BirminghamWarwick Combinatorics Meeting"
 1822 Sep 2017: OP & KS organise conference "Extremal Combinatorics"
 89 Nov 2017: Christian Reiher (Hamburg) gives a minicourse "Clique densities"
 2627 Mar 2018: OP gives a minicourse "Descriptive graph combinatorics", Workshop "Graph Limits", Janov, Czech Republic
Visitors
 59 Nov 2012: Matthew Yancey (UIUC)
 2024 Nov 2012: Oleg Verbitsky (HUBerlin)
 58 Feb 2013: Teresa Sousa (New University of Lisbon)
 1525 Nov 2013: Evan DeCorte (TUDeflt)
 23 Feb  1 Mar 2014: Humberto Naves (ETH Zurich)
 1219 Oct 2014: Felix Lazebnik (U of Delaware)
 1530 Oct 2014: Swiatoslaw Gal (Wroclaw)
 23 Nov  2 Dec 2014: Balazs Udvari (Szeged)
 1322 July 2015: Evan DeCorte (Hebrew U of Jerusalem)
 1829 Jan 2016: Jan Volec (ETH Zurich)
 12 Jul  7 Sep 2016: Maryam Sharifzadeh (UIUC)
 912 Nov 2016: Alexey Pokrovskiy (ETH Zurich)
 1721 Jan 2017: Mihyun Kang (TUGraz)
 29 Jan  4 Feb 2017: Tamas Makai (TUGraz)
 25 May 2017: Lukasz Grabowski (Lancaster)
 1619 May 2017: Hao Huang (Emory)
 29 May  3 June 2017: Evan DeCorte (McGill)
 2528 June 2017: Mohammad Bardestani (Münster)
 710 Nov 2017: Christian Reiher (Hamburg)
This project has received funding from the European Union’s Seventh Framework Programme for research, technological development and demonstration under grant agreement no 306493. 