The triangle-free process

DOI10.1016/J.AIM.2009.02.018MaRDI QIDQ1023043zbMATH OpenOpenAlexWikidataFDO

Authors Tom Bohman

Publication date 10 June 2009

Published in Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Ramsey theoryrandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Generalized Ramsey theory (05C55) Stochastic processes (60G99)

Abstract: Consider the following stochastic graph process. We begin with the empty graph on n vertices and add edges one at a time, where each edge is chosen uniformly at random from the collection of potential edges that do not form triangles when added to the graph. The process terminates at a maximal traingle-free graph. Here we analyze the triangle-free process, determining the likely order of magnitude of the number of edges in the final graph. As a corollary we show that the triangle-free process is very likely to produce a Ramsey R(3,t) graph; that is, our analysis of the triangle-free process gives a new proof of the lower bound on R(3,t) previously established by Jeong Han Kim. The techniques introduced extend to the K_4-free process thereby establishing a small improvement in the best known lower bound on the Ramsey number R(4,t).

Recommendations

• Dynamic concentration of the triangle‐free process
• Dynamic concentration of the triangle-free process
• Triangle-free subgraphs in the triangle-free process
• The triangle-free process and the Ramsey number \(R(3,k)\)
• When does the \(K_{4}\)-free process stop?

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 1317271 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• A note on Ramsey numbers
• A note on regular Ramsey graphs
• A note on the independence number of triangle-free graphs. II
• Asymptotic lower bounds for Ramsey functions
• Birth control for giants
• Bounding Ramsey numbers through large deviation inequalities
• Constrainted graph processes
• Creating a Giant Component
• Explicit Ramsey graphs and orthonormal labelings
• Graph Theory and Probability. II
• Karp-Sipser on random graphs with a fixed degree sequence
• On the size of a random maximal graph
• Probability Inequalities for Sums of Bounded Random Variables
• Product rule wins a competitive game
• Random Graph Processes with Degree Restrictions
• Random maximalH-free graphs
• Some graph theoretic results associated with Ramsey's theorem
• The Ramsey number R(3, t) has order of magnitude t²/log t

Cited in

(74)

• The Early Evolution of the Random Graph Process in Planar Graphs and Related Classes
• \(d\)-connectivity of the random graph with restricted budget
• The \(\chi\)-Ramsey problem for triangle-free graphs
• Solution to a problem of Katona on counting cliques of weighted graphs
• scientific article; zbMATH DE number 1984539 (Why is no real title available?)
• Independent set in \(k\)-claw-free graphs: conditional \(\chi \)-boundedness and the power of LP/SDP relaxations
• scientific article; zbMATH DE number 1948235 (Why is no real title available?)
• On the random greedy linear uniform hypergraph packing
• The Kőnig graph process
• Greedy maximal independent sets via local limits
• Closing the random graph gap in Tuza's conjecture through the online triangle packing process
• Interview with Joel Spencer
• The C_ℓ‐free process
• Making an H $H$‐free graph k $k$‐colorable
• A natural barrier in random greedy hypergraph matching
• An approximate version of the tree packing conjecture
• Large triangle packings and Tuza's conjecture in sparse random graphs
• A note on the random greedy independent set algorithm
• A sequence of triangle-free pseudorandom graphs
• Semi-algebraic Ramsey numbers
• On the minimum degree of minimal Ramsey graphs for multiple colours
• Dynamic concentration of the triangle-free process
• Counting independent sets in triangle-free graphs
• Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques
• The bipartite \(K_{2,2}\)-free process and bipartite Ramsey number \(b(2, t)\)
• Coloring sparse hypergraphs
• On the power of random greedy algorithms
• Lower bounds for the size of random maximal \(H\)-free graphs
• On the method of typical bounded differences
• Ramsey numbers of \(K_3\) and \(K_{n,n}\)
• Online Ramsey numbers and the subgraph query problem
• Dynamic concentration of the triangle‐free process
• The Bohman-Frieze process near criticality
• A note on the random greedy triangle-packing algorithm
• Dense subgraphs in the \(H\)-free process
• A note on regular Ramsey graphs
• A Ramsey-type result for geometric \(\ell\)-hypergraphs
• 4-cycles at the triangle-free process
• The final size of the \(C_{4}\)-free process
• A sharp threshold for bootstrap percolation in a random hypergraph
• Free triangle orders
• A variant of the Erdős–Rényi random graph process
• Ramsey games with giants
• On the chromatic index of random uniform hypergraphs
• Ramsey, paper, scissors
• The early evolution of the \(H\)-free process
• Triangle-free subgraphs in the triangle-free process
• An upper bound on the extremal version of Hajnal's triangle-free game
• The triangle-free process and the Ramsey number \(R(3,k)\)
• Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs
• Random triangle removal
• The Erdős-Hajnal conjecture for three colors and triangles
• The independent neighborhoods process
• Packing nearly optimal Ramsey \(R(3,t)\) graphs
• Ramsey-type results for semi-algebraic relations
• Independence number of graphs with a prescribed number of cliques
• On some open questions for Ramsey and Folkman numbers
• A random triadic process
• On the random greedy \(F\)-free hypergraph process
• On the random greedy \(F\)-free hypergraph process
• A randomized construction of high girth regular graphs
• Hypergraph Ramsey numbers
• A gentle introduction to the differential equation method and dynamic concentration
• The reverse \(H\)-free process for strictly 2-balanced graphs
• The Erdős-Hajnal hypergraph Ramsey problem
• When does the \(K_{4}\)-free process stop?
• The \(Q_2\)-free process in the hypercube
• Large girth approximate Steiner triple systems
• A note on the Erdős-Hajnal hypergraph Ramsey problem
• A random triadic process
• The diamond-free process
• Largest components in random hypergraphs
• Off-diagonal hypergraph Ramsey numbers
• The sum-free process

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

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