Maksim
Zhukovskii
MIPT, Moscow
Research interests:
Random graphs, extremal combinatorics, descriptive complexity, model theory
zhukmax@gmail.com
Current position
Researcher since Jan 2020, Moscow Institute of Physics and Technology, Laboratory of Combinatorial and Geometric structures
Positions held
Associate Professor Sep 2014 - Jun 2022, Moscow Institute of Physics and Technology, Department of Discrete Mathematics
Reseacher May 2016 - Dec 2020, Moscow Institute of Physics and Technology, Laboratory of Advanced Combinatorics and Networks Applications
Researcher May 2011 - May 2017, Yandex Research
Junior Researcher May 2010 - Oct 2010, Sep 2012 - Oct 2014, Department of Math Statistics and Random Processes, Lomonosov Moscow State University, Mechanics and Mathematics Faculty
Assistant Prof, Sep 2010 - Aug 2014, Moscow Institute of Physics and Technology, Department of Discrete Mathematics
Visiting positions
Monash University, Australia, Melbourne, Nov - Dec 2019
Weizmann Institute of Science, Israel, Rehovot, Apr - Jul 2022
Tel Aviv University, Israel, Tel Aviv, Aug - Sep 2022
Other personal pages
Lab videos
Publications
Submitted papers
- Covering three-tori with cubes, 2021, preprint
- On anti-stochastic properties of unlabeled graphs, 2021, preprint
- Extremal independence in discrete random systems, 2021, preprint
- Large cycles in generalized Johnson graphs, 2022, preprint
Selected journal publications
- Weak saturation stability, European Journal of Combinatorics, to appear.
- Cycle saturation in random graphs, SIAM Journal on Discrete Mathematics, to appear.
- Spectrum of FO logic with quantifier depth 4 is finite, ACM Transactions on Computational Logic, to appear.
- EMSO(FO$^2$) 0-1 law fails for all dense random graphs, SIAM Journal on Discrete Mathematics, to appear.
- Zero-one laws for existential first order sentences of bounded quantifier depth, ACM Transactions on Computational Logic (2022) Vol 23 Issue 2, No:12 pp:1-27.
- Distribution of tree parameters by martingale approach, Combinatorics, Probability and Computing (2022) pp. 1-28.
- Existential monadic second order convergence law fails on sparse random graphs, European Journal of Combinatorics, 83 (2020).
- Zero-one laws for existential first order sentences of bounded quantifier depth, ACM Transactions on Computational Logic, to appear.
- Large cycles in random generalized Johnson graphs, Discrete Mathematics, 345:3 (2022) 112721.
- Threshold for weak saturation stability, Journal of Graph Theory, to appear.
- On the sizes of large subgraphs of the binomial random graph, Discrete Mathematics, 345:2 (2022) 112675.
- The distribution of the maximum number of common neighbors in the random graph, European Journal of Combinatorics, to appear.
- $\gamma$-variable first-order logic of uniform attachment random graphs, Discrete Mathematics, 345 (2022) 112802
- On a generalization of a Ramanujan conjecture for binomial random variables, Statistics & Probability Letters, 177, 2021, 109147.
- Maximum induced forests in random graphs, Discrete Applied Mathematics, 305, 2021, pp 211-213.
- Maximum sparse induced subgraphs of the binomial random graph with given number of edges, Discrete mathematics 34:2, 2021.
- MSO zero-one law for recursive random trees, Statistics & Probability Letters, 173, 2021, 109061.
- Logical laws for short existential monadic second order sentences about graphs, Journal of Mathematical Logic, Vol 2, No 2, 2020.
- Existential monadic second order convergence law fails on sparse random graphs, European Journal of Combinatorics, 83 (2020).
- Stochastic extreme value theory for triangular arrays of dependent random variables, Russian Mathematical Surveys 75:5, 2020, 968-970.
- First-order definitions of subgraph isomorphism through the adjacency and order relations, Moscow Journal of Combinatorics and Number Theory, 9:3, 2020, 293-302.
- Zero-one laws for k-variable first-order logic of sparse random graphs, Discrete Applied Mathematics 276, 2020, 121-128.
- Existential monadic second order logic of undirected graphs: a disproof of the Le Bars conjecture, Annals of Pure and Applied Logic, 170 (2019) 505-514.
- On the First-Order Complexity of Induced Subgraph Isomorphism, Logical Methods in Computer Science, Volume 15, Issue 1, 2019, 25:1-25:24.
- Tight bounds on the asymptotic descriptive complexity of subgraph isomorphism, ACM Transactions on Computational Logic, Volume 20, Issue 2, 2019.
- First order sentences about random graphs: small number of alternations, Discrete Applied Mathematics, 2018, 236: 329-346.
- On a connection of two graph-theoretic problems with conjectures of Ramanujan and Samuels, Russian Mathematical Surveys, 2018, Vol. 73:4, P. 173-174.
- Short monadic second order sentences about sparse random graphs, SIAM J Disc Math, 2018, Vol. 32, No. 4, P. 2916-2940.
- On the zero-one k-law extensions, European J. of Combinatorics, 60 (2017): 66-81.
- Monadic second-order properties of very sparse random graphs, Annals of pure and applied logic, 2017, Vol. 168, 2087-2101.
- Bounded quantifier depth spectra for random graphs, Discrete Mathematics, 2016, 339(6): 1651-1664.
- On infinite spectra of first order properties of random graphs, Moscow Journal of Combinatorics and Number Theory, 2016, Vol. 6, No. 4, 73-102.
- Random graphs: models and asymptotic characteristics, Russian Mathematical Surveys, 2015, Vol. 70, No 1, 33-81.
- The spectra of first-order formulae having low quantifier rank, Russian Mathematical Surveys, 2015, Vol. 70, No. 6, 1176-1178.
- The Law of Large Numbers for the Number of Active Particles in an Epidemic Model, Theory Probab. Appl., 58(2), 297–313, 2014.
- Zero-One k-Law, Discrete Mathematics, 2012, 312: 1670-1688.
- On a sequence of random distance graphs subject to the zero-one law, Problems of Information Transmission, 2011, 47(3): 251-268.
Invited plenary presentations
- Dagstuhl Seminar 22061: Logic and Random Discrete Structures, Dagstuhl, Germany, 2022
- International conference IPMCCC 2019, Tehran, Iran 2019
- International conference Net 2019, Moscow, Russia 2019
- 2nd Russian-Hungarian Combinatorial Workshop, Budapest, Hungary, 2018
- International conference GraphHPC 2017, Moscow, Russia, 2017
- International conference PMDM 2016, Petrozavodsk, Russia, 2016
- International conference Net 2016, Nizhniy Novgorod, Russia, 2016
- Workshop on Logic and Random Graphs, Leiden, the Netherlands, 2015
Refereed Conferences Publications
- On anti-stochastic properties of unlabeled graphs, 48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022)
- Covering three-tori with cubes, Trends in Mathematics Research Perspectives CRM Barcelona Vol. 14, Extended Abstracts EuroComb 2021, pp. 811--816
- Cycle saturation in random graphs, Trends in Mathematics Research Perspectives CRM Barcelona Vol. 14, Extended Abstracts EuroComb 2021, pp. 772--777
- Maximum induced subgraphs of the binomial random graph, Eurocomb 2019
- Supervised Nested PageRank, CIKM 2014
- Extension of the Zero-one k-law, Electronic Notes in Discrete Mathematics, 2013
- Fresh BrowseRank, SIGIR 2013
Prize for Young Mathematicians of Russia
August 13, 2021
Maksim Zhukovskii became one of the winners in the nomination "Young Scientists" of the first Prize for Young Mathematicians of Russia.
Learn more