When does the K₄-free process stop?

DOI10.1002/RSA.20444zbMATH Open1290.05134arXiv1007.3037OpenAlexW3101998289MaRDI QIDQ5415596FDOQ5415596

Authors: Lutz Warnke 

Publication date: 13 May 2014

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

Abstract: The K_4-free process starts with the empty graph on n vertices and at each step adds a new edge chosen uniformly at random from all remaining edges that do not complete a copy of K_4. Let G be the random maximal K_4-free graph obtained at the end of the process. We show that for some positive constant C, with high probability as $noinfty$, the maximum degree in G is at most $C{n}^{3/5}sqrt[5]logn$. This resolves a conjecture of Bohman and Keevash for the K_4-free process and improves on previous bounds obtained by Bollob'as and Riordan and by Osthus and Taraz. Combined with results of Bohman and Keevash this shows that with high probability G has $Theta(n^{8/5}sqrt[5]logn)$ edges and is `nearly regular', i.e., every vertex has degree $Theta(n^{3/5}sqrt[5]logn)$. This answers a question of ErdH{o}s, Suen and Winkler for the K_4-free process. We furthermore deduce an additional structural property: we show that whp the independence number of G is at least $Omega(n^{2/5}(logn{)}^{4/5}/loglogn)$, which matches an upper bound obtained by Bohman up to a factor of $Theta(loglogn)$. Our analysis of the K_4-free process also yields a new result in Ramsey theory: for a special case of a well-studied function introduced by ErdH{o}s and Rogers we slightly improve the best known upper bound.

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

Recommendations

• The final size of the \(C_{4}\)-free process
• Constrainted graph processes
• The triangle-free process
• The C_ℓ‐free process
• The early evolution of the \(H\)-free process

zbMATH Keywords

Ramsey theoryrandom graph process\(H\)-free process

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Generalized Ramsey theory (05C55)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• The triangle-free process
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Graphs without large triangle free subgraphs
• On the independence number of sparse graphs
• The Construction of Certain Graphs
• On \(K_s\)-free subgraphs in \(K_{s+k}\)-free graphs and vertex Folkman numbers
• 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
• Threshold Functions for Ramsey Properties
• A new lower bound for a Ramsey-type problem
• Large K_r‐free subgraphs in K_s‐free graphs and some other Ramsey‐type problems
• Bounding Ramsey numbers through large deviation inequalities
• Upper tails for subgraph counts in random graphs
• The deletion method for upper tail estimates
• Poisson approximation for large deviations
• The infamous upper tail
• 4-cycles at the triangle-free process
• Dense subgraphs in the \(H\)-free process
• No dense subgraphs appear in the triangle-free graph process
• Random Graph Processes with Degree Restrictions
• An Elementary View of Euler's Summation Formula
• Triangle-free subgraphs in the triangle-free process
• Lower bounds for the size of random maximal \(H\)-free graphs

Cited In (23)

• Large girth approximate Steiner triple systems
• The \(Q_2\)-free process in the hypercube
• The diamond-free process
• Dense subgraphs in the \(H\)-free process
• On the Random Greedy $F$-Free Hypergraph Process
• Dynamic concentration of the triangle‐free process
• \(K_4\)-free subgraphs of random graphs revisited
• Packing nearly optimal Ramsey \(R(3,t)\) graphs
• On the Method of Typical Bounded Differences
• On a conjecture of Erdős on locally sparse Steiner triple systems
• The triangle-free process
• The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘)
• On the missing log in upper tail estimates
• On the power of random greedy algorithms
• On the random greedy \(F\)-free hypergraph process
• Upper tails for arithmetic progressions in random subsets
• The sum-free process
• The jump of the clique chromatic number of random graphs
• A note on the random greedy independent set algorithm
• Greedy maximal independent sets via local limits
• The final size of the \(C_{4}\)-free process
• The reverse \(H\)-free process for strictly 2-balanced graphs
• Degree sequence and independence in \(K(4)\)-free graphs

This page was built for publication: When does the \(K_{4}\)-free process stop?

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