Instructor: Hemanshu Kaul

Office: 234B, Engineering 1
Phone: (312) 567-3128
E-mail: kaul [at] math.iit.edu

Time: 11:25am, Monday & Wednesday.
Place: 241, Engineering 1 Bldg.

Office Hours: 1pm-2pm Monday and Wednesday, walk-ins, and by appointment. Emailed questions are also encouraged.

• Wednesday, 4/13 : HW#6 has been uploaded.


• Monday, 3/28 : HW#5 has been uploaded.
• Monday, 1/31 : HW#2 has been uploaded.
• Wednesday, 1/19 : HW#1 has been uploaded.


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

• Mid-term Exam: Wednesday, March 9th, In-class @11:25am and Take-home @1:30pm. Topics: The probabilistic method - lectures and HWs, and the Entropy lectures.
• Final Exam : May 3rd, Tuesday, 8am to 10am. Topics: All topics studied during the semester.

• Homework #1: Due Monday, 1/31. Solutions distributed in class on 2/7.
  
• Homework #2: Due Monday, 2/14. Solutions distributed in class on 2/14.
  
• Homework #3: Due Monday, 2/28. Solutions distributed in class on 3/2.
  
• Homework #4: Due Monday, 3/21. Solutions distributed in class on 3/28.
  
• Homework #5: Due Monday, 4/11. Solutions distributed in class on 4/13.
  
• Homework #6: Due Monday, 4/25. Solutions to be distributed in class on 4/25.
  

• Note : All Theorems/ Rules/ Properties/ Corollaries stated in the log below are proved in class unless stated otherwise.
  
  
• Monday, 1/10 : Probabilistic Method. Ramsey problem for graphs and its corresponding number, a bound on R(k,k) using existential proof, Hypergraph coloring.
• Wednesday, 1/12 : A theorem for 2-coloring hypergraphs, Intersecting family of sets, Erdos-Ko-Rado theorem and its probabilistic proof, Expectation and its linearity property, indicator random variables, Expected number of fixed points in a random permutation, using expectation to find a tournament with many Hamiltonian paths.
• Wednesday, 1/19 : Finding a bipartite subgraph with at least half the edges, Finding tournament with property S_k and computing how n grows asymptotically as a function of k, Using modification of a random set to find a large independent set in a graph in terms of n and average degree.
• Monday, 1/24 : Further discussion of the argument for finding a large independent set in a graph in terms of n and average degree, 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, Existence of a graph with high girth and high chromatic number.
• Wednesday, 1/26 : Introduction to Lovasz Local Lemma, Event mutually independent of a collection of other events, Dependency graph, (Symmetric) Lovasz Local Lemma, Applying LLL to the hypergraph coloring problem and its comparison to the basic result obtained earlier using the union bound, Using LLL for list coloring a graph with lists of limited overlap (bounded repetitions of a color in a neighborhood).
• Monday, 1/31 : Mutual Independence Principle, Using LLL to improve the lower bound for diagonal Ramsey numbers R(k,k), an application of LLL to find a independent set with at most one vertex from each part of a partition of the vertex set, the general form of LLL, and the asymmetric form of LLL with its application to frugal proper colorings of graphs.
• Wednesday, 2/2 : University closed.
• Monday, 2/7 : Frugal proper colorings of graphs and a result of Hind, Molly and Reed using asymmetric LLL, "almost always", Binomial random graph, Uniform random graph, Convex property, Conditions under which convex property almost always holds in G(n,p) iff it holds in G(n,m).
• Wednesday, 2/9 : 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, Threshold for appearance of a triangle in G(n,p).
• Monday, 2/14 : 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.
• Wednesday, 2/16 : Shannon Entropy, Entropy of a random variable with finite range, Binary entropy function, Interpretation of entropy as information content, Elementary properties of Entropy and conditional entropy, An application of Entropy function to bound the the number points in 3-space with given number of distinct projections on the 3 standard 2-spaces.
• Monday, 2/21 : An application of subadditivity to bounding the size of a set system in terms of binary entropy, Shearer's Lemma and its application to a bounding the size of a family of sets in terms of its projections on a given family of sets of coordinates, Applying the Theorem derived from Shearer's lemma to Intersecting family with pairwise intersection containing consecutive numbers.
• Wednesday, 2/22 : Applying the Theorem derived from Shearer's lemma to family of graphs with pairwise intersection containing a triangle, 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.
• Monday, 2/28 : The 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 Shearer's lemma and lower bound using a blow-up of H, Kahn and Schwarz's sharp bound on the number of independent sets in a regular bipartite graph.
• Wednesday, 3/2 : Proof for a sharp bound on the number of independent sets in a regular bipartite graph. Linear Algebra Method. Vector spaces over finite fields, vector spaces of (multivariable-) polynomials, dimension and spanning sets.
• Monday, 3/7 : Using dot product of incidence vectors of sets to show their independence over the finite field of order 2, the diagonal 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.
• Wednesday, 3/9 : Mid-term Exam.
• Monday, 3/21 : The improved bound for the the size of a 2-distance set in R^n, the outline of the linear algebra/ dimension/ polynomial method and its variation, Triangular criterion for linear independence, L-intersecting family of sets, Frankl-Wilson bound on the maximum size of an L-intersecting family on [n] with |L|=s.
• Wednesday, 3/23 : Frankl-Wilson bound on the maximum size of an L-intersecting family on [n] with |L|=s, p-modular L-intersecting family of sets and a bound on its size (exercise), Frankl-Furedi conjecture, Snevily's Theorem for L-intersecting family with L without 0 (no proof).
• Monday, 3/28 : Discussion of Mid-term Exam solutions and the distribution of scores.
• Wednesday, 3/30 : Snevily's Theorem for L-intersecting family with L without 0 (no proof), 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.
• Monday, 4/4 : Combinatorial Nullstellensatz. Number of roots of a multivariable polynomial, Combinatorial Nullstellensatz, Cauchy-Davenport Theorem on the size of A+B in terms of sizes of A and B, subsets of Z_p, Erdos-Heilbronn conjecture and its proof.
• Wednesday, 4/6 : Proof of the Combinatorial Nullstellensatz, Applications of C-N to graph theory - Alon-Friedland-Kalai theorem for finding a p-regular subgraph, Finding subgraphs with restricted degree sets, Shirazi-Verstraete result on finding a subgraph with degree of each vertex guaranteed to be outside a forbidden set.
• Monday, 4/11 : Special lecture by David Galvin (Notre Dame) on applications of Entropy Method to Bregman' s Theorem on permanent and its combinatorial extensions.
• Wednesday, 4/13 : Proof of Shirazi-Verstraete result on finding a subgraph with degree of each vertex guaranteed to be outside a forbidden set.
  Daniel Tietzer: Discrete Fourier-analytic proof of Roth's Theorem for 3-progressions: Given a long arithmetic progression P and a subset A of sufficient density, it is determined that either A contains sufficiently many length-3 progressions or there is a long progression P' contained in P in which A is more dense. Such a progression P' is detected by introducing a simple function f measuring the difference between the "expected" and "actual" number of 3-term progressions in A. If this difference is large, it is inferred that the convolution of f with itself, and therefore the discrete Fourier transform of f, has large l_p-norm. By partitioning P into long progressions on which the Fourier transform kernel is roughly constant, the magnitude of this lp-norm yields a large sum of f-values over one of these long progressions P'. This large sum of f-values yields the desired high density of A in P'.
  
• Monday, 4/18 :
  Gergely Balint: A Random Algorithm for finding Min-Cut: Abstract?
  Mary Fidler: A Simple 3/4 Approximation Algorithm for the Maximum Satisfiability Problem: The Maximum Satisfiability Problem (MAX-SAT) is to find the largest sum of weighted satisfied clauses. This problem is considered NP-Hard and because of this approximation algorithms are used. An algorithm is considered and alpha-approximation if it can produce an assignment which has at least alpha times the weight of the optimal solution. Yannakakis has developed a 3/4-Approximation Algorithm for the MAX-SAT. I will present a simpler 3/4-Approximation Algorithm established by Goemans and Williamson and a short overview of recent improvements.
  
• Wednesday, 4/20 :
  Christian Bang: New entropy-based proof for Kahn-Lovasz theorem: A new proof for the Kahn-Lovasz theorem (upper bound on the number of perfect matchings in terms of degree sequence) is presented. The proof is based on the methods of Radhakrishnan used to prove Bregman's theorem (Kahn-Lovasz for balance bipartite graphs.)
  Emma Turian: Hypergraph 2-coloring and the Lovasz Local Lemma : I will talk about the lopsided-dependency graph and the connection between the different versions of the Lovasz Local Lemma and the applications of this Lovasz Local Lemma when it comes to Hypergraph coloring.
  
• Monday, 4/25 :
  Cheng Chang: A Contribution to the Zarankiewicz problem: I will talk about the ways to solve the Zarankiewicz Problem - How many edges can have a graph of order n if it does not contain Ks,t?
  Michael Langman: Bounding Chromatic Number using Eigenvalues:R. L. Brooks first showed that the chromatic number of a simple connected graph can be bounded above by using the maximum degree of a graph. H.S. Wilf showed that Brooks' bound can be improved by using the largest eigenvalue of the adjacency matrix of a graph. Wilf's bound can be generalized to directed graphs. In this talk, I will provide a proof of Wilf's eigenvalue upper bound for the chromatic number of simple graphs and show how this result can be extended to directed graphs.
  
• Wednesday, 4/27 :
  Jinyu Huang: Constructive Proof of Lovasz Local Lemma: The Lovasz Local Lemma is a powerful tool to prove the existencce of combinatorial objects meeting a prescribed collection of criteria. In 1991, Beck gave a constructive method to convert the proofs of LLL into an efficient algorithm. We show the work of Beck by considering the problem of hypergraph two-coloring. In 2009, Moser improved the work of Beck to make almost all known applications of LLL algorithmic. The main part of the presentation is the central idea of Moser's method.
  James Williamson: Weighted Graph Homomorphisms :I will show that for any finite, n-regular, bipartite graph G and any finite graph H, the set of graph homomorphisms from G to H is maximum when G is a disjoint union of K_{n,n} 's. There will also be brief mention/discussion of the weighted version of this problem and its relationship with the framework of a system with "hard constraints".
  

• Wikipedia: Combinatorics
• Mathpages: Combinatorics
• Glossary of terms in combinatorics
• Dynamic Surveys in Combinatorics
• Combinatorics Information Pages
• Combinatorial Catalogues


• Mathworld : Graph Theory Dictionary
• Planet Math : Graph Theory
• Graph Theory with Applications by Bondy and Murty
• Graph Theory (4th ed.) by Diestel