Methods in Discrete Applied Math

**Instructor:** Hemanshu Kaul

**Office:** 125C, Engineering 1

**Phone:** (312) 567-3128

**E-mail:** kaul [at] iit.edu

**Time:** 3:15pm, Tuesday & Thursday.

**Place:** 102, Engineering 1 Bldg.

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

|Course Information| |Advice| |Announcements| |Examinations| |Homework| |Class Log & Handouts| |Links|

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 (Hypergraph), Optimization problems on discrete structures, Sampling and counting discrete objects, etc.

The

Excellent advice by Doug West on how to write homework solutions for proof-based problems.

On a more abstract note, here is a discussion of Language and Grammar of Mathematics - which is what you are starting to learn in a course like this.

Excellent advice for math majors and graduate students, by Terry Tao, 2006 Fields medallist. Required reading.

*Thursday, 2/7*: Tentative date for Exam #1 has been announced below.*Tuesday, 1/22*: HW#1 has been uploaded.*Tuesday, 1/15*: Check this webpage regularly for homework assignments, announcements, etc.

*Mid-term Exam*: Tuesday, March 26th, In-class @3:15pm and Take-home @4:30pm. Topics: The probabilistic method - lectures and HWs, and the Entropy method - lectures and HW.*Final Exam*: May 8th, Wednesday, 2pm to 4pm. Topics: All topics studied during the semester.

**Homework #1:**Due Tuesday, February 5th Solutions distributed in class on 2/5.

**Homework #2:**Due Tuesday, 2/19. Solutions distributed in class on 2/19.

**Homework #3:**Due Thursday, 2/28. Solutions distributed in class on 2/28.

**Homework #4:**Due Thursday, 3/14. Solutions distributed in class on 3/14.

**Homework #5:**Due Tuesday, 4/9. Solutions distributed in class on 4/9.

**Homework #6:**Due Thursday, 4/25. Solutions distributed in class on 4/30.

*Note*: All Theorems/ Rules/ Properties/ Corollaries stated in the log below are proved in class unless stated otherwise.

*Tuesday, 1/15*: Probabilistic Method. Ramsey problem for graphs and its corresponding number, a bound on R(k,k) using existential proof, Hypergraph coloring, m(k) and its values for k=2 and k=3.*Thursday, 1/17*: 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.*Tuesday, 1/22*: 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.*Thursday, 1/24*: 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.*Tuesday, 1/29*: 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, Mutual Independence Principle, Using LLL for list coloring a graph with lists of limited overlap (bounded repetitions of a color in a neighborhood).*Thursday, 1/31*: 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.*Tuesday, 2/5*: 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) (no proof), For fixed p, almost every G(n,p) is connected.*Thursday, 2/7*: 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), Balanced graphs - definition and examples, Threshold for appearance of a fixed balanced subgraph in G(n,p).*Tuesday, 2/12*: 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.

Shannon Entropy, Entropy of a random variable with finite range, Binary entropy function, Interpretation of entropy as information content.*Thursday, 2/14*: Jensen's Inequality, 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,An application of subadditivity to bounding the size of a set system in terms of binary entropy, Shearer's Lemma.*Tuesday, 2/19*: 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, Applying the Theorem derived from Shearer's lemma to family of graphs with pairwise intersection containing a triangle.*Thursday, 2/21*: 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, 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 fractional edge cover number.*Tuesday, 2/26*: 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: lower bound using a blow-up of H and fractional independence number, Kahn's sharp bound on the number of independent sets in a regular bipartite graph, Proof for a sharp bound on the number of independent sets in a regular bipartite graph.*Thursday, 2/28*: 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, Eventown and Oddtown, using dot product of incidence vectors of sets to show their independence over the finite field of order 2.*Tuesday, 3/5*: 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, 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..*Thursday, 3/7*: Multilinear Reduction principle, 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), Snevily's Theorem for size of p-modular L-intersecting family.*Tuesday, 3/12*: Snevily's Theorem for L-intersecting family with L without 0 (no proof), Snevily's Theorem for size of p-modular L-intersecting family.*Thursday, 3/14*: Ray-Chaudhuri-Wilson Theorem for size of L-intersecting k-uniform family of sets. Overview of the Exam syllabus and Discussion of Projects.*Tuesday, 3/26*: Mid-term Exam.*Thursday, 3/28*: Combinatorial Nullstellensatz. Fundamental Theorem of Algebra, Number of roots of a multivariable polynomial, Total degree of a 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.*Tuesday, 4/2*: Discussion of Mid-term Exam solutions and the distribution of scores.*Thursday, 4/4*: Discussion of Mid-term Exam solutions. Erdos-Heilbronn conjecture and its proof, Applications of C-N to graph theory - Alon-Friedland-Kalai theorem for finding a p-regular subgraph.*Tuesday, 4/9*: 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/11*: Completion of Shirazi-Verstraete result on finding a subgraph with degree of each vertex guaranteed to be outside a forbidden set.

Markov Chain Monte Carlo. Fundamentals of Homogenous Discrete Time Markov Chains: Definition, Transition Matrix, Transition Graph, Ergodicity - Irreducible and Aperiodic, Stationary Distributions, Stationary Distribution for Ergodic MC, Reversible Distribution. Designing a HDTMC with uniform distribution as the stationary distribution.*Tuesday, 4/16*: Two methods for creating HDMTC - Gibbs sampler and Metropolis process - examples for Independent sets, proper q-colorings, etc. Relation between exact counting, exact sampling, approximate sampling (FPAUS) and approximate counting (FPRAS). How to set up a FPRAS using a FPAUS - examples from volume of convex body and counting matchings. Overview of the whole MCMC paradigm (through email).*Thursday, 4/18*:

Adam Rumpf - Coloring Nonuniform Hypergraphs: A New Algorithmic Approach to the General Lovasz Local Lemma : The Lovasz Local Lemma is a useful tool for making probabilistic arguments for the existence of certain structures, such as proper graph colorings, however it generally provides no help when it comes to actually developing such a structure. The first known method for converting the results of LLL into an efficient algorithm was developed by Beck in 1991, specifically applied to the problem of 2-coloring a uniform hypergraph in polynomial time. I will be discussing a 2000 paper by Czumaj and Scheideler that generalizes these results to nonuniform hypergraphs. I will give a detailed description of the algorithm developed by Czumaj and Scheideler, including how it differs from previous efforts, outlines of proofs of its validity, and extensions of it to more difficult problems. I will end by describing work that has taken place more recently.

Lujia Wang - On Counting Weighted Graph Homomorphisms : My talk is based on the work by David Galvin and Prasad Tetali. We've discussed about Kahn's theorem on the number of independent sets in an N-vertex d-regular bipartite graph. This actually is a special case of homomorphisms, Hom(G,H_ind), where H_ind is a two vertex graph with one edge between the two vertices and one loop. We are talking about more general results on the numbers of homomorphisms from G to general H. Similar bound will be proved using entropy methods and asymptotics of the logarithm of |Hom(G,H)| in terms of a parameter of H will be given.

*Tuesday, 4/23*:

Francisco Hernandez - Cardinality of 2 and Higher Distance Sets : This presentation focuses on an improved upper bound on the cardinality of a 2-distance set proved by Blokhuis in 1984. Using the polynomial method, this new bound is achieved by including additional linearly independent polynomials to the set. We then move on to give bounds on the cardinality of certain three and higher distance sets in different spaces.

Arturo Jurado - Propagation of Information in a Network : Graphs are used to model communication networks and in the study of epidemics. In particular we are interested in the time it takes for information to propagate from a single vertex throughout a finite network. The expected propagation time, E(n), is dependent on the number of vertices, the graph's topology and the probability of successful transmission between vertices. We will focus our attention on paths, stars and complete graphs. The propagation time of a given network may be optimized without increasing the number of edges.

*Thursday, 4/25*:

Christodoulos Mitillos - Improved Bounds on Coloring of Graphs : This paper by Sokol Ndreca, Aldo Procacci, Benedetto Scoppola (2011) has several improvements on upper bounds of special types of chromatic numbers for graphs, all of them using a recent, improved version of the Lovasz Local Lemma, by Bissacot et al. (2011). We will present the new formulation of the Lemma and the results pertaining to the chromatic numbers for acyclic, star and frugal colouring, relating to the maximum degree of the graph.

Sisi Zhang - Subgraphs of random graphs with specified degrees : If a graph is chosen uniformly at random from all the graphs with a given degree sequence, what can be said about its subgraphs? The same can be asked of bipartite graphs, equivalently 0-1 matrices. These questions have been studied by many people. In my report will provide a partial survey of the field, with emphasis on two general techniques: the method of switchings and the multidimensional saddle-point method.

*Tuesday, 4/30*:

Hongwei Jin - Algortithms for the Min-Cut problem : The project will discuss the Min-Cut problem, and introduce some classical algorithms on it. One of the algorithms is a random algorithm developed by Karger. The fundamental idea of this algorithm is "edge contraction". The probability of a successful contraction algorithm is 2/n, and the complexity of the algorithm is O(n^4 \log n), where n=|V(G)|. Based on the analysis of Karger's algorithm, an improved algorithm, Karger-Stein algorithm, will be introduced. The faster algorithm can find the Min-Cut within the probability larger than 2 \log 2 / \log n, thus the complexity of faster algorithm is O(n^2 \log n). The project will also show an example, whose simple graph has 200 vertices, to see the difference between Karger’s algorithm and Karger-Stein algorithm, coded in Python.

Trevor Vossberg - A Polynomial Approximation to the Matrix Permanent via Markov Chain Monte Carlo.: The permanent of a matrix has been studied for over two centuries and provides a generalization of problems in graph theory. Though an exact algorithm for computing the permanent is not possible unless P=NP, a recently discovered polynomial time algorithm approximation of the permanent for non-negative matrices is presented. This algorithm is derived by generalizing a previous method of sampling perfect matchings using a Markov Chain Monte Carlo method. Reductions of graph theoretic problems preserving the approximation result are also considered, providing polynomial time approximation algorithms for related questions.

*Thursday, 5/2*:

Zhefu Chen - Counting Independent sets up to tree threshold: We consider the problem of counting a given weighted independent set of a Graph. Our goal is to count weighted independent set I that is proportional l which is activity of graph. Indeed, an algorithm for sampling independent set can help us find a maximum independent set. In this project, we will use an efficient scheme to get the bound of l. The new regime improves maximum degree from 4 to 5 when, for approximate counting of uniformly weighted independent sets of a graph and other implication will also discussed by using the new regime.

Yunjiao Liu - Properly colored copies and rainbow copies of large graphs with small maximum degree: Let G be a graph on n vertices with maximum degree. We use the Lovász local lemma to show the following two results about colorings X of the edges of the complete graph K_n. If for each vertex v of K_n the coloring X assigns each color to at most (n-2)/(22.4 D^2) edges emanating from v (D is the max degree of G), then there is a copy of G in K_n which is properly edge-colored by X. If X assigns each color to at most n/(51 D^2) edges of K_n, the there is a copy of G in K_n such that each edge of G receives a different color from X.

- Wikipedia: Combinatorics
- Mathpages: Combinatorics
- Glossary of terms in combinatorics
- Dynamic Surveys in Combinatorics
- Combinatorics Information Pages
- Mathworld : Graph Theory Dictionary
- Planet Math : Graph Theory
- Graph Theory with Applications by Bondy and Murty
- Graph Theory (4th ed.) by Diestel