Random Structures and Algorithms
Arizona State University, Fall 2021
Class meetings: Mondays and Wednesdays 3–4:15pm, WXLR A307
Instructor: Zilin Jiang, zilinj [at] asu [dot] edu
Office hours: Friday 1pm–2:30pm
Course Description
Prerequisites: A strong undergraduate background in discrete mathematics and probability theory.
Primary references:
- Noga Alon, and Joel H. Spencer. The probabilistic method. John Wiley & Sons, 2016.
- László Lovász. Large networks and graph limits. Vol. 60. American Mathematical Soc., 2012.
- Rajeev Motwani, and Prabhakar Raghavan. Randomized algorithms. Cambridge university press, 1995.
- Bernd Gärtner, Jiri Matousek. Approximation Algorithms and Semidefinite Programming. Springer Berlin Heidelberg, 2012.
Onboarding:
- Please fill out the pre-semester questionnaire.
- Learn how to use LaTeX (I recommend the tutorials on Overleaf).
Asking questions:
For class-related questions, it is best to come to office hours.
Grading
Homework 70% + Scribing 30%
Assignments
You are strongly encouraged to do as much homework as possible individually; you will gain the most of out the course this way.
Sources and collaboration policy. Collaboration and use of external sources are permitted, but must be fully acknowledged and cited. Collaboration may involve only discussion; all the writing must be done individually. Failure to do so will be treated as cheating.
Late policy and grade appeal policy. In general no late homework will be accepted unless there is a genuine emergency backed up by official documents. No grade appeal will be considered after one week of the posting of the grade for any assignment.
There will be 5 assignments.
Assignment 1 due on Jan 28 (extended to Jan 31).
Assignment 2 due on Feb 11.
Assignment 3 due on Feb 25 (extended to Feb 28)
Assignment 4 due on Mar 18 (extended to Mar 20).
Assignment 5 due on Apr 15 (extended to Apr 17).
Schedule
Week 1
Jan 10. Diagonal Ramsey numbers, random graphs Gn,1/2, the Ajtai–Komlós–Szemerédi theorem on the independence number of a triangle free graph, Turán’s lower bound on the independence number of a (general) graph, an upper bound on the Ramsey number R(3, t). [scribe: Zilin Jiang]
Jan 12. Proof of the Ajtai–Komlós–Szemerédi theorem, a lower bound on the crossing number of a graph. [scribe: Zilin Jiang]
Week 2
Jan 17. No class. (Martin Luther King Jr. Holiday)
Jan 19. the Szemerédi–Trotter theorem on point-line incidences, the Erdős–Moser theorem on distinct subsets sum. [scribe: Andre Rouhani]
Week 3
Jan 24. The independence number of an Erdős–Rényi random graph. [scribe: Chloe Frechette]
Jan 26. The phase transition of the random k-SAT problem. [scribe: Brandon Joyce Freeman]
Week 4
Jan 31. The phase transition of the 2-SAT problem happens when the clause-variable ratio equals 1. [scribe: Christopher Sumnicht]
Feb 2. The Lovász local lemma and its symmetric version, two applications: injective functions and k-CNF formulas. [scribe: Joseph Briones]
Week 5
Feb 7. 2-colorability of hypergraphs, Moser’s fix-it algorithm and the proof of its validity. [scribe: S. Alex Bradt]
Feb 9. Special cases of Moser’s fix-it algorithm, information theoretic proof of the validity of Moser’s fix-it algorithm for a random k-SAT problem. [scribe: Rajan Hari Ambrish]
Week 6
Feb 14. Szemerédi’s regularity lemma, energy increment argument. [scribe: Christiaan van de Sande]
Feb 16. Triangle counting lemma, triangle removal lemma, property testing. [scribe: Andre Rouhani]
Week 7
Feb 21. Roth’s theorem via triangle removal lemma, graph counting lemma, graph removal lemma, graph embedding lemma. [scribe: Chloe Frechette]
Feb 23. Induced graph removal lemma, the colorful graph removal lemma, the infinite graph removal lemma, the strong graph regularity lemma, hypergraph regularity [scribe: Brandon Joyce Freeman]
Week 8
Feb 28. Five equivalent definitions of pseudorandom graphs [scribe: Christopher Sumnicht]
Mar 2. Equivalence of C4 and EIG, expander mixing lemma, Payley graphs are pseudorandom. [scribe: Joseph Briones]
Week 9
Mar 7. No class. (Spring break)
Mar 9. No class. (Spring break)
Week 10
Mar 14. Graphon, associated graphon, left-convergence, homomorphism densities, measure-preserving map of [0, 1]. [scribe: S. Alex Bradt]
Mar 16. Left convergence of graphs and graphons, W-random graphs and their left-convergence, cut norm, cut distance, Lp-norm. [scribe: Rajan Hair Ambrish]
Week 11
Mar 21. The Goemans–Williamson algorithm: rounding the MaxCut SDP [scribe: Joseph Briones]
Mar 23. Weak regularity lemma for graphs, and its application to approximate the MaxCut problem up to an additive error Ɛn2, the metric space of graphons under the cut distance, and its compactness [scribe: Andre Rouhani]
Week 12
Mar 28. Graphs are dense in the space of graphons, equivalence of left convergence and convergence under the cut metric, the uniqueness lemma. [scribe: Chloe Frechette]
Mar 30. MaxCut problem, approximation algorithm, semidefinite programming, 0.5-approximation algorithm for MaxCut. [scribe: Christopher Sumnicht]
Week 13
April 4.
April 6. Semidefinite programming, ellipsoid methods, secret agent and umbrella [scribe: S. Alex Bradt]
Week 14
April 11. Computation of Θ(C5), the Lovász theta function, the Lovász sandwich theorem. [scribe: Rajan Hari Ambrish]
April 13. Semidefinite formulation of the Lovász theta function, hardness of approximation of MaxCut, the unique game conjecture and the topography problem. [scribe: Christiaan van de Sande]
Week 15
April 18. Six deviations suffice. [speakers: Joseph Briones and S. Alex Bradt]
April 20. The Lovász theta function of cycles, and bounds on the Shannon capacity of C7. [speakers: Rajan Hari Ambrish and Christiaan van de Sande]
Week 16
April 25. The spectral graph theoretic proof of Szemeredi’s regularity lemma [speakers: Christopher Sumnicht and Chloe Frechette]
April 27. The algorithmic version of the weak regularity lemma [speakers: Andre Rouhani and Christiaan van de Sande]