Math 554: Modern Methods in Discrete Applied Math
Instructor: Hemanshu Kaul
Office: 125C Rettaliata Engg Center.
E-mail: kaul [at] iit.edu
Time: 3:15pm-4:30pm Monday and Wednesday.
Place: 119 Rettaliata Engg Center
Discussion Forums: Math 554 at Canvas.
Office Hours: Monday and Wednesday at 4:30-5:30pm. And by appointment in-person or through Zoom (send email to setup appointment).
Questions through Canvas Discussion Forums are strongly encouraged.
|Course Information|
|Advice|
|Announcements|
|Examinations|
|Problems & Topics|
|Weekly Class Log & HW|
|Supplemental Reading|
|Links|
Course Information:
This graduate-level course in Discrete Mathematics will introduce students in Applied Mathematics, Computer science, and Engineering, to the use of tools and techniques from various fields of mathematics like Probability, Linear Algebra, Algebra, and Stochastic processes, to existential and algorithmic problems arising in Graph Theory, Combinatorics, and Computer science.
The tools considered would include Probabilistic Methods, Linear Algebra methods, Combinatorial Nullstellensatz, Entropy, Martingales and large deviation bounds, Markov chain Monte Carlo, etc. These tools will applied to various fundamental problems like - Graph and Hypergraph coloring, Intersecting families of sets, Ramsey problems, Extremal problems on Graphs and on Set systems (Hypergraphs), Optimization problems on discrete structures, Sampling and counting discrete objects, etc.
The Course Information Handout has extensive description of the course - topics, textbook, student evaluation policy, rules for HW, as well as other relevant information. Read it carefully!
The official MATH 554 course syllabus for topics.
Advice for students:
Excellent advice by Francis Su on good mathematical writing.
Why do we have to learn proofs?
On a more abstract note, here is a discussion by Tim Gowers on Language and Grammar of Mathematics - which is what you are learning in a course like this.
Excellent advice for math majors, especially those planning to go on to graduate school, by Terry Tao, 2006 Fields medallist. Required reading.
Read this book on a variety of experiences in the journey to learn mathematics:
Living Proof
Some of the primary sources of information/discussion for careers in Mathematical Sciences:
MAA - Careers
SIAM - Careers
INFORMS - Careers
AMS - Careers
Class Announcements:
- Thursday, 1/16 : Note the change in classroom to RE 119
- Monday, 1/13 : Check this webpage regularly for homework assignments, announcements, etc.
Examinations:
- Mid-term Exam: 4/9 Wednesday. Syllabus: All topics corresponding to HWs#1 to #5.
- Final Exam : TBA. Syllabus: All topics covered during the semester.
Running list of Topics and Methods (covered so far):
- Problems:
Extremal and Existential (deterministic) problems (solved using probabilistic methods): Monte Carlo Randomized algorithm for verifying matrix multiplication; Max-Cut/Largest Bipartite subgraph; Ramsey Numbers; Bernstein's Property B and m(k), Hypergraph Coloring; List coloring of graphs; Intersecting family of sets and Erdos-Ko-Rado theorem; Largest Antichain in Boolean lattice and Bollobas' generalization of LYM inequality; Hamiltonian paths in Tournaments; Turan Number for Graphs; Caro-Wei theorem and application to Turan's theorem; Domination Number of graphs; Graphs with high girth and high chromatic number; More list coloring of graphs;
- Methods and Connections:
Probability Theory. Probability and Union Bound; Expectation; Convexity; Estimates on Binomial coefficients and polynomials; AM-GM and Jensen's inequality; Alteration method; Markov Inequality; Dependency graph and various forms of Lovasz Local Lemma; First Moment method; Second Moment method and Chebyshev Inequality;
Weekly Class Log with HW:
- Weeks #1 and #2 : 3 Lectures and 1 Holiday.
- Topics: Discussion of course structure and purpose. Review of elementary probability theory with an application to Randomized algorithm (Monte Carlo Algo) for verifying matrix multiplication efficiently. Probabilistic Method. Finding a bipartite subgraph with at least half the edges.
Basic Ramsey number, Lower bounds on R(k,k) using existential argument and its improvement using the alteration method, Explicit bounds using estimates for binomial coefficients, factorials, etc., Lower bound vs.upper bound for R(k,k), Hypergraph coloring, Property B, m(k) and its values for k=2 and k=3, Fano plane, Lower bound and Upper bound on m(k), Use of convexity and Jensen's inequality, List coloring, Relation between m(k) and non-k-choosable bipartite graphs, the list chromatic number of K_{n,n}.
[Comment: See below for some relevant supplemental readings.]
- Lecture Notes: Outlines of lectures without all the details as discussed in the classroom. Notes#1. Notes#2.
- Homework:
Carefully review Probability theory and Graph theory using the suggested topics and textbooks listed in Course Information Handout. Ask for help as needed.
Follow the detailed instructions and rules for HWs given in the Course Information Handout.
Homework #1 Due Monday, 2/3.
Questions? Ask on Canvas. Or, send email. Plus Office hours as announced above.
HW solutions to be distributed in class.
- Weeks #3 and #4 : 4 Lectures.
- Topics: Intersecting family of sets, Erdos-Ko-Rado theorem and its probabilistic proof. A more formal write-up of the Erdos-Ko-Rado theorem proof. Using expectation to find a tournament with many Hamiltonian paths, Caro-Wei theorem, its complementary form and application to Turan's theorem, Addition/Deletion method for finding a small dominating set in a graph in terms of n and minimum degree.
Markov inequality for non-negative discrete random variables, Erdos-Renyi Random graphs, Existence of a graph with high girth and high chromatic number. Introduction to Lovasz Local Lemma, Event mutually independent of a collection of other events, Dependency graph, Mutual Independence Principle, (Symmetric) Lovasz Local Lemma and its application to improve the lower bound for diagonal Ramsey numbers R(k,k). General Lovasz Local Lemma, its proof and application to Symmetric Local Lemma; Comments on Lopsided Local Lemma and its application to Latin transversals of arrays; Comments on Algorithmic LLL, Moser-Tardos LLL algorithm (Las Vegas vs Monte Carlo algorithms), Applying LLL to the hypergraph coloring problem and its comparison to the basic result obtained earlier using the union bound, Subtlety of defining "bad events" in: Finding an independent transversal in a partitioned graph.
[Comment: See below for some relevant supplemental readings.]
- Lecture Notes: Outlines of lectures without all the details as discussed in the live classroom. Notes#3, Notes#4.
- Homework:
Follow the detailed instructions and rules for HWs given in the Course Information Handout.
Homework #2 Due Monday, 2/17
Questions? Ask on Canvas. Or, send email. Plus Office hours as announced above.
Supplemental Reading:
- For textbooks for each topic, refer to the course information sheet, and ask me for specific recommendations and advice based on the topic and your interests. Here I will mostly list relevant research papers and problems that can serve as starting points to learn more.
- Max-Cut at wikipedia gives a good overview of the problem and relevant references for better bounds than what we proved in class, the best approximation algorithms, and connections to statistical physics, amongst other things.
- Regarding Ramsey problems.
A short essay I wrote for a general audience that uses Ramsey theory as an example.
If you want to learn more about Ramsey Theory systematically, the following books are easy to read at an undergrad level:
An Introduction to Ramsey Theory: Fast Functions, Infinity, and Metamathematics and Ramsey Theory on the Integers; while Rudiments of Ramsey Theory: Second Edition is nice introductory survey.
A collection of recent articles on Ramsey theory related results in Quanta magazine.
Survey on small Ramsey numbers.
Survey on Applications of Ramsey theory.
An overview of Euclidean Ramsey Theory, which I find fascinating.
Major Breakthrough in Ramsey Numbers!, an exponential improvement after almost 100 years!
- Regarding Turan-type problems.
Wikipedia article gives an overview of five different proofs of Turan's theorem (I strongly recommend buying the book "Proofs from the BOOK" by Aigner and Ziegler for these and many many more beautiful mathematical arguments; its a book for a lifetime of enjoyment).
Survey on Turan-type problems on graphs.
Survey on Turan-type problems on Hypergraphs.
Survey on Turan-type problems on set systems in the language of matrices.
- Regarding the Probabilistic Method overall, to learn more start with the Alon and Spencer's classic textbook. Please discuss with me if you want specific suggestions of topics, or a study plan, following what cover in class.
Links for Additional Information:
HOME