Instructor: Hemanshu Kaul

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

Time: 10am, Tuesday & Thursday.
Place: 106, Engineering 1 Bldg.

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

• Wednesday, 4/15 : Schedule for the project presentations has been announced below. Recall that each presentation is for 30-35 minutes. Also, your project report is due on Thursday, April 30th.


• Thursday, 4/9 : HW#5 has been announced. Its a bit longer than usual.


• Tuesday, 3/24 : The details for Mid-term exam are given below.
• Tuesday, 3/10 : Mid-term exam has been scheduled for 3/31, Tuesday. See below.
• Monday, 1/26 : Corrected HW#1 has been uploaded. Problem # 6 was incorrectly stated in the earlier version.
• Thursday, 1/22 : Check this webpage regularly for homework assignments, announcements, etc.

• Mid-term Exam: Tuesday, March 31st - In-class @10am; Take-home @11:15am. Topics: Probabilistic method, and Shannon Entropy as discussed in class and homework from 1/20 to 3/10 (inclusive of both dates).
• Final Exam : Monday, May 11th, 2pm-4pm. Topics: All topics studied during the semester.

• Note : All Theorems/ Rules/ Properties/ Corollaries stated in the log below are proved in class unless stated otherwise.
  
  
• Tuesday, 1/20 : Probabilistic Method. Ramsey problem for graphs and its corresponding number, a bound on R(k,k) using existential proof, Hypergraph coloring and a theorem for 2-coloring hypergraphs.
• Thursday, 1/22 : 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.
• Tuesday, 1/27 : 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, Finding a small dominating set in a graph in terms of n and minimum degree.
• Thursday, 1/29 : Markov inequality for non-negative discrete random variables, Existence of a graph with high girth and high chromatic number, Introduction to Lovasz Local Lemma.
• Tuesday, 2/3 : 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 with lists with limited overlap.
• Thursday, 2/5 : Mutual Independence Principle, Using LLL for list coloring an arbitrary graph with bounded repetitions of a color in a neighborhood, Using LLL to improve the lower bound for diagonal Ramsey numbers R(k,k).
• Tuesday, 2/10 : An application of LLL to find a independent set with atmost one vertex from each part of a partition of the vertex set, the general form of 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).
• Thursday, 2/12 : For fixed p, almost every G(n,p) is connected, Threshold function for a monotone graph property, Variance, Covariance and Chebyshev's inequality, Second Moment Method, Threshold for appearance of a triangle in G(n,p).
• Tuesday, 2/17 : Threshold for appearance of a triangle in G(n,p) (completed), Balanced graphs - definition and examples, Threshold for appearance of a fixed balanced subgraph in G(n,p).
• Thursday, 2/19 : Threshold for appearance of non-balanced subgraph, Why threshold for appearance non-balanced subgraph is not not the same as the threshold for a balanced subgraph with same number of vertices and edges, 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.
• Tuesday, 2/24 : 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, An application of subadditivity to extremal set theory, 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.
• Thursday, 2/26 : Applying the Theorem derived from Shearer's lemma to Intersecting family with pairwise intersection containing consecutive numbers, and 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, fractional independence number of a hypergraph.
• Tuesday, 3/3 : 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 the 0-1 integer programs, discussion of various definitions of "subhypergraphs", Set-up of 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.
• Thursday, 3/5 : 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, theorem and proof set-up for bounding the number of independent sets in a regular bipartite graph.
• Tuesday, 3/10 : Proof for a sharp bound on the number of independent sets in a regular bipartite graph. Discussion of HWs.
• Thursday, 3/12 : Linear Algebra Method. Vector spaces over finite fields, vector spaces of polynomials, dimension and spanning sets; 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 sharp bound on the size of a 2-distance set in R^n.
• Tuesday, 3/24 : The outline of the linear algebra/ 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.
• Thursday, 3/26 : p-modular L-intersecting family of sets and a bound on its size, Frankl-Furedi conjecture, Snevily's Theorem for L-intersecting family with L without 0 (no proof), Snevily's Theorem for size of p-modular L-intersecting family.
• Tuesday, 3/31 : Mid-term Exam.
• Thursday, 4/2 : Discussion of Mid-term Exam solutions.
• Tuesday, 4/7 : Ray-Chaudhuri-Wilson Theorem for size of L-intersecting K-uniform family of sets. 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.
• Thursday, 4/9 : Further discussion of Cauchy-Davenport Theorem, Erdos-Heilbronn conjecture and its proof, Proof of the Combinatorial Nullstellensatz.
• Tuesday, 4/14 : 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.
• Thursday, 4/16 : Finished the proof of Shirazi-Verstraete theorem. Markov Chain Monte Carlo. Overview of Homogenous Discrete time Markov Chains - Definition, Transition Matrix, Transition graph, Irreducibility, Aperiodicity, Stationary distribution, Ergodic MC has unique stationary distribution, Convergence of an ergodic MC distribution to stationary distribution under total variation norm, Reversible distribution and its relation to stationary distribution; Sampling using Markov Chain - MCMC.
• Tuesday, 4/21 : Lemma for creating Markov Chains with unique stationary distribution that is uniform over the state space, Gibbs sampler for creating Markov chain with given stationary distribution, Gibbs samplers for Independent sets in a graph, proper q-colorings of a graph, Metropolis process, Using MCMC for counting the state space, Ideas underlying estimation of the volume of a d-dimensional convex body.
• Thursday, 4/23 :
  Hannah Kolb: Information Broadcasting in Random Graphs
  Shaojie Tang: Propagation of Information in Social Networks
• Tuesday, 4/28 :
  Junghwan Shin: An approximation algorithm for MAX-SAT - Linear programming relaxation and Randomized rounding techniques
• Thursday, 4/30 :
  YoungJu Jo: A Constant Factor Approximation for the Single Sink Edge Installation Problem
  Jingran Liu: Ulam's Liar Game
  [after class]Joseph Srigiri: Approximating the Stochastic Knapsack Problem - The Benefit of Adaptivity
• Tuesday, 5/5 :
  Cory Knapp: Coloring Uniform Hypergraphs with Few Colors
  Hong Liu: On the Chromatic Number of Set Systems
• Thursday, 5/7 :
  Allen Flavell: Random Channel Assignment in the Plane
  Chris Mitillos: Algorithmic Aspects of the Lovasz Local Lemma