Showing math.COShow all
3 papers · 1 filter
math.CO2024
Maximum induced trees and forests of bounded degree in random graphs
Margarita Akhmejanova, Vladislav Kozhevnikov, Maksim Zhukovskii
Asymptotic behaviour of maximum sizes of induced trees and forests has been studied extensively in last decades, though the overall picture is far from being complete. In this pape…
math.CO2023
The maximum size of an induced forest in the binomial random graph
Margarita Akhmejanova, Vladislav Kozhevnikov
The celebrated Frieze's result about the independence number of states that it is concentrated in an interval of size for all . We show…
math.CO2020
Large cycles in random generalized Johnson graphs
Vladislav Kozhevnikov, Andrey Raigorodskii, Maksim Zhukovskii
This paper studies thresholds in random generalized Johnson graphs for containing large cycles, i.e. cycles of variable length growing with the size of the graph. Thresholds are ob…