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: Take-home on Friday 4/11, and in-class on Monday 4/14. Syllabus: All topics corresponding to HWs#1 to #5.
• Final Exam : Monday, May 5, 2pm-4pm, RE 119. 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.
  Counting Problems (solved using Polynomial Method and Vector Space dimension): Size of a 2-distance set in R^n, maximum size of an L-intersecting family of sets, maximum size of a p-modular L-intersecting family of sets, maximum size of an L-intersecting k-uniform family of sets, maximum size of a p-modular L-intersecting k-uniform family of sets; (Hadwiger-Nelson problem in high dimensions, Borsuk Conjecture in high dimensions, Constructive Ramsey 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; 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.
  Linear Algebra. Multivariable polynomial encoding, Dimension of multivariable polynomial vector spaces over R and finite fields, principle of Multilinearization of polynomials (over finite field of order 2), Blokhius's technique for improving the dimension bound, Frankl-Wilson L-intersecting family theorems as a tool.
  

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


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


• 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 Due Wednesday, 3/26
    Questions? Ask on Canvas. Or, send email. Plus Office hours as announced above.
    HW solutions to be distributed in class.
    


• Weeks #10, #11, and #12 : 2 Spring breaks, and 4 Lectures.
  
  • Topics: Enumerative problems for Homomorphisms of graphs, Kahn's sharp bound on the number of independent sets in a regular bipartite graph.
    Linear Algebra Method. Eventown and Oddtown, using dot product of incidence vectors of sets to show their independence over the finite field of order 2, the diagonal criterion and the trianglular criterion for linear independence of polynomials, k-distance set, a bound on the size of a 2-distance set in R^n and how to improve this bound, the outline of the linear algebra/ dimension/ polynomial method and its variation. L-intersecting family of sets, Frankl-Wilson bound on the maximum size of an L-intersecting family on [n] with |L|=s, Multilinear Reduction principle, Frankl-Wilson bound on the maximum size of an L-intersecting family on [n] with |L|=s, Modular Frankl-Wilson: p-modular L-intersecting family of sets and a bound on its size, Applications of Frankl-Wilson Theorems to Ray-Chaudhuri-Wilson Theorem, Generalized Fisher Inequality, Chromatic Number of the Unit-distance graph in R^d, Counterexample to Borsuk conjecture (no proof), Constructive Ramsey graphs; Frankl-Furedi conjecture for L-intersecting family with L without 0, Snevily's Theorem for size of p-modular L-intersecting family, Ray-Chaudhuri-Wilson Theorem for size of L-intersecting k-uniform family of sets.
    [Comment: See below for some relevant supplemental readings.]
  • Lecture Notes: Outlines of lectures without all the details as discussed in the live classroom. Notes#11. Notes#12.
  • Homework:
    Follow the detailed instructions and rules for HWs given in the Course Information Handout.
    Homework #6 Due Monday 4/21 (earlier submission is encouraged)
    Questions? Ask on Canvas. Or, send email. Plus Office hours as announced above.
    
    

• 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.
• Regarding the Simonovits-Sos conjecture for triangle-intersecting family of graphs. You can look up the original paper by Chung et al. at Fan Chung, R.L. Graham, P. Frankl, and J.B. Shearer, J. Combin. Theory Ser. (A) 43 (1986), no. 1, 23--37. You can see that the proof they give in the paper is for n even. How can we modify the same argument to make it work for n odd?
  The Simonovits-Sos conjecture (along with some more general results) has been proved in David Ellis, Yuval,Filmus, and Ehud Friedgut, J of European Mathematical Society 14:3, 2012, 841–885 The techniques used are Fourier-analytic in nature.
• Regarding the problem of counting all homomorphisms, |Hom(G,H)|. See Galvin and Tetali's 2004 paper extending Kahn's Entropy based arguments.
• Regarding Alon's conjecture about counting the number of independent sets in a regular graph. See Yufei Zhao's extension of Kahn's result from bipartite regular graphs to all regular graphs.
• See a subtle use of blow-up of a graph to give a sharp construction for Long local search for a large bipartite subgraph.
• Regarding Bregman's bound on the permanent of a 0-1 matrix (and equivalently the number of perfect matchings in a bipartite graph). Read Radhakrishnan's Entropy based proof together with the connection between perfect matchings and the permanent.
• Regarding the connection between Entropy and classical inequalities like AM-GM, Cauchy-Schwartz, Holder, etc., (HW#5 problem#5) read the paper on Hypergraphs, Entropy and Inequalities.
• Here is an interesting simulation problem for you to think about. If you go through to the end, you will find a connection to Entropy!
  The overall question is "How can we simulate an unbiased coin flip using a biased coin? And what is the most efficient way of doing this?"
  Question 1: You are given a biased coin that comes up heads with some probability greater than 1/2. Can you come up with a procedure using this coin, so that the outcome of this procedure allows us to simulate an unbiased coin toss?
  Question 2: TBA. Think about Question 1 first and then ask me for the next question.
  Question 3: TBA. Think about Question 1-2 first.
  Question 4: TBA. Think about Question 1-3 first.
  Question 5: TBA. Think about Question 1-4 first.
  Question 6: TBA. Think about Question 1-5 first.
  
• Regarding the Linear Algebra Method.
  Start with the seminal Alon, Babai, Suzuki paper from 1991, and then look up the papers that cite it.
  Another worthwhile read is Snevily's 1994 paper.
  Also see this proof of Frankl-Furedi conjecture along the lines of our proof of Snevily's theorem: by Sankar and Vishwanathan 1999.
• Regarding the Hadwiger-Nelson unit-distance graph problem,
  see a basic introduction, and an overview of the recent improvement in the lower bound to 5.
  You can read the mathematical details of this improvement in De Grey's 2018 paper.
• How is the answer to the Chromatic number of the plane dependent on the which axioms we assume are true?
  See this fascinating paper by Shelah and Soifer from 2003.
  Reverse Mathematics is the field within mathematical logic that studies which axioms are essential for the proof of a theorem. Starting from a base axiom system that is strong enough to develop the definitions underlying a theory but not strong enough to prove the theory itself, we look for a minimal set of axioms to add to the base axioms so that theorem can be proved. In a sense, this shows the equivalence of the extended axiom system and the theorem (one implication is the usual proof of a theorem using axioms, while the other implication is the identification of axioms necessary for the proof of the theorem). If this intrigues you, then look up the book: J. Stillwell (2018), Reverse Mathematics, proofs from the inside out.
• In Math 553 you (possibly) saw a bit of spectral methods (methods based on eigenvalues and vectors of the matrices associated with a graph, such as the adjacency matrix and the Laplacian) and their applications to chromatic number, etc., but we won't have time do more of those methods in this course.
  However, here is a short, elegant and very famous application of these methods from 2019, that you can read and understand in 30 minutes, Hao Huang's resolution of the Sensitivity conjecture and a general overview of why this is such a big deal!
  How about a couple of elementary graph theory problems that can be solved elegantly using appropriate matrices and their properties:
  (1) Prove that the (45) edges of the complete graph on 10 vertices can not be covered by the (15 each) edges of three Petersen graphs. Tedious case analysis is not an acceptable proof here.
  (2) Does a given graph G on n vertices contain a triangle? We can check this by procedure that checks all possible triples for edges, for a total of (n choose 3) i.e. O(n^3) steps. Can you give a much faster procedure (say with O(n^(2.37)) steps)?

• 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