Course: MCS 583, Extremal Combinatorics

Call no: 44948

Time: MWF 10:00-10:50pm

Place: 202 Lincoln Hall

Professor: Dhruv Mubayi

Office: 620 SEO

E-mail: mubayi@uic.edu

Course Web Page:
http://www.math.uic.edu/~mubayi/583/Fall24/ExtremalFall24.html

Office Hours: TBD

Grading Policies and Points Breakdown:

You grade will be based on homework assignments (roughly 4-5 problems every two weeks) (60%), and
quizzes/in-class tests, and class presentations (40%). A total score of 80% roughly correlates to an A.
You can discuss homework with each other but must write it up
independently with no help from anyone else. Do not search the web for solutions, but you are permitted to search the
web for definitions (or just email me).

Homework *MUST* be typed in Latex and posted on blackboard as a pdf file before class begins on the day it is due.

Accommodations: Disability Policy - Students with disabilities who require accommodations for access and participation in this course must be registered with the Office of Disability Services (ODS). Please contact ODS a 312/413/-2183 (voice) or 312/413-0123 (TTY).

Prerequisite: An undergraduate course in combinatorics/graph theory or probability, and the mathematical maturity of a (relatively advanced) graduate student.

Course Description: Extremal combinatorics studies the extreme value of a parameter over a class of discrete objects.
The subject has been growing for the past century and by now it encompasses some of the most important contributions
to combinatorics and has applications to many other disciplines including discrete geometry, number theory, coding theory,
computer science. This course will study the modern developments in the subject focusing on Ramsey theory and extremal
graph and hypergraph theory. Throughout the course open problems will be presented that are suitable for thesis research.

A sampling of topics:

- Ramsey numbers of graphs and hypergraphs including recent work on asymmetric Ramsey numbers for hypergraphs, the Erd\H os-Rogers problem, and multicolor Ramsey numbers.
- Methods in extremal graph and set theory, including classical extremal graph theory (Zarankiewicz problem, Erdos-Simonovits-Stone theorem) and more recent probabilistic tools (dependent random choice) and algebraic constructions (Projective Norm graphs); extensions of classical results in extremal set theory (Erdos-Ko-Rado type theorems), the delta system method, the random walk method, and more recent approaches using sampling and shadows.
- Graph and Hypergraph Regularity Lemmas and accompanying removal lemmas; applications to Roth's theorems on arithmetic progressions and the multidimensional Szemer\'edi theorem.
- Quasirandom structures focusing on recent developments on hypergraph quasirandomness.

Course Goals and Learning Objectives: To gain proficiency in the main themes of modern extremal combinatorics.

Recommended Coure Materials: Extremal Combinatorics, by Mubayi and Verstraete; I will provide an electronic copy of the working draft of this text.

Policy for missed or late work, including acceptance of revised work: Homework turned in late will not be graded unless prior approval of the instructor has been obtained.

Attendance/Participation Policy: Attendance is required and students are expected to actively participate and engage with the material during lectures.

Community Agreement/Classroom Conduct Policy: Community Agreement: Ground Rules for a Safe/Brave Space

- Be present (turn off cell phones and remove yourself from other distractions)
- Be respectful
- Assume good will
- Challenge with care - approach discussion as a "think out loud"
- Take space/make space
- Try not to make assumptions, seek to understand, not to judge
- Be open to challenges as an opportunity to learn something new
- Be open to different perspectives Debate the concepts not the person
- Be flexible when things don't work
- Share helpful tips
- Use preferred names and gender pronouns
- No side conversations
- Be willing to work together

Homework 1, Due Friday September 13

Homework 2, Due Friday September 27

Homework 3, Due Friday October 11

Homework 4, Due Friday October 25

Homework 5, Due Friday November 8

Homework 6, Due Friday November 22

Homework 7, Due Friday December 6