The diamond-free process

DOI10.1002/RSA.20517MaRDI QIDQ2930059zbMATH OpenOpenAlexFDO

Authors Michael E. Picollelli

Publication date 17 November 2014

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

diamond graphuniform random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: Let K_4^- denote the diamond graph, formed by removing an edge from the complete graph K_4. We consider the following random graph process: starting with n isolated vertices, add edges uniformly at random provided no such edge creates a copy of K_4^-. We show that, with probability tending to 1 as $noinfty$, the final size of the graph produced is $Theta(sqrtlog(n)cdot{n}^{3/2})$. Our analysis also suggests that the graph produced after i edges are added resembles the random graph, with the additional condition that the edges which do not lie on triangles form a random-looking subgraph.

Recommendations

• The final size of the \(C_{4}\)-free process
• Dense subgraphs in the H-free process
• When does the \(K_{4}\)-free process stop?
• No dense subgraphs appear in the triangle-free graph process
• Isolation of the diamond graph

Cites work

• Dense subgraphs in the H-free process
• Lower bounds for the size of random maximal H-free graphs
• No dense subgraphs appear in the triangle-free graph process
• On the size of a random maximal graph
• Random Graph Processes with Degree Restrictions
• Random maximalH-free graphs
• The early evolution of the \(H\)-free process
• The final size of the \(C_{4}\)-free process
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The triangle-free process
• Triangle-free subgraphs in the triangle-free process

Cited in

(13)

• Packing nearly optimal Ramsey R(3,t) graphs
• The bipartite \(K_{2,2}\)-free process and bipartite Ramsey number \(b(2, t)\)
• The sum-free process
• A note on the random greedy independent set algorithm
• The final size of the \(C_{4}\)-free process
• On the random greedy \(F\)-free hypergraph process
• On the random greedy F-free hypergraph process
• scientific article; zbMATH DE number 7640987 (Why is no real title available?)
• The reverse \(H\)-free process for strictly 2-balanced graphs
• Dynamic concentration of the triangle‐free process
• On some generalized vertex Folkman numbers
• From the Pearcey to the Airy process.
• Diamond-free families

This page was built for publication: The diamond-free process

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