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 and Thursday.

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

**Office Hours:** 4:35-5:35pm 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 (Hypergraphs), 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, 1/15*: Check this webpage regularly for homework assignments, announcements, etc.

*Mid-term Exam*: Tuesday, March 24th, 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*: Tuesday, May 5th, 2-4pm. Topics: All topics studied during the semester.

**Homework #1:**Due Thursday, January 29th Solutions distributed in class on 2/3.

**Homework #2:**Due Thursday, February 12th Solutions distributed in class on 2/12.

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

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

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

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

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

*Tuesday, 1/13*: Probabilistic Method. Pigeonhole principle, Ramsey problem for graphs and its corresponding number - notation for general graphs vs. complete graphs, Examples and motivation of Ramsey problem, General Ramsey number and its existence, Upper bound on R(p,q), Exact values for small R(p,q), lower bound vs.upper bound for Ramsey numbers.

**[Comment:**See Ramsey Theory Applications in this survey.**]***Thursday, 1/15*: A short intro to discrete probability spaces, and bounds for binomial coefficients, factorials, etc. Lower bound on R(k,k) using existential proof, Hypergraph coloring, m(k) and its values for k=2 and k=3, Fano plane, a theorem for 2-coloring hypergraphs using random coloring.*Tuesday, 1/20*: Intersecting family of sets, Erdos-Ko-Rado theorem and its probabilistic proof, Expectation and its linearity property, indicator random variables, Using expectation to find a tournament with many Hamiltonian paths, Finding a bipartite subgraph with at least half the edges (multiple proofs), Finding tournament with property S_k.*Thursday, 1/22*: 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, 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, Random graphs, Existence of a graph with high girth and high chromatic number.*Tuesday, 1/27*: 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, (Symmetric) Lovasz Local Lemma, Applying LLL to the hypergraph coloring problem and its comparison to the basic result obtained earlier using the union bound.*Thursday, 1/29*: Mutual Independence Principle, Using LLL for list coloring a graph with lists of limited overlap (bounded repetitions of a color in a neighborhood), Using LLL to improve the lower bound for diagonal Ramsey numbers R(k,k), the general form of LLL and its comparison with the symmetric LLL, the asymmetric form of LLL.*Tuesday, 2/3*: Frugal proper colorings of graphs and a result of Hind, Molly and Reed using asymmetric LLL, "almost always", Binomial random graph, Uniform random graph.*Thursday, 2/5*: 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, 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).*Tuesday, 2/10*: 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 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.*Thursday, 2/12*: Shannon Entropy, Entropy of a random variable with finite range, Binary entropy function, Interpretation of entropy as information content, 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.

**[Comment:**The wikipedia entry for (Shannon) Entropy gives a very nice overview, and it lists the particular properties that characterize this function. The textbook by McKay is highly recommended if you need more information. Theory of Information & Coding by Robert McEliece is also good classic text. We don't need any of these (or an in-depth study of Information complexity) for our course, this is simply for your pleasure.**]***Tuesday, 2/17*: An application of subadditivity to bounding the size of a set system in terms of binary entropy, Shearer's Lemma, 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.*Thursday, 2/19*: 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.

**[Comment:**The conjecture about size of family of graphs containing K_3 in its pairwise intersection was by Simonovits and Sos from 1976. Note that the conjectured bound is sharp for family with one K_3 in common. 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? Something to think about.

Regarding the Simonovits-Sos conjecture, it (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.**]***Tuesday, 2/24*: 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.*Thursday, 2/26*: 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. Reminder of Finite fields, multivariate polynomials, etc.*Tuesday, 3/3*: 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, the diagonal criterion for linear independence of polynomials, k-distance set, a bound on the size of a 2-distance set in R^n.*Thursday, 3/5*: 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, 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).*Tuesday, 3/10*: Frankl-Furedi conjecture and 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, Fundamental Theorem of Algebra, Number of roots of a non-zero multivariable polynomial.*Thursday, 3/12*: Combinatorial Nullstellensatz. Fundamental Theorem of Algebra, Number of roots of a non-zero 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.*Tuesday, 3/24*: Mid-term Exam.*Thursday, 3/26*: Erdos-Heilbronn conjecture and its proof, Applications of C-N to graph theory - Alon-Friedland-Kalai theorem for finding a p-regular subgraph.*Tuesday, 3/31*: 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/2*: Reminder of degree conditions for Combinatorial Nullstellensatz and why they are important in applications. Discussion of Mid-term Exam solutions and the distribution of scores.*Tuesday, 4/7*: 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. Lemma for Designing a HDTMC with uniform distribution as the stationary distribution.*Thursday, 4/9*: Two methods for creating HDMTC - Gibbs sampler and Metropolis process - Markov chains for sampling Independent sets, and proper q-colorings, and their ergodicity/ reversibility/ stationary distribution.*Tuesday, 4/14*: TV Distance between distributions and mixing time of MC, Definition of 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. Overview of the whole MCMC paradigm.*Thursday, 4/16*: Eigenvalues of the Transition matrix of an Ergodic, reversible MC, Spectral bounds on mixing time, Conductance and min-cut - bounds on second largest eigenvalue, Method of "canonical paths" and congestion and the corresponding bounds.*Tuesday, 4/21*: A toy example for the method of canonical paths and use of an injective encoding of paths in the analysis; How congestion can be bounded using properties of an injective encoding, Sampling Matchings of a graph - its MC using Gibbs sampler and the definition of the canonical paths.*Thursday, 4/23*: MCMC for Matchings of a graph - encodings of canoncical paths and how FPAUS becomes a FPRAS.*Thursday, 4/23*:

Dane Wilburne - Expander Graphs in Combinatorics: The goal of this project is to explore the important role that expander graphs play in the field of combinatorics. We discuss expansion in terms the edges of a graph and in terms its spectrum and present the famous Expander Mixing Lemma. The main connection to combinatorics that we highlight is the role of expanders in Markov Chain Monte Carlo methods. Specifically, we present and prove some basic results related to random walks on expander graphs.

James Panek - Defining and introducing binomial edge ideals of a simple graph: This project will explore the connection between graph theory and commutative algebra by defining, for a simple graph G, the binomial edge ideal, J_G; a set of polynomials over an arbitrary field in |2V(G)| variables generated by binomials that are based on the edge set of G. Several theorems and propositions will be shown to introduce relationships between G and J_G. For example, how do properties of ideals such as being prime or having a quadratic Grobner basis translate into a property of G.

*Tuesday, 4/28*:

Razan Tajeddine - Triangle-intersecting Families of Graphs: It has been conjectured by Simonovits and Sos that the size of the largest family of triangle intersecting graphs on n vertices is 1/8(2^(n \choose 2)), which is he size of the family of all graphs containing a fixed triangle. The most important advancement on this conjecture was made by Chung et al (1986) who proved by using entropy based arguments that the size of this family F is at most 1/4(2^(n \choose 2)). In this paper, David Ellis and Yuval Filmus (2012)p rove the conjecture for odd cycle intersecting families, and also odd cycle agreeing families. They use random graphs, with p in (0, 1/2) to measure the size of the family instead of using only the uniform measure on all subgraphs of K_n. They prove the theorem for p = 1/2 by proving the existence of an odd cycle Cayley operator with a spectrum having certain eigenvalues and spectral gap and using some properties of the Fourier transform, which will be the focus of my presentation.

Bo Yin - Approximation Algorithms for Maximum Satisfiability Problem: I plan to present several approximation algorithms which achieve certain performance guarantee by applying randomized rounding to solution to both linear and nonlinear relaxation of MAX SAT. After brief introduction of MAX SAT, a straightforward probabilistic method is reviewed. Then the application of randomized rounding to linear programming relaxation is presented, including a hybrid approach and its variants which are all 3/4-approximation. Following that, technique that randomly rounds the solution to nonlinear relaxation is presented which achieves an improved approximation.

Melinda Bulin - Testing Hypergraphs for Colorability by Different Methods: This presentation discusses different topics associated with hypergraph coloring. First, it will discuss the idea of testing for hypergraph colorability using property testing. Property testing is a process by which you may relax the decision making process on whether a graph is colorable by introducing a notion of being "far" or "near" to being colorable, then narrowing the search within those that are "near" to being colorable. Then, the type of hypergraph is narrowed to the subset that represent Steiner Quadruple Systems (SQS) and a new algorithm for finding a proper coloring is assessed.

*Thursday, 4/30*:

Benjamin Grimmer - Bounds on the Problem of Counting Graph Homomorphisms: Let G, H be two Graphs. We say f: V(G) -> V(H) is a homomorphism exactly when uv \in E(G) implies f(u)f(v) \in E(H). Many common graph theory problems can be described in terms of homomorphisms but computing the number of homomorphisms between two graphs is #P-complete. Following from this, we survey results giving upper and lower bounds on the number of homomorphisms between two graphs G and H. First, we show an extension of a result proven in class using entropy to the following: For any r-regular, bipartite graph G and any graph H, |Hom(G,H)| is maximized when G is a disjoint union of K_{r,r}'s. Second, we give extremal graphs for maximizing the number of homomorphisms when H is a K_2 with one looped vertex (independent set problem) and when H is a completely looped path of length two (the Widom-Rowlinson statistical physics model).

Todor Markov - Algebraic Constructions for Some Turan Numbers: The Turan Number ex(n,G) is the maximum number of edges a graph on n vertices can have while containing no subgraph isomorphic to G. I present constructions due to Furedi (based on Finite Projective geometry) that gives an asymptotic lower bound on ex(n,K_2,t), and a construction due to Kollar, Ronyai, and Szabo (based on normed graphs) for an asymptotic lower bound on ex(n,K_t,t!+1).

Haley Shopp - A Linear Algebraic Proof of a Conjecture of Frankl and Furedi: An overview of some of the techniques used in linear algebraic proofs used to bound sizes of intersecting families of subsets. This culminates in a proof of a conjecture of Frankl and Furedi about the bound on F when pairwise intersection between all pairs of sets is bounded by k.

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