Maximum induced forests in random graphs

DOI10.1016/J.DAM.2021.08.018MaRDI QIDQ2235276zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 21 October 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.08190

zbMATH Keywords

concentrationinduced forestinduced treerandom graph

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80)

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

Review text

The authors prove that the maximum size of an induced forest (i.e.\ a subgraph that is a forest) in an Erdős-Rényi graph \(G(n,p)\) is of size either \(\lfloor2\log_{1/(1-p)}(enp)+2+\varepsilon \rfloor\) or \(\lfloor2\log_{1/(1-p)}(enp)+3+\varepsilon \rfloor\) with high probability as \(n\to\infty\), when \(p\) is fixed, for some constant \(\varepsilon > 0\). The argument is a first moment computation for the higher bound, the lower bound being deduced from \textit{D. Kamaldinov} et al. [Discrete Math. 344, No. 2, Article ID 112205, 14 p. (2021; Zbl 1454.05111)], where the same concentration result is proven for the maximum size of an induced tree in \(G(n,p)\).

Recommendations

• On the order of the largest induced tree in a random graph
• Trees in random graphs
• Induced Forests in Regular Graphs with Large Girth
• Forests in random graphs
• scientific article; zbMATH DE number 4087713

Cites work

• A Remark on Stirling's Formula
• Amazing and aesthetic aspects of analysis
• Cliques in random graphs
• scientific article; zbMATH DE number 932179 (Why is no real title available?)
• scientific article; zbMATH DE number 3340110 (Why is no real title available?)
• Maximal induces trees in sparse random graphs
• Maximum sparse induced subgraphs of the binomial random graph with given number of edges
• On colouring random graphs
• On induced paths, holes and trees in random graphs
• On the order of the largest induced tree in a random graph

Cited in

(14)

• Maximal induces trees in sparse random graphs
• Indistinguishability of the components of random spanning forests
• On maximum induced forests in graphs
• Forests in random graphs
• The analysis of a prioritised probabilistic algorithm to find large induced forests in regular graphs with large girth
• Induced Forests in Regular Graphs with Large Girth
• scientific article; zbMATH DE number 4087713 (Why is no real title available?)
• Maximum induced forests in graphs of bounded treewidth
• MIP formulations for induced graph optimization problems: a tutorial
• Induced forests in some distance-regular graphs
• The maximum size of an induced forest in the binomial random graph
• Induced forests and trees in Erdős-Rényi random graph
• Maximum induced trees in sparse random graphs
• Maximum induced trees and forests of bounded degree in random graphs

This page was built for publication: Maximum induced forests in random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2235276)