Discrete Analysis 2

Published

18 October 2026

Passport

  • Where and when. Semester IV of the 01.03.02 β€œApplied Mathematics and Informatics” program, β€œMathematics” track, 2025 intake. This is the second semester of the single year-long course β€œDiscrete Analysis”.
  • Workload. 135 hours, 3 credits: 60 contact hours (30 lecture hours and 30 seminar hours), 45 hours of independent work and 30 hours for exam preparation and the exam itself.
  • Department. Department of Discrete Mathematics.
  • Lecturers. The available 2022/23 program names A. M. Raigorodskii, D.Sc. (Phys.-Math.), and D. G. Ilyinsky, Cand.Sc. (Econ.). This is information from a historical program, not confirmation of the current group assignments.
  • Final assessment. Exam in semester IV according to the curriculum for the 2025 intake.

Contents of the published program

The department publishes the spring 2022/23 program β€œDiscrete Analysis” but does not call it β€œ2”. Below is the complete topic list of this document; it belongs to a historical version of the course and is not presented as the 2025 program.

  1. Estimates of factorials and binomial coefficients.
  2. Graphs, digraphs, multigraphs and pseudographs; trees, Cayley’s formula and unicyclic graphs.
  3. Walks, trails and cycles; Eulerian graphs and digraphs.
  4. Hamiltonian paths and cycles, Dirac’s condition, connectivity and the independence number.
  5. De Bruijn sequences and graphs.
  6. Plane and planar graphs, Euler’s formula.
  7. Random graphs and their connectivity.
  8. The chromatic number, the clique number and the independence number; BollobΓ‘s’s theorems.
  9. Greedy construction of an independent set and ErdΕ‘s’s theorem on large girth and chromatic number.
  10. Hypergraphs, the ErdΕ‘s–Ko–Rado theorem and the intersection graph.
  11. The quantity \(m(n,k,t)\) and the Frankl–Wilson theorem.
  12. The chromatic number of space and its lower bound.
  13. Independent sets, cliques and TurΓ‘n’s theorem.
  14. The Kneser graph and LovΓ‘sz’s theorem.
  15. Ramsey theory, the probabilistic method, the LovΓ‘sz local lemma and the Frankl–Wilson bound.
  16. Multicolor and bipartite Ramsey numbers.
  17. Systems of common representatives and the greedy upper bound.
  18. Systems of common representatives in geometry, the Vapnik–Chervonenkis dimension, \(\varepsilon\)-nets and applications in statistics.
  19. The chromatic number of a hypergraph and the problem of the minimum number of edges.
  20. Borsuk’s problem.

Reading list in the 2022/23 program

N. Alon and J. Spencer, The Probabilistic Method; R. Graham, Rudiments of Ramsey Theory; A. M. Raigorodskii, The Linear-Algebraic Method in Combinatorics and Models of Random Graphs and Their Applications; A. M. Raigorodskii, Systems of Common Representatives in Combinatorics and Their Applications in Geometry; F. Harary, Graph Theory; S. Jukna, Extremal Combinatorics With Applications in Computer Science; B. BollobΓ‘s, Random Graphs; A. A. Glibichuk, A. B. Dainiak, D. G. Ilyinsky et al., Elements of Discrete Mathematics in Problems.

Grading

No current, publicly available grading scheme was found for this version of the course.

Sources and currency

Spring 2022/23 program, department course page, 01.03.02 curriculum, 2025 intake.