Maximum induced forests in random graphs

2021/01/20 by Krivoshapko, Maria, Zhukovskii, Maksim · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2101.08190

Abstract

We prove that with high probability maximum sizes of induced forests in dense binomial random graphs are concentrated in two consecutive values.

Cited by

• Concentration of the maximum size of an induced subtree in moderately sparse random graphs

Related

• Maximum induced trees and forests of bounded degree in random graphs
• Maximum sparse induced subgraphs of the binomial random graph with given\n number of edges
• Concentration of the maximum size of an induced subtree in moderately sparse random graphs
• The maximum size of an induced forest in the binomial random graph
• Large induced trees in dense random graphs