Dense subgraphs in the H-free process

DOI10.1016/J.DISC.2011.08.008MaRDI QIDQ409409zbMATH OpenOpenAlexFDO

Authors Lutz Warnke

Publication date 13 April 2012

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

random graph processessmall subgraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Density (toughness, etc.) (05C42)

Abstract: The H-free process starts with the empty graph on n vertices and adds edges chosen uniformly at random, one at a time, subject to the condition that no copy of H is created, where H is some fixed graph. When H is strictly 2-balanced, we show that for some c,d>0, with high probability as $noinfty$, the final graph of the H-free process contains no subgraphs F on $v_{F}leq{n}^d$ vertices with maximum density $ma{x}_{JsubseteqF}{e}_J/v_{J}geqc$. This extends and generalizes results of Gerke and Makai for the C_3-free process.

Recommendations

• Dense subgraphs in random graphs
• The densest subgraph problem in sparse random graphs
• Dense subgraphs of power-law random graphs
• Subgraph counts for dense random graphs with specified degrees
• Subgraph distributions in dense random regular graphs
• On substructure densities of hypergraphs
• Subgraph densities in \(K_r\)-free graphs
• Subgraphs of dense random graphs with specified degrees
• Subgraph densities in hypergraphs
• The component structure of dense random subgraphs of the hypercube

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• 4-cycles at the triangle-free process
• Differential equations for random processes and random graphs
• No dense subgraphs appear in the triangle-free graph process
• On the size of a random maximal graph
• Random maximalH-free graphs
• Small subgraphs of random regular graphs
• The C_ℓ‐free process
• The early evolution of the \(H\)-free process
• The random planar graph process
• The triangle-free process
• Threshold functions for small subgraphs
• When does the \(K_{4}\)-free process stop?

Cited in

(13)

• Large girth approximate Steiner triple systems
• The \(Q_2\)-free process in the hypercube
• The diamond-free process
• No dense subgraphs appear in the triangle-free graph process
• Dynamic concentration of the triangle‐free process
• Random maximalH-free graphs
• Lower bounds for the size of random maximal \(H\)-free graphs
• On the random greedy \(F\)-free hypergraph process
• The C_ℓ‐free process
• \(d\)-connectivity of the random graph with restricted budget
• A note on the random greedy independent set algorithm
• When does the \(K_{4}\)-free process stop?
• The reverse \(H\)-free process for strictly 2-balanced graphs

This page was built for publication: Dense subgraphs in the \(H\)-free process

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