糖心TV

This is the webpage of the ERC Starting Grant No. 306493 1 Oct 2012 - 31 July 2018 (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).

ERC-Funded Group Members

• (Research Fellow, 1 February 2013 - 30 September 2015)
• (PhD student 1 October 2014 - 31 July 2018)
• (Research Fellow, 1 February - 30 August 2016)

• (PI)

• (Research Fellow, 13 October 2016 - 31 December 2017)
• (MPhil student, 1 October 2013 - 30 September 2015)
• (Research Fellow, 1 February 2015 - 31 December 2017)
• (Research Fellow, 1 July 2014 - 30 August 2016)

Papers

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

1. D.Kral' and OP: , Geometric Funct Analysis, 23 (2013) 570-579.
2. OP: , Israel J Math, 201 (2014) 415-454.
3. J.Hladky, A.Mathe, V.Patel and OP: , Trans Amer Math Soc, 367 (2015) 4319-4337.
4. OP and E.R.Vaughan: , 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. 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.
10. 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 47 (2015) 284–303
11. H.Liu, OP, T.Sousa, Monochromatic Clique Decompositions of Graphs, J Graph Theory, 80 (2015) 287-298.
12. KT, Primitive recursive bounds for the finite version of Gowers' c0 theorem, Mathematika, 61 (2015) 501–522.
13. 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 .
14. H.Naves, OP, A.Scott: , Europ J Comb 73 (2018) 138-152
15. ECs, G.Lippner and OP: , Forum of Mathematics, Sigma, 4 (2016) 40pp.
16. OP, A.Razborov, Asymptotic Structure of Graphs with the Minimum Number of Triangles, Combin Prob Comput, 26 (2017) 138-160.
17. OP, Z.Yilma: Supersaturation Problem for Color-Critical Graphs, J Comb Th (B), 123 (2017) 148-185.
18. E.DeCorte, OP: Spherical sets avoiding a prescribed set of angles, International Math Research Notices, 2016 (2016) 6095-6117.
19. OP, The maximal length of a gap between r-graph Turan densities, Electr J Combin, 22 (2015) 7pp.
20. ECs: On the graph limit question of Vera T. S贸s, J Comb Th (B) 116 (2016) 306-311.
21. ECs, Szabolcs M茅sz谩ros: Generalized solution for the Herman Protocol Conjecture, arXiv:1504.06963, 13pp.
22. ECs: Limits of some combinatorial problems, Electronic Notes in Discrete Mathematics, 49 (2015) 577–581.
23. P.Dodos, V.Kanellopoulos and KT: A concentration inequality for product spaces, J Func Anal 270 (2016) 609–620
24. ECs, I.Lo, S.Norin, H.Wu, L.Yepremyan: The extremal function for disconnected minors, JCTB 126 (2017) 162–174
25. ECs, T.Lidbetter: The solution to an open problem for a caching game, Naval Research Logistics, 63 (2016) 23-31
26. L.Grabowski, A.Mathe, OP: Measurable circle squaring, Annals of Mathematics, 185 (2017) 671-710.
27. L.Grabowski, A.Mathe, OP: Measurable equidecompositions for group actions with an expansion property, arXiv:1601.02958
28. ECs: Independent sets and cuts in large-girth regular graphs, arxiv:1602.02747
29. ECs, L.Grabowski, A.Mathe, OP, KT: Borel version of the Local Lemma, arXiv:1605.04877
30. 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.
31. OP, KS, Z.Yilma: The Erd艖s-Rothschild problem on edge-colourings with forbidden monochromatic cliques, Math. Proc Cambridge Phil. Soc., 163 (2017) 341-356.
32. J.Balogh, HL, M.Sharifzadeh: On two problems in Ramsey-Tur谩n theory, SIAM J. Discrete Math. 31 (2017) 1848–1866
33. MF, Rational exponents for hypergraph Turan problems, Journal of Combinatorics, 10 (2019) 61 – 86.
34. A.Geogakopoulos, KT, The Bradley-Terry condition is L1-testable, Discrete Math. 341 (2018) 1171-1177
35. HL, MSh, KS, Local conditions for exponentially many subdivisions, Combin. Prob. Comput. 26 (2017) 423–430
36. KS, A.Treglown, On degree sequences forcing the square of a Hamilton cycle, SIAM J. Discrete Math. 31 (2017) 383–437
37. R.Hancock, KS, A.Treglown, Independent sets in hypergraphs and Ramsey properties of graphs and the integers, SIAM J Discr Math. 33 (2019) 153–188
38. J.Kim, HL, MSh, KS, Proof of Koml\'os's conjecture on Hamiltonian subsets, Proc. London Math. Soc. 115 (2017) 974–1013
39. HL, OP, MSh: Edges not in any monochromatic copy of a fixed graph, J Comb Th (B), 135 (2019) 16-43
40. HL, MSh, KS, On the maximum number of integer colourings with forbidden monochromatic sums, arXiv:1709.09589
41. Ostap Chervak, OP, KS, Minimum number of additive tuples in groups of prime order, Electr J Combin, 26 (2019) Paper 1.30, 15pp
42. HL, OP, KS, The exact minimum number of triangles in a graph of given order and size, Forum of Math, Pi 8 (2020) 144pp.
43. J.Balogh, S.Das, HL, MSh, T.Tran, Structure and Supersaturation for Intersecting Families, Electronic J Comb 26 (2019) Paper 2.34, 38pp
44. JS, OP, KT: , J Comb Th (B) 135 (2019) 129-178
45. MF, Implicit representation conjecture for semi-algebraic graphs, Discr Applied Math 259 (2019) 53–62
46. MF, Kruskal-Katona type problem, arXiv:1805.00340
47. A.Blumenthal, B.Lidicky, Y.Pehova, F.Pfender, OP and J.Volec: , accepted by Combin Prob Comput, 20pp
48. M.Kang, T.Makai, OP, , European J Comb 88 (2020) paper 103107, 27pp
49. T.Banakh, A.Idzik, I.Protasov, OP, K.Pszczola: , J Graph Theory 94 (2020) 175-191
50. P.Bennett, A.Dudek, B.Lidicky, OP: , Combin Prob Comput 29 (2020) 44-67

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
• 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
• 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
• 29 May 2014: OP, Combinatorics seminar, Bristol
• 4 Jun 2014: OP, , Oxford
• 29 Jun 2014: OP, Workshop "", 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
• 14 Nov 2014: KT, Combinatorics seminar, University of 糖心TV
• 21 Nov 2014: OP, Combinatorics Seminar, Queen Mary University of London
• 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 糖心TV
• 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
• 27 May 2015: OP, Seminar, TU-Delft
• 5 June 2015: ECs, Combinatorics Seminar, University of 糖心TV
• 6 Jul 2015: JS, British Combinatorial Conference, University of 糖心TV
• 6 July 2015: KS, British Combinatorial Conference, University of 糖心TV
• 7 July 2015: ECs, British Combinatorial Conference, University of 糖心TV
• 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 糖心TV Maths Society
• 3 Dec 2015: OP, seminar, Cambridge University
• 5 Feb 2016: HL, seminar, U of 糖心TV
• 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 糖心TV
• 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
• 1 Feb 2018: OP, Workshop "Graph Limits", ENS, Lyon
• 15 Feb 2018: OP, Combinarorics Seminar, Cambridge
• 10 May 2018: MF, Poster at London Colloquia in Combinatorics
• 11 Jul 2018: OP, ICGT 2018, Lyon
• 30 Aug 2018: OP, Southwestern German Workshop on Graph Theory, Karlsruhe

Flagmatic

Flagmatic is a package originally developed by 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).

The latest version by Jakub can be downloaded from . Associated user's guide is located in the flagmatic-dev/doc folder or linked here: Flagmatic-dev User's Guide. This version of Flagmatic has been tested on Sage-7.2 and you can have the source from . Flagmatic installation instructions (once you have Sage 7.2) 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: . 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
• Jan 2013: OP becomes a member of the Editorial Board of "Discrete Mathematics"
• Jan-Mar 2013: OP organises "Problem-solving seminar for undergraduates" (糖心TV'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
• 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
• 15 Oct - 3 Dec 2013: OP lectures a TCC course
• Jan-Mar 2014: Tomasz Tkocz and OP organise "Problem-solving seminar for undergraduates" (糖心TV's team comes 39th in 2014 IMC)
• 5-9 May 2014: A.Coja-Oghlan, M.Jerrum, OP and G.Sorkin organise workshop , University of 糖心TV
• 7-10 Jul 2014: E.Cancellero, D.Falik, A.Liebenau, V.Patel and JS organise QMUL-糖心TV 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 糖心TV'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 , University of 糖心TV
• 6-10 July 2015: A.Czumaj, A.Georgakopoulos, D.Kral', V.Lozin and OP are the local organisers of the , University of 糖心TV
• 31 Aug - 4 Sep 2015: R.Kang, T.Muller, J.van Oosten, OP and A.Taraz organise Workshop , Lorentz Center at Oort
• 14-16 Sep 2015: OP and KT organise workshop , University of 糖心TV
• 4-5 Nov 2015: Petter Br盲nd茅n (KTH Stochholm) gives a mini-course ""
• 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-糖心TV 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"
• 26-27 Mar 2018: OP gives a mini-course "Descriptive graph combinatorics", Workshop "Graph Limits", Janov, Czech Republic

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)

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