Maksim Zhukovskii

J. Comb. Theory B, 2025

On the maximum number of common neighbours in dense random regular graphs.

[BibT_eX]

[DOI]

Mikhail Isaev

Eur. J. Comb., 2025

Canonical Labeling of Sparse Random Graphs.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

2024

Spectrum of FO Logic with Quantifier Depth 4 is Finite.

[BibT_eX]

[DOI]

Yury Yarovikov

ACM Trans. Comput. Log., April, 2024

On vertex Ramsey graphs with forbidden subgraphs.

[BibT_eX]

[DOI]

Discret. Math., March, 2024

Maximum Number of Symmetric Extensions in Random Graphs.

[BibT_eX]

[DOI]

Stepan Vakhrushev

SIAM J. Discret. Math., 2024

On Isomorphism-Invariant Antistochastic Properties of Random Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2024

Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes.

[BibT_eX]

[DOI]

SIAM J. Comput., 2024

Maximum chordal subgraphs of random graphs.

[BibT_eX]

[DOI]

Michael Krivelevich

Comb. Probab. Comput., 2024

Functionality of Random Graphs.

[BibT_eX]

[DOI]

John Sylvester

Viktor Zamaraev

CoRR, 2024

Canonical labelling of sparse random graphs.

[BibT_eX]

[DOI]

CoRR, 2024

New bounds for the optimal density of covering single-insertion codes via the Turán density.

[BibT_eX]

[DOI]

Oleg Pikhurko

CoRR, 2024

Gathering Information about a Graph by Counting Walks from a Single Vertex.

[BibT_eX]

[DOI]

CoRR, 2024

Canonization of a Random Circulant Graph by Counting Walks.

[BibT_eX]

[DOI]

Proceedings of the WALCOM: Algorithms and Computation, 2024

First order distinguishability of sparse random graphs.

[BibT_eX]

[DOI]

Tal Hershko

Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

First order complexity of finite random structures.

[BibT_eX]

[DOI]

Danila Demin

Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

Tight Bounds on Adjacency Labels for Monotone Graph Classes.

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Large cycles in generalized Johnson graphs.

[BibT_eX]

[DOI]

Vladislav Kozhevnikov

J. Graph Theory, December, 2023

Weak saturation stability.

[BibT_eX]

[DOI]

O. Kalinichenko

Eur. J. Comb., December, 2023

Cycle Saturation in Random Graphs.

[BibT_eX]

[DOI]

Yury Demidovich

Arkadiy Skorkin

SIAM J. Discret. Math., September, 2023

Tight asymptotics of clique-chromatic numbers of dense random graphs.

[BibT_eX]

[DOI]

Yury Demidovich

J. Graph Theory, July, 2023

The distribution of the maximum number of common neighbors in the random graph.

[BibT_eX]

[DOI]

I. V. Rodionov

Eur. J. Comb., 2023

Tight concentration of star saturation number in random graphs.

[BibT_eX]

[DOI]

S. Demyanov

Discret. Math., 2023

Reconstruction of colours.

[BibT_eX]

[DOI]

Yury Demidovich

Yaroslav Panichkin

CoRR, 2023

Small But Unwieldy.

[BibT_eX]

[DOI]

CoRR, 2023

Canonization of a Random Graph by Two Matrix-Vector Multiplications.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs.

[BibT_eX]

[DOI]

Margarita Akhmejanova

SIAM J. Discret. Math., September, 2022

Zero-One Laws for Existential First-Order Sentences of Bounded Quantifier Depth.

[BibT_eX]

[DOI]

Moumanti Podder

ACM Trans. Comput. Log., 2022

<i>γ</i>-variable first-order logic of uniform attachment random graphs.

[BibT_eX]

[DOI]

Yury A. Malyshkin

Discret. Math., 2022

Large cycles in random generalized Johnson graphs.

[BibT_eX]

[DOI]

Vladislav Kozhevnikov

Andrei M. Raigorodskii

Discret. Math., 2022

On the sizes of large subgraphs of the binomial random graph.

[BibT_eX]

[DOI]

József Balogh

Discret. Math., 2022

Distribution of tree parameters by martingale approach.

[BibT_eX]

[DOI]

Mikhail Isaev

Angus Southwell

Comb. Probab. Comput., 2022

A very sharp threshold for first order logic distinguishability of random graphs.

[BibT_eX]

[DOI]

Itai Benjamini

CoRR, 2022

On Anti-stochastic Properties of Unlabeled Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2022

2021

Maximum sparse induced subgraphs of the binomial random graph with given number of edges.

[BibT_eX]

[DOI]

Dmitry Kamaldinov

Arkadiy Skorkin

Discret. Math., 2021

Maximum induced forests in random graphs.

[BibT_eX]

[DOI]

M. Krivoshapko

Discret. Appl. Math., 2021

2020

Logical laws for short existential monadic second-order sentences about graphs.

[BibT_eX]

[DOI]

J. Math. Log., 2020

Existential monadic second order convergence law fails on sparse random graphs.

[BibT_eX]

[DOI]

Alena Egorova

Andriaherimanana Sarobidy Razafimahatratra

Eur. J. Comb., 2020

Zero-one laws for k-variable first-order logic of sparse random graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2020

2019

Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2019

The Descriptive Complexity of Subgraph Isomorphism Without Numerics.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2019

On the First-Order Complexity of Induced Subgraph Isomorphism.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2019

Existential monadic second order logic of undirected graphs: The Le Bars conjecture is false.

[BibT_eX]

[DOI]

S. N. Popova

Ann. Pure Appl. Log., 2019

2018

Short Monadic Second Order Sentences about Sparse Random Graphs.

[BibT_eX]

[DOI]

Andrey Kupavskii

SIAM J. Discret. Math., 2018

First order sentences about random graphs: Small number of alternations.

[BibT_eX]

[DOI]

A. D. Matushkin

Discret. Appl. Math., 2018

2017

Quantifier Alternation in First-Order Formulas with Infinite Spectra.

[BibT_eX]

[DOI]

Probl. Inf. Transm., 2017

On the zero-one k-law extensions.

[BibT_eX]

[DOI]

Eur. J. Comb., 2017

Around power law for PageRank components in Buckley-Osthus model of web graph.

[BibT_eX]

[DOI]

Alexander V. Gasnikov

CoRR, 2017

Monadic second-order properties of very sparse random graphs.

[BibT_eX]

[DOI]

L. B. Ostrovsky

Ann. Pure Appl. Log., 2017

2016

Bounded quantifier depth spectra for random graphs.

[BibT_eX]

[DOI]

Joel H. Spencer

Discret. Math., 2016

The Descriptive Complexity of Subgraph Isomorphism in the Absence of Order.

[BibT_eX]

[DOI]

CoRR, 2016

Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods.

[BibT_eX]

[DOI]

Lev Bogolubsky

Pavel E. Dvurechensky

Alexander V. Gasnikov

Gleb Gusev

Yurii E. Nesterov

Andrei M. Raigorodskii

Aleksey Tikhonov

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

2013

Extension of the Zero-one k-law.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2013

URL Redirection Accounting for Improving Link-Based Ranking Methods.

[BibT_eX]

[DOI]

Gleb Gusev

Pavel Serdyukov

Proceedings of the Advances in Information Retrieval, 2013

2012

Zero-one k-law.

[BibT_eX]

[DOI]

Discret. Math., 2012

2011

On a sequence of random distance graphs subject to the zero-one law.

[BibT_eX]

[DOI]