The early evolution of the H-free process

DOI10.1007/S00222-010-0247-XzbMATH Open1223.05270arXiv0908.0429OpenAlexW3104768492WikidataQ55969770 ScholiaQ55969770MaRDI QIDQ982189FDOQ982189

Tom Bohman, Peter Keevash

Publication date: 6 July 2010

Published in: Inventiones Mathematicae (Search for Journal in Brave)

Abstract: The H-free process, for some fixed graph H, is the random graph process defined by starting with an empty graph on n vertices and then adding edges one at a time, chosen uniformly at random subject to the constraint that no H subgraph is formed. Let G be the random maximal H-free graph obtained at the end of the process. When H is strictly 2-balanced, we show that for some c>0, with high probability as $noinfty$, the minimum degree in G is at least $c{n}^{1-(v_H-2)/(e_H-1)}(logn{)}^{1/(e_H-1)}$. This gives new lower bounds for the Tur'an numbers of certain bipartite graphs, such as the complete bipartite graphs $K_{r,r}$ with $rge5$. When H is a complete graph $K_s$ with $sge5$ we show that for some C>0, with high probability the independence number of G is at most $C{n}^{2/(s+1)}(logn{)}^{1-1/(e_H-1)}$. This gives new lower bounds for Ramsey numbers R(s,t) for fixed $sge5$ and t large. We also obtain new bounds for the independence number of G for other graphs H, including the case when H is a cycle. Our proofs use the differential equations method for random graph processes to analyse the evolution of the process, and give further information about the structure of the graphs obtained, including asymptotic formulae for a broad class of subgraph extension variables.

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

Recommendations

• Evolution of nucleons and hydrogen
• On the evolution of a primordial interstellar gas cloud
• hi_class background evolution, initial conditions and approximation schemes
• Cosmological hydrogen recombination: influence of resonance and electron scattering
• The evolution of the gaseous envelope around a newborn protostar
• Recent progress of the study of hydrodynamic evolution of gaseous stars
• scientific article; zbMATH DE number 3947847

zbMATH Keywords

random graph process

Mathematics Subject Classification ID

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

Cites Work

• On the structure of linear graphs
• Counting extensions
• Title not available (Why is that?)
• Title not available (Why is that?)
• The triangle-free process
• The Ramsey number R(3, t) has order of magnitude t²/log t
• On Graphs that do not Contain a Thomsen Graph
• A note on Ramsey numbers
• Asymptotic lower bounds for Ramsey functions
• Norm-graphs: Variations and applications
• New asymptotics for bipartite Turán numbers
• Title not available (Why is that?)
• An Upper Bound on Zarankiewicz' Problem
• Constrainted graph processes
• Title not available (Why is that?)
• On the size of a random maximal graph
• Random maximalH-free graphs
• Graph Theory and Probability. II
• A central limit theorem for decomposable random variables with applications to random graphs
• Random Graph Processes with Degree Restrictions
• An Elementary View of Euler's Summation Formula
• The independence number of graphs with a forbidden cycle and Ramsey numbers
• A note on odd cycle-complete graph Ramsey numbers
• Asymptotic bounds for some bipartite graph: Complete graph Ramsey numbers
• A note on regular Ramsey graphs
• Lower bounds for the size of random maximal \(H\)-free graphs
• A central limit theorem via differential equations
• On random greedy triangle packing
• Title not available (Why is that?)

Cited In (91)

• The bipartite \(K_{2,2}\)-free process and bipartite Ramsey number \(b(2, t)\)
• On off-diagonal ordered Ramsey numbers of nested matchings
• Large girth approximate Steiner triple systems
• The \(Q_2\)-free process in the hypercube
• Ramsey numbers and bipartite Ramsey numbers via quasi-random graphs
• Complete graphs and complete bipartite graphs without rainbow path
• The diamond-free process
• On the Lovász Theta Function for Independent Sets in Sparse Graphs
• Dense subgraphs in the \(H\)-free process
• Asymptotic improvements to the lower bound of certain bipartite Turán numbers
• Approximately strongly regular graphs
• Multicolor Ramsey numbers via pseudorandom graphs
• On the Random Greedy $F$-Free Hypergraph Process
• Counting extensions revisited
• Dynamic concentration of the triangle‐free process
• The Bohman-Frieze process near criticality
• Packing nearly optimal Ramsey \(R(3,t)\) graphs
• Ramsey numbers of \(K_3\) and \(K_{n,n}\)
• On the Method of Typical Bounded Differences
• On \(n\)-dependence
• The Final Size of theC₄-Free Process
• Ramsey-type results for semi-algebraic relations
• On a conjecture of Erdős on locally sparse Steiner triple systems
• The polynomial method over varieties
• Online Ramsey Numbers and the Subgraph Query Problem
• Off-diagonal hypergraph Ramsey numbers
• Turán and Ramsey Properties of Subcube Intersection Graphs
• Random maximalH-free graphs
• The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘)
• A note on regular Ramsey graphs
• A Ramsey-type result for geometric \(\ell\)-hypergraphs
• The independent neighborhoods process
• Multicolor Ramsey numbers for complete bipartite versus complete graphs
• Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques
• On the power of random greedy algorithms
• Ramsey, Paper, Scissors
• On the random greedy \(F\)-free hypergraph process
• A construction for clique-free pseudorandom graphs
• Hypergraph Ramsey numbers: tight cycles versus cliques
• When does the K₄‐free process stop?
• The Erdős-Hajnal hypergraph Ramsey problem
• The C_ℓ‐free process
• On a diagonal conjecture for classical Ramsey numbers
• Random triangle removal
• Triangle‐free subgraphs in the triangle‐free process
• The Reverse H‐free Process for Strictly 2‐Balanced Graphs
• A note on projective norm graphs
• Sparse Hypergraphs with Applications to Coding Theory
• A semi-algebraic version of Zarankiewicz's problem
• The sum-free process
• Bounds on Ramsey games via alterations
• Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers
• The Game Saturation Number of a Graph
• Separation Choosability and Dense Bipartite Induced Subgraphs
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• A note on the random greedy independent set algorithm
• Phase transitions in Ramsey-Turán theory
• On the Ramsey-Turán number with small \(s\)-independence number
• Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
• A sharp threshold for bootstrap percolation in a random hypergraph
• Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs
• An improved bound for the stepping-up lemma
• The Erdős-Hajnal conjecture for three colors and triangles
• A note on the Erdős-Hajnal hypergraph Ramsey problem
• Erdős-Hajnal conjecture for graphs with bounded VC-dimension
• Structure and colour in triangle-free graphs
• Semi-algebraic Ramsey numbers
• A note on multicolor Ramsey number of small odd cycles versus a large clique
• On Ramsey Size-Linear Graphs and Related Questions
• Independent set in \(k\)-claw-free graphs: conditional \(\chi \)-boundedness and the power of LP/SDP relaxations
• Title not available (Why is that?)
• Generating Random Networks Without Short Cycles
• Friendly bisections of random graphs
• Ramsey properties of semilinear graphs
• The Early Evolution of the Random Graph Process in Planar Graphs and Related Classes
• Ramsey numbers and the Zarankiewicz problem
• Turán numbers of several bipartite graphs
• Improved Bounds for the Ramsey Number of Tight Cycles Versus Cliques
• Maximum number of symmetric extensions in random graphs
• On off-diagonal ordered Ramsey numbers of nested matchings
• Clique minors in graphs with a forbidden subgraph
• The inertia bound is far from tight
• The asymptotics of \(r(4,t)\)
• Prominent examples of flip processes
• Ramsey-Turán problems with small independence numbers
• A gentle introduction to the differential equation method and dynamic concentration
• The Kőnig graph process
• \(d\)-connectivity of the random graph with restricted budget
• From flip processes to dynamical systems on graphons
• A note on pseudorandom Ramsey graphs
• Near-domination in graphs

This page was built for publication: The early evolution of the \(H\)-free process

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