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 40; this maximum if achieved would give the full 80% contribution towards the final grade, i.e. every point from the homework assignments counts as 2% towards the final grade.

Assignment 1 (deadline: March 28, maximum number of points: 68)

Assignment 2 (deadline: April 20, maximum number of points: 28)

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
Feb 28, 2025	Lecture 11	an example of the use of the flag algebra method in the setting of permutations
Mar 4, 2025	TBD	flags with multiple roots, characterization of quasirandom graphs using the flag algebra method
Mar 6, 2025	Lecture 13	Lovász-Sós Theorem on step graphons (stochastic block models), proof of the case of two parts of equal sizes
Mar 11, 2025	Lecture 14	construction of an SDP program to find a flag algebra proof, strategies for cleaning up an SDP solution
Mar 13, 2025	N/A	Q&A sessions on the topics covered so far
Mar 18, 2025	Lecture 15	Paley graphs, spectrum of Paley graphs, quasirandomness of Paley graphs
Mar 20, 2025	Lecture 16	Sidorenko's Conjecture, proof that K_a,b has the Sidorenko property using the entropy method, step Sidorenko property
Apr 1, 2025	TBD	Benjamini-Schramm convergence, estimability of the matching ratio by local algorithms
Apr 3, 2025	TBD	Strong Regularity Lemma, Induced Removal Lemma, testing hereditary graph properties
Apr 8, 2025	TBD	limit distribution associated with Benjamini-Schramm convergent sequences, Aldous-Lyons Conjecture
Apr 10, 2025	TBD	notion of graphing, existence of a limit graphing for Benjamini-Schramm convergent sequences of graphs
Apr 16, 2025	N/A	Q&A sessions on the topics covered so far
Apr 18, 2025	TBD	hypergraph limits, sketch of the statement of the Hypergraph Regularity Lemma
Apr 22, 2025	TBD	convergence notions in the sparse setting (left/right/partition/local-global/large deviation convergence) and their mutual relations
Apr 24, 2025	TBD	basic terminology from matroid theory, quotient-convergence of set functions

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 points for the previous problem
Show that the Turán density of any graph H is equal to (χ(H)-2)/(χ(H)-1) (povided χ(H)>0). [8 points]
Show that for every permuton μ the 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]
Show that a sequence of tournaments is quasirandom if and only if the density of the 4-vertex transitive tournament converges to 4!/64=3/8. [8 points]

Show that the Paley graph with p vertices has no clique larger than √p vertices. [10 points]
Show that every tree has the Sidorenko property. [6 points]
Show that every cycle of even length has the Sidorenko property. [6 points]
Explicitly construct a limit graphing for the following sequence of graphs: G_n is the graph obtained from the n×n grid by subdividing each edge exactly once. [6 points]