Discrete Structures: Course Archive

Interactive Course Map

Course Program

Fall Semester: Basic Concepts

Fundamentals of Combinatorics

• Basic principles of combinatorics: addition rule, multiplication rule, pigeonhole principle, inclusion-exclusion formula. [VVV, §§4,13,131] [Sha, ch. 1]
• Arrangements, permutations and combinations. Newton’s binomial theorem, polynomial formula. Some identities with binomial coefficients. [VVV, §§5,19,20,23,24,33] [Sha, ch. 1]
• Estimates for factorials and binomial coefficients. Stirling’s formula (w/o proof). Notation \((c+o(1))^n\). Estimates for binomial coefficients of the form . Asymptotics for \(\binom{n}{k}\) when \(k=o(\sqrt{n})\). Estimates for \(\binom{n}{k}\) for larger \(k\). [GKP, §4.4 and ch. 9] [KLRSH, ch. 3]
• Möbius function. Möbius inversion formula. Application of Möbius inversion formula for counting cyclic sequences. [Sa, ch. 2 §3]
• Problems on partitions of numbers into summands. Ordered and unordered partitions. Recurrence formulas. Number of ordered partitions. Young diagrams. Euler’s theorems on equality of numbers of unordered partitions. Hardy-Ramanujan formula (w/o proof). [VVV, ch. 4]
• Linear recurrence relations with constant coefficients. 2nd order relations - with proof, higher order relations - formulation only. Fibonacci numbers. [VVV, §§94, 101-104]
• Power series and generating functions. Example of identity proven using power series. Theorems on convergence of power series (w/o proof). Catalan numbers. Finding sums involving binomial coefficients, Fibonacci numbers, etc. [VVV, ch. 8] [GKP, ch. 7]

Finite Algebraic Structures

• Algebraic structures: groups, fields. Axiomatics. Examples of finite and infinite groups and fields. [Any general algebra textbook] [KM, §1] [BB, §7.3, 7.5, 10.1]
• Cayley’s theorem on universality of permutation groups. Concepts of group action on a set and orbit of an element. Examples. [KM, §11, 12]
• Decomposition of a group by subgroup. Lagrange’s theorem. Sylow’s theorem on existence of subgroup of given order. [KM, §§2, 11.1] [BB, §§7.9-7.11]
• Burnside’s lemma. Redfield-Pólya enumeration theorem. [VVV, ch. 9]
• Irreducible polynomials: their properties and quantity. Construction of finite fields.

Basic Concepts of Graph and Hypergraph Theory

• Definition of graph, digraph, multigraph, pseudograph etc. Graph isomorphism. Independence number, clique number. [EMST, §§1,2,4,25,26,53]
• Paths in graphs. Hamiltonian and Eulerian cycles. Ore’s sufficient condition for existence of Hamiltonian cycle. Criterion for existence of Eulerian cycle. Fleury’s algorithm. Construction of De Bruijn sequences based on Eulerian cycles. [EMST, §§43,44] [RE, ch. 9]
• Graph coloring. Basic estimates of chromatic number and chromatic index. König’s theorem on chromatic index of bipartite graphs. Chromatic polynomial.
• Planar graphs. Minors. Wagner’s criterion. Five color theorem.
• Matchings in bipartite graphs. Hall’s theorem. Systems of distinct representatives, permanents.
• Concept of hypergraph. Analogues of graph terms for hypergraphs. Transversal sets (systems of common representatives). Greedy algorithm. Estimates of greedy cover size.

Spring Semester: Advanced Theorems, Probabilistic and Algebraic Methods

• Alon’s Combinatorial Nullstellensatz and some of its combinatorial consequences: Cauchy-Davenport theorem, theorem on covering cube vertices with planes, theorem on existence of regular subgraphs in almost regular graphs. [Al]
• Turán’s theorem on graph with given clique number and maximum number of edges. Turán problem analogue for bipartite graphs: Zarankiewicz problem. Solution of Zarankiewicz problem in special case for graphs without K2,2. Probabilistic lower bound for Zarankiewicz numbers.
• Ramsey theory. Ramsey numbers \(R(s,t)\): exact values for \(s=1,2\); Erdős-Szekeres upper bound, its corollary for diagonal Ramsey numbers; lower bound for diagonal numbers using simple probabilistic method. Ramsey theorem for hypergraphs (w/o proof). [AS, §3.1]
• Linear algebraic method: Frankl-Wilson theorem, constructive lower bound for Ramsey numbers. [RaL, ch. 5] [RaE, ch. 5]
• Lovász Local Lemma: symmetric and general cases. Refinement of lower bound for diagonal Ramsey numbers using it. Idea of lower bound for numbers \(R(s,3)\) [AS, §§5.1,5.3]
• Some applications of probabilistic method in graph theory. Erdős theorem on existence of graphs with arbitrarily large girth and chromatic number. Estimate of independence number. Estimate of crossing number.
• Partially ordered sets. Boolean lattice. Lubell-Yamamoto-Meshalkin and Sperner theorems on size of antichain in Boolean lattice. Decomposition of poset into chains and antichains. Derivation of Hall’s theorem from Dilworth’s theorem.
• \(t\)-intersecting hypergraphs. Erdős-Ko-Rado theorem. Ahlswede-Khachatrian theorem (without proof). Fisher’s theorem. [RaE, §10.1]
• Projections of families onto sets. Vapnik-Chervonenkis dimension. Upper bound on size of families with bounded VC-dimension. Upper bound on VC-dimension of shatterings. Haussler-Welzl theorem on \(\epsilon\)-nets for families with bounded VC-dimension (without proof) and its geometric corollary. [RaS, ch. 6]

Course Bibliography

• [AS] N. Alon, J. Spencer. The Probabilistic Method. — M.: Binom, 2007.
• [AZ] M. Aigner, G. Ziegler. Proofs from THE BOOK. — M.: Mir, 2006.
• [BB] G. Birkhoff, T. Bartee. Modern Applied Algebra. — M.: Mir, 1976.
• [VVV] N. Ya. Vilenkin, A. N. Vilenkin, P. A. Vilenkin. Combinatorics. — M: FIMA, MCCME, 2010.
• [GS] G. P. Gavrilov, A. A. Sapozhenko. Problems and Exercises in Discrete Mathematics. — M.: Fizmatlit, 2006.
• [GKP] R. Graham, D. Knuth, O. Patashnik. Concrete Mathematics. Foundation of Informatics. — M.: Binom. Laboratory of Knowledge, Mir, 2009.
• [EMST] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. Lectures on Graph Theory. — M.: Librokom, 2009.
• [KM] M. I. Kargapolov, Yu. I. Merzlyakov. Fundamentals of Group Theory. 3rd ed. — M.: Nauka, 1982.
• [CLRS] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Algorithms: Construction and Analysis. — M.: Williams, 2007.
• [RaV] A. M. Raigorodskii. Probability and Algebra in Combinatorics. — M.: MCCME, 2008.
• [RaL] A. M. Raigorodskii. Linear-Algebraic Method in Combinatorics. — M.: MCCME, 2007.
• [RaE] A. M. Raigorodskii. Extremal Problems in Graph Theory and Data Analysis. — M.-Izhevsk: Institute of Computer Research, 2008.
• [RaS] A. M. Raigorodskii. Systems of Common Representatives in Combinatorics and their Applications in Geometry. — M.: MCCME, 2009.
• [Sa] V. N. Sachkov. Introduction to Combinatorial Methods of Discrete Mathematics. — M.: MCCME, 2004.
• [Ha] F. Harary. Graph Theory. — M.: Mir, 1973.
• [Sha] A. Kh. Shakhmeister. Combinatorics. Statistics. Probability. — M.: MCCME, 2010.
• [Al] N. Alon. Combinatorial Nullstellensatz // Combinatorics, Probability and Computing. 8 (1999), pp. 7-29.
• [Ju] S. Jukna. Extremal Combinatorics (With Applications in Computer Science). — Springer, 2001.