Math 7018 Probabilistic Methods in Combinatorics

Spring 2021 Tentative Syllabus

Instructor: Lutz Warnke (warnke-at-math.gatech.edu)

Lecture location/time: Bluejeans, Tuesday and Thursday 12:30-13:45

Office hours: Bluejeans, TBA

                      (the easiest way to contact me is to approach/ask me after class)

Grader: Kalen Patton (kpatton33-at-gatech.edu)

Prerequisite: Undergrad probability and combinatorics, or consent of instructor.

Objective:

•  The main goal is to gain basic mathematical working knowledge of the Probabilistic Method, which is a powerful set of tools/methods that has many applications in combinatorics, discrete mathematics and theoretical computer science. (This includes the perhaps surprising idea that probability can be used to prove the deterministic statement of a theorem/the existence of a desired object.)

•  A secondary goal is to learn a few concepts/tools from classical probability theory that are relevant for ACO research. (This includes concentration inequalities, which often play an important role in the analysis of randomized algorithms.)

List of Main Topics:

•  Basics of Combinatorial Probability/Probabilistic Method:

   First and second moment methods, Linearity of expectation, Alteration/deletion method, Lov´asz Local Lemma

•  ACO Probability Theory:

   Random variables and convergence notions (incl. Laws of large numbers, Central limit theorem, and Berry-Esseen Theorem), Conditional expectation and variance, Chernoff bounds, Method of moments

•  Martingales:

   Doob martingale, Azuma-Hoeffding inequality, Method of bounded differences (Mc-Diarmid’s inequality)

•  The Poisson Paradigm:

   Janson’s inequality, Method of moments, Correlation and Harris’ inequality, Suen’s inequality

•  Further potential Topics (as time permits):

   Properties of random graphs and threshold phenomena, Combinatorial discrepancy, Talagrand’s inequality, Existence of limits (Interpolation Method), Dynamic Concen-tration (Differential Equation Method), Entropy techniques

Textbook: The Probabilistic Method by Alon-Spencer, Wiley (3rd or 4th ed.)

You may also find it useful to consult other related textbooks:

•  Extremal Combinatorics by Jukna (Springer).

•  Probability and Computing by Mitzenmacher-Upfal (CUP).

•  Probability and Random Processes by Grimmett-Stirzaker (OUP).

•  Random Graphs by Frieze-Karo´nski (CUP) or Janson- Luczak-Ruci´nski (Wiley).

Suggestions:

•  Class participation and discussion is highly encouraged.

•  Please feel free to ask questions at any time: in particular before, after or during the class (or come to office hours).

Grading policy: Homework 40%, Midterm exam 20%, Final exam 40%.

Final grades will be assigned according to the standard cutoffs (90-100 A, 80-89 B, 70-79 C, 60-69 D, 0-59 F). These cutoffs may be lowered (curved down) at the end of the semester based on class performance, but they will not be raised.

Homework: There will be around 5 graded homework assignments during the semester, which must be submitted online through Gradescope (which can be accessed through Canvas); you are encouraged to typeset your homework solutions using LaTeX.

You are strongly advised to (attempt to) solve all the homework problems. You are allowed to discuss your homework assignments with other students, but you are required to write the solutions on your own (i.e., you have to write them in your own words).

Solutions to optional bonus problems can not increase your score beyond 100% of the points, i.e., for grading purposes the total score on the homeworks is capped at 100%.

The default policy is to not accept late homework.

Exam-Dates: Closed-book and closed-notes.

Midterm: Friday March 11: in class + take-home component

Cumulative Final: Monday May 3: online (details tBA)

The default policy is to have no makeup exams. If you have a documented illness or circumstances outside of your control which prevent you from taking the final exam, we will make other arrangements.

Hybrid touchpoint format: Online lectures via Bluejeans during the regularly sched-uled class time, with a few in-person sessions, where face covering is required (but in-person attendance is not mandatory). Lectures will be recorded and posted to Canvas, and office hours will be conducted remotely via BlueJeans. Class announcements and information will be posted to Canvas, and all forms of assessment will be online/collected electronically (attendance is not part of the course grade).

Auditing and Pass/Fail Grading: If you intend to audit this course or take the course with a pass/fail grade, please e-mail me as soon as possible.

Academic Integrity: Georgia Tech aims to cultivate a community based on trust, academic integrity, and honor. Students are expected to act according to the highest ethical standards. See http://www.catalog.gatech.edu/policies/honor-code/ or http://www.catalog.gatech.edu/rules/18/ for information on Georgia Tech’s Academic Honor Code. Any student suspected of cheating or plagiarizing on a quiz, exam, or assignment will be reported to the Office of Student Integrity, who will investigate the incident and identify the appropriate penalty for violations.

Student-Faculty Expectations: At Georgia Tech we believe that it is important to strive for an atmosphere of mutual respect, acknowledgement, and responsibility between faculty members and the student body. See http://www.catalog.gatech.edu/rules/ 22/ for an articulation of some basic expectation that you can have of me and that I have of you. In the end, simple respect for knowledge, hard work, and cordial interactions will help build the environment we seek. Therefore, I encourage you to remain committed to the ideals of Georgia Tech while in this class.

Accommodations for Students with Disabilities If you are a student with learning needs that require special accommodation, contact the Office of Disability Services at (404)894-2563 or http://disabilityservices.gatech.edu/, as soon as possible, to make an appointment to discuss your special needs and to obtain an accommodations letter. Please also e-mail me as soon as possible in order to set up a time to discuss your learning needs

Health-related considerations: Effective July 15, 2020, University System of Georgia (USG) institutions will require all faculty, staff, students, and visitors to wear an appropriate face covering while inside campus facilities/buildings where six feet social distancing may not always be possible. Face covering use will be in addition to and is not a substitute for social distancing. Anyone not using a face covering when required will be asked to wear one or must leave the area. Refusal to comply with the requirement may result in discipline through the applicable conduct code for faculty, staff or students. For more information about face masks and coverings, review the guidelines from Human Resources at https://hr.gatech.edu/face-coverings.

Copyright: My lectures and course materials, including slides, videos, lecture notes, tests, outlines, and similar materials, are protected by U.S. copyright law and by University policy. I am the exclusive owner of the copyright in those materials I create. You may take notes and make copies of course materials for your own use. You may also share those materials with another student who is enrolled in or auditing this course. You may not reproduce, distribute or display (post/upload) lecture notes or recordings or course materials in any other way - whether or not a fee is charged - without my express prior written consent. You also may not allow others to do so. If you do so, you may be subject to student conduct proceedings under the Georgia Tech Student Code of Conduct.

This syllabus is subject to change.