- Quiz 1 on August 31st, in class
- Quiz 2 on October 31st, in class

Top

Assignment 1 (Due September 7th, in class)

Assignment 2 (Due dates: Any 6 problems on each Wednesday, starting from Oct. 17th)

Assignment 3 Submit 6 problems each Wednesday, from either of the two assignments.

Problem set on probability Linear algebra problem set

- Aug 10: Graph theory: Introduction, simple results related to connectivity, characterization of bipartite graphs
- Aug 17: Bipartite graphs continued, degree-sum formula, Mantel's theorem, trees
- Aug 24: Eulerian graphs: characterization, directed graphs, tournaments
- Aug 29: Matchings: Definition, Maximum vs. maximal matching, augmenting path, Berge's theorem
- Aug 31: Bipartite matching, Hall's theorem
- Sept 5: König-Egerváry theorem, planar graphs: definition, Euler's formula
- Sept 7: Characterization of planar graphs, 6-coloring, Tutte's theorem for perfect matching
- Sept 12: Pigeonhole principle: applications including Chinese remainder theorem and Erdös-Szekeres theorem, permutations and combinations, counting with and without repetitions (Ref: Sections 1.1-1.3, 1.5, 1.6 of this book)
- Sept 18: Principle of inclusion-exclusion: Derangements, Euler's phi function, applications to counting
- Sept 19: Generating functions, partitions, recurrences: Fibonacci recurrence
- Sept 21: Regions in plane, Exponential generating functions: application to derangements
- Oct 3: Midsem discussion, linear recurrences with constant coefficients
- Oct 5: Linear recurrences continued, Catalan numbers, combinatorics of sets: largest pairwise non-intersecting family
- Oct 10: Sperner's theorem, Dilworth's theorem
- Oct 11: Groups: Definition, examples, basic properties, subgroups, cosets, Lagrange's theorem
- Oct 12: Cyclic groups, generating sets, permutation groups, Cayley's theorem, Permutations: cycle structure and sign of a permutation
- Oct 17: Permutations continued, normal subgroups, quotient groups, homomorphism
- Oct 24: Sylow's theorem (without proof), direct products and fundamental theorem of finite abelian groups (without proof), rings, integral domains, fields: definitions and examples
- Oct 26: Properties of finite fields, construction of finite fields from polynomial rings, vector spaces: definition, dimension, linear independence, basis
- Oct 30: Linear transformations, rank-nullity theorem
- Nov 2: Change of basis, elementary matrices, row echelon form, system of linear equations, determinant, inner product, Cauchy-Schwartz inequality (proof left as exercise), orthgonality, eigenvalues and eigenvectors, characteristic polynomial, eigenvalues and eigenvectors of real symmetric matrices
- Nov 7: Basic concepts, conditional probability and independence, Bayes' formula, random variables and expectation, linearity of expectation
- Nov 9: Discrete random variables: Bernoulli, binomial, negative binomial, geometric, poisson; variance
- Nov 13: Coupon collector's problem, Tail inequalities: Markov's and Chebyshev's inequalities, Probabilistic method: Lower bound on the maximum number of Hamiltonian paths in a tournament
- Nov 14: Chernoff bound, maximum likelihood estimate, continuous random variables: probability density function, uniform and normal random variables
- Nov 16: Entropy and error correcting codes: Entropy, noiseless coding theorem, rate of a code, noisy coding theorem for binary symmetric channel, simple examples: error correction by repetition, error detection using parity bits
- Nov 19: Error correcting codes continued:
[7,4] Hamming codes: encoding and parity check
matrices, distance, rate, linear codes, Singleton bound,
Reed-Solomon codes

Group actions: Burnside's lemma, application to counting 2-colorings of a chessboard (Ref) - Nov 20: Markov chains: Definition, irreducibility, aperiodicity, stationary distribution, Fundamental theorem of Markov chains (without proof), Example: Random walks on regular, undirected graphs (Ref)

An introduction to combinatorics by David Guichard

Algebra by Artin