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

Generalized Ramsey theory (05C55) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) 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

• 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
• 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?)
• 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

(87)

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