This is an intensive two-week online mini-course where we will learn some applications of finite geometry in Ramsey theory. We will cover some of the recent breakthroughs in graph Ramsey theory and discuss how finite geometry can play a role in further progress.
No prior background in finite geometry or Ramsey theory is required. The algebraic background that we will need is reviewed here and the common asymptotic approximations that we will use is reviewed here.
There will be 6 lectures (1.5 hours each), 2 exercise sessions and 2 open problem sessions.
Dates: 11-01-2021 to 22-01-2021.
Time: 15:30 – 17:15 UTC
First Week, 11th Jan to 15th Jan:
Monday, Lecture 1: introduction, affine spaces, projective spaces and generalized quadrangles. Video.
Tuesday, Lecture 2: generalized quadrangles and spectral graph theory. Video.
Thursday, Lecture 3: Ramsey numbers, explicit constructions for r(3, t). Video.
Friday, Lecture 4: lower bounds via graphs with few independent sets, polar spaces, Video.
Second Week, 18th Jan to 22nd Jan:
Tuesday, Lecture 5: clique-free optimally pseudorandom graphs from quadratic forms. Video.
Wednesday, Lecture 6: multicolour diagonal Ramsey numbers, Video.
Thursday, Open Problem Session 1.
Friday, Open Problem Session 2.
The lecture notes can be found here.
- Simeon Ball, Finite Geometry and Combinatorial Applications
- Bart De Bruyn, An introduction to Incidence Geometry
- Chris Godsil and Gordon Royle, Algebraic Graph Theory
- Luca Trevisan, Lecture Notes on Expansion, Sparsest Cut, and Spectral Graph Theory
- Akihiro Munemasa, The geometry of orthogonal groups over finite fields.
- Yuval Wigderson, Multicolor Ramsey numbers.
- David Conlon, Graph Ramsey theory.
- Michael Krivelevich and Benny Sudakov, Pseudo-random graphs.
- N. Alon. Explicit Ramsey graphs and orthonormal labelings.Electron J Comb, page #R12, 1994
- N. Alon and M. Krivelevich. Constructive bounds for a Ramsey-type problem.Graphs Comb, 13(3):217–225,1997
- J. Bamberg, A. Bishnoi, and T. Lesgourgues. The minimum degree of minimal Ramsey graphs for cliques.arXiv:2008.02474, 2020
- A. Bishnoi, F. Ihringer, and V. Pepe. A construction for clique-free pseudorandom graphs.Combinatorica,40:307–314, 2020.
- D. Conlon. A sequence of triangle-free pseudorandom graphs. Combin. Probab. Comput., 26:195–200, 2017.
- D. Conlon and A. Ferber. Lower bounds for multicolor Ramsey numbers. Adv. Math., accepted, arXiv:2009.10458, 2020 (Blog).
- X. He and Y. Wigderson. Multicolor Ramsey numbers via pseudorandom graphs. arXiv:1910.06287, 2019.
- S. Kopparty. Cayley Graphs. 2011. (Blog)
- A. Kostochka, P. Pudlák, & V. Rödl. Some constructive bounds on Ramsey numbers. Journal of Combinatorial Theory, Series B, 100(5), 439-445, 2010.
- Patrick Morris, Clique factors in pseudorandom graphs, arXiv:2101.05092, 2021.
- D. Mubayi and J. Verstraëte. A note on Pseudorandom Ramsey graphs. arXiv:1909.01461, 2019.
- A. Sah. Diagonal Ramsey via effective quasirandomness. arXiv:2005.09251, 2020.
- Y. Wigderson. An improved lower bound on multicolor Ramsey numbers.arXiv:2009.12020, 2020.
Lecturer: Anurag Bishnoi
Organizers: Anurag Bishnoi (TU Delft) and Jozef Skokan (LSE)
The course is open to everyone. Please sign up using the following link: https://forms.gle/oxdDo19Pgbdz7iVU8
The zoom link will be emailed to those who register.
Sponsored by the research in pairs grant of the London Mathematical Society.