Maksim Zhukovskii

Photo by zoom


MIPT, Moscow
Research interests:

Random graphs, extremal combinatorics, descriptive complexity, model theory

Positions held

Since Sep 2014: MIPT, Department of Discrete Mathematics, Associate Professor.
Since Jan 2020: MIPT, Laboratory of Combinatorial and Geometric Structures, Researcher.
Since May 2018: The Russian Presidential Academy of National Economy and Public Administration, Researcher.
Since Sep 2017: Caucasus mathematical center, Adyghe State University, Researcher.
May 2016 — Dec 2020: MIPT, Laboratory of advanced combinatorics and network applications, Researcher.
Jul 2016 — Nov 2017: RUDN University, Center of Mathematical modeling for interdisciplinary research, Researcher.
May 2011 — May 2017: Yandex, Researcher.
May 2010 — Oct 2014: Lomonosov Moscow State University, Department of Mathematical Statistics and Random Processes, Junior Researcher.
Sep 2010 — Aug 2014: Moscow Institute of Physics and Technology, Department of Discrete Mathematics, Assistant Professor.
May 2010 — Oct 2010: Lomonosov Moscow State University, Department of Mathematical Statistics and Random Processes, Junior Researcher.

Lab videos


Submitted papers

  1. Y. Demidovich, M. Zhukovskii
  2. M. Isaev, I. Rodionov, R. Zhang, M. Zhukovskii
  3. M. Akhmejanova, M. Zhukovskii
  4. O. Kalinichenko, M. Zhukovskii
  5. Yu. Demidovich, A. Skorkin, M. Zhukovskii

Selected journal publications

  1. A. Egorova, M. Zhukovskii,
  2. M. Isaev, A. Southwell, M. Zhukovskii
    Distribution of tree parameters by martingale approach, Combinatorics, Probability and Computing, to appear.
  3. M. Podder, M. Zhukovskii
    Zero-one laws for existential first order sentences of bounded quantifier depth, ACM Transactions on Computational Logic, to appear.
  4. V.S. Kozhevnikov, A.M. Raigorodskii, M.E. Zhukovskii
    Large cycles in random generalized Johnson graphs, Discrete Mathematics, to appear.
  5. M.R. Bidgoli, A. Mohammadian, B. Tayfeh-Rezaie, M. Zhukovskii
    Threshold for weak saturation stability, Journal of Graph Theory, to appear.
  6. Jozsef Balogh, Maksim Zhukovskii
  7. I.V. Rodionov, M.E. Zhukovskii
  8. Y. Malyshkin, M. Zhukovskii
  9. D. Dmitriev, M. Zhukovskii
    Maximum induced forests in random graphs, Discrete Applied Mathematics, 305, 2021, pp 211-213.
  10. M. Krivoshapko, M. Zhukovskii
    On a generalization of a Ramanujan conjecture for binomial random variables, Statistics & Probability Letters, 177, 2021, 109147, to appear.
  11. D. Kamaldinov, A. Skorkin, M. Zhukovskii
  12. Y. Malyshkin, M. Zhukovskii
    MSO zero-one law for recursive random trees, Statistics & Probability Letters, 173, 2021, 109061.
  13. M.E. Zhukovskii
  14. A. Egorova, M. Zhukovskii,
  15. R. Zhang, M.E. Zhukovskii, M.I. Isaev, I.V. Rodionov,
    Stochastic extreme value theory for triangular arrays of dependent random variables, Russian Mathematical Surveys 75:5, 2020, 968-970.
  16. O. Grigoryan, M. Makarov, M. Zhukovskii,
    First-order definitions of subgraph isomorphism through the adjacency and order relations, Moscow Journal of Combinatorics and Number Theory, 9:3, 2020, 293-302.
  17. A.S. Razafimahatratra, M. Zhukovskii,
    Zero-one laws for k-variable first-order logic of sparse random graphs, Discrete Applied Mathematics 276, 2020, 121-128.
  18. S.N. Popova, M.E. Zhukovskii,
  19. O. Verbitsky, M. Zhukovskii,
    On the First-Order Complexity of Induced Subgraph Isomorphism, Logical Methods in Computer Science, Volume 15, Issue 1, 2019, 25:1-25:24.
  20. O. Verbitsky, M. Zhukovskii,
    Tight bounds on the asymptotic descriptive complexity of subgraph isomorphism, ACM Transactions on Computational Logic, Volume 20, Issue 2, 2019.
  21. A.D. Matushkin, M.E. Zhukovskii,
    First order sentences about random graphs: small number of alternations, Discrete Applied Mathematics, 2018, 236: 329-346.
  22. D.I. Dmitriev, M.E. Zhukovskii,
    On a connection of two graph-theoretic problems with conjectures of Ramanujan and Samuels, Russian Mathematical Surveys, 2018, Vol. 73:4, P. 173-174.
  23. A. Kupavskii, M. Zhukovskii,
    Short monadic second order sentences about sparse random graphs, SIAM J Disc Math, 2018, Vol. 32, No. 4, P. 2916-2940.
  24. M.E. Zhukovskii,
    On the zero-one k-law extensions, European J. of Combinatorics, 60 (2017): 66-81.
  25. L.B. Ostrovsky, M.E. Zhukovskii,
    Monadic second-order properties of very sparse random graphs, Annals of pure and applied logic, 2017, Vol. 168, 2087-2101.
  26. J.H. Spencer, M.E. Zhukovskii,
    Bounded quantifier depth spectra for random graphs, Discrete Mathematics, 2016, 339(6): 1651-1664.
  27. M.E. Zhukovskii,
    On infinite spectra of first order properties of random graphs, Moscow Journal of Combinatorics and Number Theory, 2016, Vol. 6, No. 4, 73-102.
  28. M.E. Zhukovskii, A.M. Raigorodskii,
    Random graphs: models and asymptotic characteristics, Russian Mathematical Surveys, 2015, Vol. 70, No 1, 33-81.
  29. M.E. Zhukovskii,
    The spectra of first-order formulae having low quantifier rank, Russian Mathematical Surveys, 2015, Vol. 70, No. 6, 1176-1178.
  30. M.E. Zhukovskii,
  31. M.E. Zhukovskii,
    Zero-One k-Law, Discrete Mathematics, 2012, 312: 1670-1688.
  32. M.E. Zhukovskii,
    On a sequence of random distance graphs subject to the zero-one law, Problems of Information Transmission, 2011, 47(3): 251-268.


  1. I. Bogdanov, O. Grigoryan, M. Zhukovskii,
    Covering three-tori with cubes, Trends in Mathematics Research Perspectives CRM Barcelona Vol. 14, Extended Abstracts EuroComb 2021, pp. 811-816.
  2. Yu. Demidovich, M. Zhukovskii,
    Cycle saturation in random graphs, Trends in Mathematics Research Perspectives CRM Barcelona Vol. 14, Extended Abstracts EuroComb 2021, pp. 772-777.

Refereed Conferences Publications

  1. J. Balogh, M.E. Zhukovskii,
  2. O. Verbitsky, M. Zhukovskii,
  3. O. Verbitsky, M. Zhukovskii,
  4. Lev Bogolubsky, Pavel Dvurechensky, Alexander Gasnikov, Gleb Gusev, Yurii Nesterov, Andrei Raigorodskii, Aleksey Tikhonov, Maksim Zhukovskii,
  5. Maxim Zhukovskiy, Tsimafei Khatkevich, Gleb Gusev, Pavel Serdyukov,
  6. Maxim Zhukovskiy, Gleb Gusev, Pavel Serdyukov,
  7. M.E. Zhukovskii,
    Extension of the Zero-one k-law., Electronic Notes in Discrete Mathematics, 2013
  8. Maksim Zhukovskii, Gleb Gusev, Pavel Serdyukov,
  9. Maxim Zhukovskiy, Andrei Khropov, Gleb Gusev, Pavel Serdyukov,
  10. Maxim Zhukovskiy, Andrei Khropov, Gleb Gusev, and Pavel Serdyukov,
    Fresh BrowseRank., SIGIR 2013
  11. Maxim Zhukovskiy, Dmitry Vinogradov, Yuri Pritykin, Liudmila Ostroumova, Evgeny Grechnikov, Gleb Gusev, Pavel Serdyukov, Andrei Raigorodskii,
  12. Maxim Zhukovskiy, Dmitry Vinogradov, Gleb Gusev, Pavel Serdyukov, Andrei Raigorodskii,