### 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 *G _{n}*

_{,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, *L _{p}*-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 *Ɛn*^{2}, 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 Θ(*C*_{5}), 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 *C*_{7}. [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]