Largest sparse subgraphs of random graphs

DOI10.1016/J.EJC.2013.06.012MaRDI QIDQ2509750zbMATH OpenOpenAlexFDO

Authors Nikolaos Fountoulakis, Ross J. Kang, Colin McDiarmid

Publication date 29 July 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75) Random graphs (graph-theoretic aspects) (05C80)

Abstract: For the ErdH{o}s-R'enyi random graph G(n,p), we give a precise asymptotic formula for the size of a largest vertex subset in G(n,p) that induces a subgraph with average degree at most t, provided that p = p(n) is not too small and t = t(n) is not too large. In the case of fixed t and p, we find that this value is asymptotically almost surely concentrated on at most two explicitly given points. This generalises a result on the independence number of random graphs. For both the upper and lower bounds, we rely on large deviations inequalities for the binomial distribution.

Recommendations

• Largest sparse subgraphs of random graphs
• Maximum sparse induced subgraphs of the binomial random graph with given number of edges
• scientific article; zbMATH DE number 568829
• Independent sets in random sparse graphs
• The densest subgraph problem in sparse random graphs

Cites work

• Cliques in random graphs
• scientific article; zbMATH DE number 3825706 (Why is no real title available?)
• scientific article; zbMATH DE number 1158743 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3333197 (Why is no real title available?)
• On colouring random graphs
• Random graphs.
• Range of values of the entropy of hereditary classes of graphs
• The \(t\)-improper chromatic number of random graphs
• The \(t\)-stability number of a random graph
• The \textsc{max quasi-independent set} problem
• The structure of hereditary properties and colourings of random graphs
• The t-improper chromatic number of random graphs

Cited in

(14)

• Dense subgraphs in random graphs
• Maximum sparse induced subgraphs of the binomial random graph with given number of edges
• The size of a maximum subgraph of the random graph with a given number of edges
• The densest subgraph problem in sparse random graphs
• On the sizes of large subgraphs of the binomial random graph
• Largest sparse subgraphs of random graphs
• Random Subgraphs in Sparse Graphs
• The Largest Eigenvalue of Sparse Random Graphs
• Induced forests and trees in Erdős-Rényi random graph
• Maximum induced trees in sparse random graphs
• Maximum induced subgraphs of the binomial random graph
• Maximum induced trees and forests of bounded degree in random graphs
• Variance of the subgraph count for sparse Erdős-Rényi graphs
• The \(t\)-stability number of a random graph

This page was built for publication: Largest sparse subgraphs of random graphs

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