Where and when
We typically we will meet at the CS Institute (Ústav informatiky, Pod Vodárenskou věží 2; directions)
If we broadcast on ZOOM, it is in the room https://cesnet.zoom.us/j/3906355031 (with waiting room)
At the CS Institute, the default location is room 318, backup rooms are 107 or 419, see the schedule before coming.
You are welcome in the lecture room for tea and biscuits 15 minutes before the start.
Programme
2022
Friday July 1 in 318, 10:00-11:00, Tomas surveying thresholds for random sets
Friday June 24 in 318 (and on Zoom), 10:00-11:00, Pedro talking about A proof of the Kahn-Kalai conjecture
Monday February 21 in 419 (and on Zoom), 10:00-11:30, Honza H. talking about Graph norms. (Graph norms are a useful new tool for handling many problems extremal graph(on) theory. I will explain some basics. I will assume that people know what a graphon is.)
2021
Friday December 17 in 318 (and on Zoom), 9:30-11:00, Matas on Gärtner-Ellis theorem
Tuesday December 14 in 419 (and on Zoom) 10:00-11:30, Tomas talking anticoncentration and the perfect graph theorem
Friday December 10 in 419 (and on Zoom), 9:30-11:00, Matas on Cramér's theorem: lower bound and extension to higher dimensions
Friday December 3, 9:30-11:00 in 419 (and on Zoom), Tomas completing a proof from Chatterjee and Varadhan; Matas on Cramér's theorem
Friday November 26, 9:30-11:00 in 318 (and on Zoom), Tomas continuing on the paper of Chatterjee and Varadhan
Friday November 19, 9:30-11:00 in 318 (and on Zoom), Cancelled due to illness: Tomas continuing on the paper of Chatterjee and Varadhan
Friday 12: no seminar (book event)
Friday November 5, 10:00-11:30 in 419 (and on Zoom), Tomas presenting The large deviation principle for the Erdős-Rényi random graph by Chatterjee and Varadhan
October 29: no seminar (schoolchildren's holiday)
Friday October 22 in 318, 10:00-11:30 (and on Zoom), Pedro continuing on Combinatorial anti-concentration inequalities, with applications.
Friday October 15 in 419, 10:00-11:00 (and on Zoom), Honza H. continuing on Linear cover time is exponentially unlikely
Friday October 8 in 419, 10:00-11:30 (and on Zoom), Pedro presenting Combinatorial anti-concentration inequalities, with applications by Jacob Fox, Matthew Kwan, and Lisa Sauermann.
Friday October 1 in 318, 10:00-11:00 (and on Zoom), Honza H. presenting Linear cover time is exponentially unlikely by Quentin Dubroff and Jeff Kahn.
Friday September 17 in 318, 10:00-11:00 (cancelled), Pedro
Tuesday June 29 in 318 (and on Zoom - unusually at https://cesnet.zoom.us/my/honzahladky) at 10:30, Honza will read Section 2.1 Combinatorial Techniques for Finite Alphabets from book Large Deviations: Techniques and Applications by A. Dembo, O. Zeitouni
Thursday June 17 in 318 (and Zoom) at 10:30-11:30, Tomas will continue what is left from the last talk
Friday June 11 in 318 (and Zoom) at 10:30-11:30, Tomas will talk about Shearer's inequality and how it is used in Janson-Oleszkiewicz-Ruciński paper
Friday June 4, at CS Institute (broadcast on Zoom) Pedro will present Harel-Mousset-Samotij upper tail proof for triangle count.
Friday May 28 on Zoom, 10:30-11:30, Matas continues on Janson, Oleszkiewicz and Ruciński. Notes
Friday May 21 on Zoom, 10:30-11:30, Matas talking about the upper tail problem for subgraph counts in G(n,p), focusing on Janson, Oleszkiewicz and Ruciński 2004. Notes
2020
Thursday Mar 12 at CS Institute, 10:00-13:45, Diana continuing about packing degenerate graphs, CANCELLED
Friday Mar 6 at Maths Institute, Frederik taling about the proof of Ringel's Conjecture
Feb 27, no seminar
Friday Feb 21 at CS Institute, 10:00-11:30, CANCELLED
Thursday Feb 13 at Maths Institute, 13:01-14.31, Honza talking about Graceful tree labelling conjecture
Thursday Feb 6 at CS Institute, 13:00-14:30, Diana talking about packing degenerate graphs.
Thursday Jan 30 at CS Institute, 13:00-14:30, Diana giving an introductory talk about packing
Thursday Jan 23 at CS Institute, 14:00-15:30, Matas reading about concentration inequalities
2019
Thursday Oct 24 at Matematický ustav (Žitná 25), Modra poslucharna, 13:00-14:30, Honza Hladký reading Davies, Jenssen, Perkins, Roberts: Independent Sets, Matchings, and Occupancy Fractions
Thursday Nov 7 at Matematický ustav (Žitná 25), Modra poslucharna, 14:00-15:30, Honza Hladký reading about the Ising model from these lecture notes.
Thursday Nov 14 at Ústav informatiky (Pod vodárenskou věží 2; directions), Meeting room 419, 13:00-14:30, Frederik reading kissing numbers
Thursday Nov 21 at Matematický ústav (Žitná 25), Konírna, 13:00-14:30, Nicolás reading about the Matching measure
Thursday Nov 28 at Matematický ústav (Žitná 25), Konírna, 13:00-14:30, Hanka reading Matchings in B-S convergent sequences
Thursday Dec 05 at Matematický ústav (Žitná 25), Konírna, 13:00-14:30, Christos reading Widom-Rowlinson model
Thursday Dec 12 at Matematický ústav (Žitná 25), Konírna, 13:00-14:30, Matas reading about the Bethe lattice
Suggested papers to be read (to be extended)
2021
Upper tail:
Borgs, C., Chayes, J., Gaudio, J., Petti, S., & Sen, S. (2020). A large deviation principle for block models. arXiv preprint arXiv:2007.14508.
Cook, N., & Dembo, A. (2020). Large deviations of subgraph counts for sparse Erdős–Rényi graphs. Advances in Mathematics, 373, 107289.
Harel, M., Mousset, F. and Samotij, W., (2019). Upper tails via high moments and entropic stability
F. Augeri (2020). Nonlinear large deviation bounds with applications to traces of Wigner matrices and cycles counts in Erdős–Rényi graphs.
Warnke, L. (2020). On the missing log in upper tail estimates. Journal of Combinatorial Theory, Series B, 140, 98-146.
(reserved for Tomas) Eldan, R. (2018). Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations. Geometric and Functional Analysis, 28(6), 1548-1596.
Bhattacharya, B. B., Ganguly, S., Lubetzky, E., & Zhao, Y. (2017). Upper tails and independence polynomials in random graphs. Advances in Mathematics, 319, 313-347.
Eyal Lubetzky, Yufei Zhao (2017) Random Structures & Algorithms On the variational problem for upper tails in sparse random graphs
Warnke, L. (2016). On the method of typical bounded differences. Combinatorics, Probability and Computing, 25(2), 269-299.
Chatterjee, S., & Dembo, A. (2016). Nonlinear large deviations.Advances in Mathematics, 299, 396-450.
Chatterjee, S. and Varadhan, The large deviation principle for the Erdős-Rényi random graph, 2011 (the main result is Theorem 2.3)
Janson, S., Oleszkiewicz, K. and Ruciński, A., (2004). Upper tails for subgraph counts in random graphs (reserved for Matas)
Large deviations, general theory:
Section 2.1 Combinatorial Techniques for Finite Alphabets from book Large Deviations Techniques and Applications by A. Dembo, O. Zeitouni (I think this is a kind of introduction explaining what "entropy" is in the context of large deviations).
Subgraph count distribution:
Bollobás, B. and Wierman J. (1989) Subgraph Counts and Containment Probabilities of Balanced and Unbalanced Subgraphs in a Large Random Graph
Other:
Quentin Dubroff, Jeff Kahn (2021). Linear cover time is exponentially unlikely (reserved for Honza) arXiv:2109.01237
Jeff Kahn, Gil Kalai (2007) Thresholds and expectation thresholds
Nicolas Curien (2022) Erdös-Rényi Poissonized
2020 spring
Designs:
Minimalist designs, Ben Barber, Stefan Glock, Daniela Kühn, Allan Lo, Richard Montgomery, Deryk Osthus (already contains the main ideas of the "The existence of designs via iterative absorption")
Coloured and directed designs, Peter Keevash (Very hard)
The existence of designs via iterative absorption, Stefan Glock, Daniela Kühn, Allan Lo, Deryk Osthus
Decomposition:
A short proof of the blow-up lemma for approximate decompositions Stefan Ehard and Felix Joos (contains a considerably shorter proof of the main result of the paper by Kim, Kühn, Osthus, Tyomkyn (26 vs. 70 pages))
A blow-up lemma for approximate decompositions, Jaehoon Kim, Daniela Kühn, Deryk Osthus, Mykhaylo Tyomkyn
Packing degenerate graphs, Peter Allen, Julia Böttcher, Jan Hladký, Diana Piguet
Embedding rainbow trees with applications to graph labelling and decomposition, Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov, reservation for Frederik
Resolution of the Oberwolfach problem, Stefan Glock, Felix Joos, Jaehoon Kim, Daniela Kühn, Deryk Osthus
Optimal packings of bounded degree trees, Felix Joos, Jaehoon Kim, Daniela Kühn, Deryk Osthus (the blow-up lemma for approximate decompositions is a main tool in this paper)
A bandwidth theorem for approximate decompositions, P. Condon, Jaehoon Kim, D. Kühn, D. Osthus (the blow-up lemma for approximate decomposition was also used as the main tool; the result of this paper that was the main tool used in the "Oberwolfach problem" paper)
Packing minor-closed families of graphs into complete graphs, Silvia Messuti, Vojtěch Rödl, Mathias Schacht (Easier), reservation for Hanka
Packing trees of unbounded degrees in random graphs, Asaf Ferber, Wojciech Samotij
Packing spanning graphs from separable families, Asaf Ferber, Choongbum Lee, Frank Mousset (Easier)
A proof of Ringel's Conjecture, Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov, reservation for Frederik
Diana's comments "Very hard"and "Easier" apply to those she has read, so no comment means: "I have no idea"
2019 autumn
Graphs and polynomials:
a survey by Will Perkins: here
Hard constraints and the Bethe lattice: adventures at the interface of combinatorics and statistical physics (note that Bethe lattice is infinite d-regular tree, a relatively pleasant object)
Matchings in Benjamini–Schramm convergent graph sequences, reservation for Hanka
On kissing numbers and spherical codes in high dimensions, reservation for Frederik
Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy, reservation for Nicolas
Benjamini–Schramm continuity of root moments of graph polynomials, this one is perhaps difficult if you are not strong in algebra
The Widom–Rowlinson model, the hard-core model and the extremality of the complete graph, reservation for Christos
this book by Mézard and Montanari
Upper tails and independence polynomials in random graphs - rather advanced topic in random graphs, may be a topic for the next season