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.

• Thursday, 1/16 : Note the change in classroom to RE 119


• Monday, 1/13 : Check this webpage regularly for homework assignments, announcements, etc.

• 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.

• 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; Frugal proper colorings of graphs; Hardy-Ramanujan theorem for number of prime factors; Weierstrass Approximation Theorem; Low-distortion embedding of data points in low dimensions and the Johnson-Lindentrauss flattening lemma; Discrepancy of a set system/hypergraph; A counterexample to Hajos' conjecture in graph theory.
  Probabilistic problems (solved using probabilistic methods): Random graph models, particularly Erdos-Renyi Random graphs; Properties of Random graphs that hold "with high probability"; Almost every G(n,p) is connected for a fixed p; Threshold function for a monotone graph property; Threshold for appearance of a Balanced (and non-balanced) subgraph in G(n,p); Sampling multidimensional data and a weak version of VC-dimension bound; Almost orthogonality of any two vectors picked from unit sphere in Euclidean space; Almost all graphs are counterexamples to Hajos' conjecture in graph theory.
  Counting Problems (solved using Entropy): Discrete version of Loomis-Whitney Isoperimetric Inequality; Estimating Binomial coefficients and their sums using binary entropy; Size of the family of graphs with pairwise intersection containing a triangle as progress towards Simonovits-Sos conjecture; the maximum number of copies of a fixed hypergraph H in the family of all hypergraphs with l edges using the fractional cover number of H; the number of independent sets in a regular bipartite graph.
  


• 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; Chernoff-Hoeffding deviation bounds and Concentration of Measure; CH-bounds for negatively correlated r.v.s; Martingale based large deviation inequalities - IBDI, ABDI.
  Information Theory. Entropy; Binary Entropy; Conditional Entropy; Uniformity, Subadditivity, Chain rule, and related properties; Shearer's Entropy Lemma.
  

• 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 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.
    HW solutions distributed in class.
    


• Weeks #5 and #6 : 4 Lectures.
  
  • Topics: Subtlety of defining "bad events" in: Finding an independent transversal in a partitioned graph; List coloring a graph with lists of limited overlap (bounded repetitions of a color in a neighborhood). Asymmetric form of LLL and its proof from the general form, example in hypergraph 2-coloring where symmetric LLL doesn't apply but asymmteric LLL does. Frugal proper colorings of graphs and bounding the number of colors in a frugal coloring using asymmetric LLL.
    "almost always"/ "asymptotically almost always"/ "with high probability", Binomial random graph model, Uniform random graph model, Graph property, Convex and Monotone properties, Conditions under which convex property almost always holds in G(n,p) iff it holds in G(n,m) (no proof), For fixed p, almost every G(n,p) is connected. Threshold function for a monotone graph property, Variance, Covariance, Chebyshev's inequality, Second Moment Method using Markov and Chebyshev, Threshold for appearance of a triangle in G(n,p), Balanced graphs - definition and examples, Threshold for appearance of a fixed balanced subgraph in G(n,p), Threshold for appearance of non-balanced subgraph in terms of maximum density, Why threshold for appearance non-balanced subgraph is not the same as the threshold for a balanced subgraph with same number of vertices and edges.
    Some examples and conjectures for sharp thresholds and suggestions for further reading. Application of Second Moment method (Chebyshev's inequality) in Number Theory (Hardy-Ramanujan theorem for number of prime factors) and Analysis (Weierstrass Approximation Theorem).
    What is concentration of measure phenomenon?, various methods to derive large deviation bounds, Bernstein's idea to use Moment generating function, how it generalizes to Chernoff and Chernoff-Hoeffding inequalities and their variants.
    [Comment: See below for some relevant supplemental readings.]
  • Lecture Notes: Outlines of lectures without all the details as discussed in the live classroom. Notes#5. Notes#6.
  • Homework:
    Follow the detailed instructions and rules for HWs given in the Course Information Handout.
    Homework #3 Due Wednesday, 2/26.
    Questions? Ask on Canvas. Or, send email. Plus Office hours as announced above.
    
    


• Week #7 : 2 Lectures.
  
  • Topics: What is concentration of measure phenomenon?, various methods to derive large deviation bounds, Bernstein's idea to use Moment generating function, how it generalizes to Chernoff and Chernoff-Hoeffding inequalities and their variants. An exponentially decaying bound for Chernoff and Chernoff-Hoeffding, CH-bounds for independent random variables on general and distinct intervals, CH-bound with variance, Applications of CH-bounds: Sampling multidimensional data and a weak version of VC-dimension bound, discrepancy of a set system/hypergraph, Any two vectors picked from unit sphere in Euclidean space are almost orthogonal, Low-distortion embedding of data points in low dimensions and the Johnson-Lindentrauss flattening lemma, Hajos and Hadwiger's conjectures in graph theory, almost all graphs are counterexamples to Hajos' conjecture.
    CH-type bounds in situations when underlying random variables are not independent (e.g. negatively correlated (Paconesi and Srinivasan 1997; dependency graph (Pemmaraju 2001)), or if the function of the random variables is arbitrary (not necessarily linear) (Martingale based methods (McDiarmid 1997)).
    [Comment: See below for some relevant supplemental readings.]
  • Lecture Notes: Outlines of lectures without all the details as discussed in the live classroom. Notes#7.
  • Homework:
    Follow the detailed instructions and rules for HWs given in the Course Information Handout.
    Homework #4 Due Wednesday, March 12th
    Questions? Ask on Canvas. Or, send email. Plus Office hours as announced above.
    
    
• Weeks #8 and #9 : 4 Lectures.
  
  • Topics: Shannon Entropy. Entropy of a random variable with finite range, Characterizing properties of the Entropy function, Binary entropy function, Interpretation of entropy as information content, Jensen's Inequality, Uniform bound for Entropy and its connection with counting. Properties of Entropy - Subadditivity, Monotonicity, Conditional Entropy, Chain rule, Dropping Conditioning; Discrete version of Loomis-Whitney Isoperimetric Inequality; Binary Entropy and Binomial coefficients.
    Bounding the size of a set system in terms of binary entropy; Shearer's Lemma and Combinatorial version of Shearer's Lemma; Bounding the size of an Intersecting family with pairwise intersection containing consecutive numbers; Bounding the family of graphs with pairwise intersection containing a triangle as progress towards Simonovits-Sos conjecture.
    Bounding the maximum number of copies of a fixed hypergraph H in the family of all hypergraphs with l edges in terms of the fractional cover number of H, discussion of various definitions of "subhypergraphs", independent sets and edge covers in hypergraphs, A brief discussion of - Linear Optimization, duality theory, 0-1 integer program, LP relaxation of an 0-1 integer program, fractional cover number and fractional independence number of a hypergraph as dual LP relaxations of their 0-1 integer programs.
    Proof for bounding N(H,l)= the maximum number of copies of a fixed hypergraph H in the family of all hypergraphs with l edges: upper bound using fractional cover number, lower bound using a blow-up of H and fractional independence number. Enumerative problems for Homomorphisms of graphs, Kahn's sharp bound on the number of independent sets in a regular bipartite 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#8. Notes#9. Notes#10
  • Homework:
    Follow the detailed instructions and rules for HWs given in the Course Information Handout.
    Homework #5 TBA: Due TBA
    Questions? Ask on Canvas. Or, send email. Plus Office hours as announced above.
    HW solutions distributed in class.
    

• 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 we cover in class.
• Regarding Random graphs, Random graph and network models, and their properties, I recommend the following three textbooks to dive deeper into these topics:
  Frieze, Karonski, Introduction to Random Graphs.
  Janson, Rucinski, Luczak, Random Graphs.
  van der Hofstad, Random Graphs and Complex Networks.
• A couple of classic papers by Michel Talagrand on concentration of measure and probability.
  A new look at independence.
  Concentration of measure and isoperimetric inequalities in product spaces
• Some good sources for discussion on applications of concentration of measure and particularly Martingale based methods:
  McDiarmid's chapter on Concentration in Probabilistic Methods for Algorithmic Discrete Mathematics and
  the appropriate chapters in Concentration of Measure for the Analysis of Randomized Algorithms
• Pemmaraju, Equitable Coloring Extends Chernoff-Hoeffding Bounds is an elegant paper.
  As a graduate student, I used the idea of equitable coloring of dependency graph to extend Arnold and Groenveld's classical bounds on order statistics of indepednent r.v.s to a useful dependent setting in H. Kaul and S. H. Jacobson, New global optima results for the Kauffman NK model: handling dependency; also see slide 87-88 of Talk slides.
• See Section 4 of DP-Coloring of Graphs from Random Covers for a recent application of CH-type bound on negatively correlated random variables.
• The Handbook of Graph Drawing and Visualization gives a series of surveys on all aspects of graph drawing - theoretical, algorithmic, and applied.
• To learn more about theoretical aspects of Topological Graph Theory, consider a combination of one or more of these textbooks:
  TGT by Gross and Tucker;
  Graphs on Surfaces by Mohar and Thomassen;
  Crossing Numbers of Graphs by Schaefer.
• To learn more about Low-distortion embeddings of finite metric spaces:
  Matousek's lecture notes;
  Handbook survey chapter;
  An article on algorithmic applications of such embeddings.
• The seminal paper of Shannon that introduced Information Entropy and much more.
  Also look up Mutual Information; Shannon capacity of a (confusability) graph, Lovasz Theta function (proof for 5-cycle in the chapter on communicating without errors in Proofs from THE BOOK.
• A gentle discussion of the distinction between probability and randomness with a surprise showing of Entropy at the end.

• Wikipedia: Combinatorics
• Mathpages: Combinatorics
• Mathworld : Combinatorics Dictionary
• Wikipedia: Graph Theory
• Mathworld : Graph Theory Dictionary
• Dynamic Surveys in Combinatorics
• Combinatorial Software and Databases
• Combinatorial Object Server


• Journals (etc.) in Discrete Mathematics and related fields


• A summary of useful inequalities