Discrete Analysis 1

Published

18 October 2026

Passport

  • Where and when. Semester III of the 01.03.02 “Applied Mathematics and Informatics” program, “Mathematics” track, 2025 intake. In the official curriculum the discipline is listed as a single year-long course, “Discrete Analysis”.
  • Workload. 90 hours, 2 credits: 60 contact hours (30 lecture hours and 30 seminar hours) and 30 hours of independent work.
  • Department. Department of Discrete Mathematics.
  • Lecturer. The published FPMI fall 2022 program does not name the lecturer. In the old 2017/18 version the lecturer was A. M. Raigorodskii; this is historical information, not data on the current stream.
  • Final assessment. The form of the interim assessment for semester III should be checked in the current curriculum and timetable.

Contents of the published program

The title “Discrete Analysis 1” is this site’s editorial division; below is the complete list of the main (pass/fail test, or zachet) questions from the FPMI fall 2022 program for 2nd-year Applied Mathematics and Informatics students, Informatics track. The document also contains 16 separate questions “for an excellent grade”; they are listed after the main program.

  1. Graphs with loops and multiple edges, digraphs, the handshaking lemma, paths, cycles and criteria for Eulerian graphs.
  2. De Bruijn sequences and graphs; the binary alphabet, subwords and the “0 is better than 1” rule.
  3. Plane and planar graphs, Euler’s formula, non-planar graphs and the Pontryagin–Kuratowski criterion.
  4. Hamiltonian paths and cycles, Dirac’s sufficient condition.
  5. The chromatic number, the independence number and the clique number, relations between them.
  6. Turán’s theorem, the asymptotics of the maximum number of edges without \(k\)-cliques and its refinement for the distance graph.
  7. Estimates of factorials and binomial coefficients, Stirling’s formula and the asymptotics of the central binomial coefficient.
  8. The asymptotics of \(\ln n!\) and \(\sqrt[n]{n!}\) without Stirling’s formula.
  9. Asymptotic estimates of binomial and multinomial coefficients.
  10. The asymptotics of \(\binom nk\) for \(k^2=o(n)\) and for large \(k\).
  11. Random graphs, Markov’s and Chebyshev’s inequalities, random walk.
  12. Connectivity of a random graph for \(p=c\ln n/n\), the giant component.
  13. Bollobás’s theorems on the chromatic number of a random graph and special regimes of \(p\).
  14. Comparison of bounds on the chromatic number via the clique number and the independence number.
  15. Kneser graphs, bounds on the chromatic and clique numbers, independent sets.
  16. Lovász’s theorem on the chromatic number of the Kneser graph.
  17. Intersecting hypergraphs and the Erdős–Ko–Rado theorem.
  18. Subsequent generalizations: the theorems of Frankl, Wilson and Ahlswede–Khachatrian.
  19. The quantity \(m(n,k,t)\), the exact value of \(m(n,3,1)\) and the linear-algebraic bound.
  20. The bound on \(m(n,5,2)\) and its asymptotic sharpness.
  21. The Frankl–Wilson theorem for \(m(n,k,k-p)\) with \(k<2p\).
  22. The chromatic number of space and its relation to distance graphs.

Questions “for an excellent grade” in the 2022 program

  1. The exact formula and asymptotics for the number of unicyclic graphs.
  2. The graph isomorphism problem and an algorithm that works on almost all graphs.
  3. Connectivity of a random graph for \(p=c\ln n/n\), \(c>1\).
  4. Deviations of Lipschitz random variables and Bollobás’s theorem for \(p=n^{-\alpha}\).
  5. Another derivation of Bollobás’s theorem for \(p=n^{-\alpha}\).
  6. Edge deviations and a technical estimate for Bollobás’s theorem for \(p=1/2\).
  7. The full version of Bollobás’s theorem for \(p=1/2\).
  8. Accuracy of the greedy coloring of a random graph and Kučera’s theorem.
  9. Erdős’s theorem on a graph with large girth and large chromatic number.
  10. The Borsuk–Ulam–Lyusternik–Schnirelmann theorem and Lovász’s theorem.
  11. Special cases of the Borsuk–Ulam–Lyusternik–Schnirelmann theorem for closed sets.
  12. The Frankl–Wilson theorem for \(k\geq2p\).
  13. Sharpness of the Frankl–Wilson theorems, the quantity \(h(n,k,t)\), the connection with coding and Rödl’s theorem.
  14. An exponential lower bound on the chromatic number of space.
  15. Borsuk’s problem on the line and in the plane.
  16. An exponential lower bound on the Borsuk number.

Grading

The fall 2022 program publishes the rules of the pass/fail test (zachet); this is a historical grading scheme, not a guarantee for the 2025 intake. The seminar grade \(S\) ranges from 0 to 10. The zachet grade \(E\) ranges from 2 to 10; if \(E=2\), the final grade is immediately 2, otherwise \(I=0.5S+0.5E\), rounded to the nearest integer, with halves rounded up.

Each exam card contained two theory questions and a problem, 18 points in total, with 100 minutes allowed for the answer. After the first part: up to 7 points gives \(E_1=2\), 8–9 gives 3, 10–11 gives 4, 12–14 gives 5, 15–16 gives 6, 17–18 gives 7. With 15–18 points one could take an additional question “for an excellent grade” and receive \(E_2\) from 0 to 3; then \(E=E_1+E_2\).

Sources and currency

Program and pass/fail test rules, Applied Mathematics and Informatics (Informatics track), fall 2022, page of this program, archived 2017/18 version, 01.03.02 curriculum, 2025 intake.