28th Estonian Winter School in Computer Science (EWSCS)
XXVIII Eesti Arvutiteaduse Talvekool

Viinistu, Estonia, March 2 - 5, 2026

Miklós Simonovits

Research professor at Alfréd Rényi Institute of Mathematics, Hungary
home page, Wikipedia

Lecture 1-3:

Extremal graph theory and related areas

 

In the middle of the previous century Combinatorics and Graph Theory consisted only from a few larger areas and many isolated, puzzle-looking problems and results. Next a strange two-direction interaction was built up between these areas and Theoretical Computer Science. Finding fast algorithms became more and more important and understanding several deeper parts of Graph Theory, or more generally, Discrete Mathematics became very important. Random, modified, and pseudo-random methods were introduced by Paul Erdős, and also random codes were used already by Shannon. The investigation of when and how can the randomness be eliminated was also very important in the related cases.

The aim of my first three lectures is to introduce the audience into one of the fastest developing areas of Discrete Mathematics, Extremal Graph Theory, and some further related areas. A sketch of my lectures is the following.

  1. Ramsey and Turán theorems
  2. Classification of Extremal problems, degenerate and non-degenerate extremal problems [6]
  3. Random graphs, the three models: hypergeometric, binomial models and the stopping rule model.
  4. Szemerédi Regularity Lemma, and its applications, see e.g. [5]
  5. Removal Lemma
  6. Typical structures
  7. Some hypergraph results
  8. Some (further) important open problems.

My lectures are planned to be interactive in the sense that the audience can ask questions and I can change the original plans by shifting the originally planned proportions.

Course material (updated 25 March 2026)

References

  1. Homepage of Miklós Simonovits: users.renyi.hu/~miki/
  2. Homepage of Paul Erdős: users.renyi.hu/~p_erdos/
  3. J. Balogh, B. Bollobás, and M. Simonovits: ‘The typical structure of graphs without given excluded subgraphs’, Random Structures and Algorithms 34 (2009), 305–318. MathSciNet MR2504400
  4. Z. Füredi and M. Simonovits: The history of degenerate (bipartite) extremal graph problems, in Erdős Centennial, Bolyai Soc. Math. Stud., 25, János Bolyai Math. Soc., Budapest, (2013) 169–264. arXiv:1306.5167. MathSciNet MR3203598
  5. J. Komlós, and M. Simonovits: Szemerédi’s regularity lemma and its applications in graph theory, in Combinatorics, Paul Erdős Is Eighty, Vol. 2 (Keszthely, 1993), Bolyai Soc. Math. Stud. 2, János Bolyai Math. Soc., Budapest, (1996), pp. 295–352. MathSciNet MR1395865
  6. M. Simonovits: Extremal graph theory, in: L.W. Beineke, R.J. Wilson (Eds.), Selected Topics in Graph Theory II., Academic Press, London, (1983), pp. 161–200. MathSciNet MR0797252
  7. E. Szemerédi: Regular partitions of graphs. In Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), volume 260 of Colloq. Internat. CNRS, pages 399– 401. CNRS, Paris, (1978). MathSciNet MR0540024
Lecture 4:

Estimating the volume and diameter,
by Monte Carlo Markov Chain Method

 

The results, algorithms of Khachian and later of Karmarkar influenced very much some parts of Theoretical Computer Science. Grötschel, Lovász, and Schrijver wrote an important book [5] on Geometric Algorithms. Under the influence of this book, CO. Elekes [3] proved that the volume of a high dimensional convex body cannot be approximated properly with deterministic algorithms. His results were improved by Bárány and Füredi [1].

It was an important problem in Theoretical Computer Science to find fast algorithms for some counting problems. L. Valiant showed that counting the 1-factors, i.e. estimating the permanent of a matrix is a “difficult problem”. It was a breakthrough when Jerrum and Sinclair [6] showed that randomized algorithms can approximate the number of 1-factors of a graph. This led to a next breakthrough by Dyer, Frieze and Kannan [2] showing that using randomization the volume can be well approximated. Lovász and Simonovits [9], [10], [11] improved this result, and after a series of papers Lovász and Vempala [12] proved that basically n4 oracle questions are enough to approximate the volume. We have to remark that the volume can be approximated, however, the the diameter cannot be approximated.

In some sense it was natural to approach the area by randomized algorithms, e.g. Monte Carlo methods [14] were fairly popular. The methods mentioned above can also be used in several further areas, see e.g. [4].

My lecture will give an introduction into this area. Some recommended surveys are the papers of Lovász, and Winkler, e.g. [13], or the homepage of Santosh Vempala [15]

Course material

References

  1. I. Bárány and Z. Füredi: Computing the volume is difficult, Proc. of the 18th Annual ACM Symposium on Theory of Computing (1986), 442–447.
  2. M. Dyer, A. Frieze and R. Kannan: A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies, Proc. of the 21st Annual ACM Symposium on Theory of Computing (1989), 375–381.
  3. G. Elekes: A geometric inequality and the complexity of computing volume, Discrete and Computational Geometry 1(1986), 289–292.
  4. Péter L. Erdős, István Miklós, Lajos Soukup (2025): Fully graphic degree sequences and P-stable degree sequences. Adv. Appl. Math. 163: 102805 (2025)
  5. M. Grötschel, L. Lovász, A. Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin-New York, (1988). MR0936633
  6. M. R. Jerrum and A. Sinclair: Approximating the permanent, SIAM J. Comput. 18(1989), 1149–1178.
  7. R. Kannan, L. Lovász and M. Simonovits, Random walks and a faster volume algorithm, (in preparation).
  8. L. Lovász: How to compute the volume? Jber. d. Dt. Math.-Verein, Jubiläumstagung 1990, B. G. Teubner, Stuttgart, (1992), 138–151.
  9. L. Lovász and M. Simonovits: Mixing rate of Markov chains, an isoperimetric inequality, and computing the volume, Proc. 31st Annual Symp. on Found. of Computer Science, IEEE Computer Soc., (1990), 346–355.
  10. L. Lovász and M. Simonovits: On the randomized complexity of volume and diameter, Proc. 33rd IEEE FOCS (1992), 482–491.
  11. L. Lovász and M. Simonovits: Random walks in a convex body and an improved volume algorithm Random Structures and Alg. 4 (1993), 359–412.
  12. L. Lovász and S. Vempala: “Simulated annealing in convex bodies and an O(n4) volume algorithm”, pp. 650–659 in 44th Annual Symposium on Foundations of Computer Science (Cambridge, MA, 2003), IEEE Comput. Soc. Press, Los Alamitos, CA, 2003. Available at https://faculty.cc.gatech.edu/~vempala/papers/vol4.ps. Also to appear in JCSS.
  13. L. Lovász and P. Winkler: Exact mixing in an unknown Markov chain, The Electronic Journal of Combinatorics 2 (1995), paper R15, 1–14.
  14. N. Metropolis, A. Rosenblut, M. Rosenbluth, A. Teller amd E. Teller, Equation of state calculation by fast computing machines, J. Chem. Physics 21 (1953), 1087–1092.
  15. Santosh Vempala, homepage: https://faculty.cc.gatech.edu/~vempala/

Last changed March 26, 2026 14:55 EET (GMT +02:00) by local organisers