Dense subgraphs in the H-free process

DOI10.1016/J.DISC.2011.08.008zbMATH Open1238.05253arXiv1003.0220OpenAlexW2055970774MaRDI QIDQ409409FDOQ409409

Lutz Warnke

Publication date: 13 April 2012

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Threshold functions for small subgraphs
• The triangle-free process
• Title not available (Why is that?)
• Title not available (Why is that?)
• The early evolution of the \(H\)-free process
• Differential equations for random processes and random graphs
• On the size of a random maximal graph
• Random maximalH-free graphs
• When does the K₄‐free process stop?
• The C_ℓ‐free process
• 4-cycles at the triangle-free process
• The random planar graph process
• No dense subgraphs appear in the triangle-free graph process
• Small subgraphs of random regular graphs

Cited In (11)

• 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
• When does the K₄‐free process stop?
• The C_ℓ‐free process
• The Reverse H‐free Process for Strictly 2‐Balanced Graphs
• \(d\)-connectivity of the random graph with restricted budget
• A note on the random greedy independent set algorithm

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)