MATH272 Interdisciplinary Topics in Mathematics

This course taught in relation the SLMath Semester Program on Extremal Combinatorics is focused on the theory of combinatorial limits and its interaction with other areas of mathematics and computer science. The lectures take place at 2pm every Tuesday and Thursday in Dwinelle Hall 183 starting on Tuesday January 21.

Literature

The course does not follow a specific book but a large part of its content can be found in the following two excellent books.

L. Lovász: Large Networks and Graph Limits, American Mathematical Society, Colloquium Publications vol. 60, 2012, 475pp.
Y. Zhao: Graph Theory and Additive Combinatorics, Cambridge University Press, 2023, 338pp.

Assessment

The coursework contributes 80% and the exam 20% contributes to the final grade of the course. Throughout the term, homework assignments will be posted. The maximum number of points that is possible to get for homework assignments is capped at 80; this maximum if achieved would give the full 80% contribution towards the final grade.

Lecture content

A summary of the topics covered during the lectures is posted here. Daniel Raban has kindly been scribing lecture notes, which are available at his homepage https://pillowmath.github.io/.

Date	Summary	Lecture content
Jan 21, 2025	Lecture 0	Motivation results for combinatorial limits: Mantel's Theorem, Turán's Theorem, p-quasirandom graphs, regularity decompositions, Roth's Theorem
Jan 23, 2025	Lecture 1	subpermutation density, permutation convergence, notion of permuton, μ-random permutation, existence of a limit permuton
Jan 28, 2025	Lecture 2	finishing the proof of the existence of a limit permuton, expressing integrals with respect to a permuton as subpermutation densities
Jan 30, 2025	TBD	characterization of quasirandomness of permutations by subpermutations of size four
Feb 5, 2025	Lecture 4	Szemerédi Regularity Lemma (statement only), Removal Lemma for graphs and its proof for triangles
Feb 7, 2025	TBD	Roth's Theorem on arithmetic progressions, Chvátal-Rödl-Szemerédi-Trotter Theorem on Ramsey numbers
Feb 12, 2025	Lecture 6	Proof of Szemerédi Regularity Lemma
Feb 14, 2025	Lecture 7	(induced) density and homomorphic density of graphs, notion of graphon and basic properties, W-random graphs, convergence of W-random graphs to W
Feb 19, 2025	Lecture 8	Erdős-Lovász-Spencer Theorem on the dimension of the subgraph density space
Feb 21, 2025	Lecture 9	existence of a limit graphon of a convergent sequence of graphs
Feb 26, 2025	Lecture 10	introduction of the flag algebra method in the setting of graphs, asymptotic proof of Mantel's Theorem

Assignment problems

Show the uniqueness of the limit permuton of convergent sequences of permutations. [8 points]
Prove the Graph Removal Lemma for complete graphs K_k. [5 points]
Prove the Graph Removal Lemma for all graphs. [3 points in addition to the previous problem]
Show that the Turán density of every graph H is equal to (χ(H)-2)/(χ(H)-1) (povided χ(H)>0). [8 points]
Show that for every permuton μ a sequence of μ-random permutations with increasing sizes converges to μ with probability one. [8 points]
Show the version of the Szemerédi Regularity Lemma with prepartitioning and without the garbage set. [6 points]
Show that for every δ>0 and every graph H, there exiests ε>0 such that the homorphism density of H in a graph G differs from its value expected based on an ε-regular decomposition of G by at most δ. [8 points]
Show that if a graphon W satisfies that d(K₂,W)=1/2 and d(K₃,W)=0, then there exists a partition of [0,1] to two disjoint measurable sets A and B such that W(x,y)=0 for almost all pairs (x,y) in A²∪B² and W(x,y)=1 for almost all remaining pairs (x,y). [6 points]
Show that the fraction of monochromatic triangles (among all triangles) in any 2-edge-coloring of K_n is at least 1/4-o(1). [8 points]