Dynamic concentration of the triangle-free process
From MaRDI portal
Abstract: The triangle-free process begins with an empty graph on n vertices and iteratively adds edges chosen uniformly at random subject to the constraint that no triangle is formed. We determine the asymptotic number of edges in the maximal triangle-free graph at which the triangle-free process terminates. We also bound the independence number of this graph, which gives an improved lower bound on the Ramsey numbers R(3,t): we show R(3,t) > (1-o(1)) t^2 / (4 log t), which is within a 4+o(1) factor of the best known upper bound. Our improvement on previous analyses of this process exploits the self-correcting nature of key statistics of the process. Furthermore, we determine which bounded size subgraphs are likely to appear in the maximal triangle-free graph produced by the triangle-free process: they are precisely those triangle-free graphs with density at most 2.
Recommendations
Cited in
(51)- The triangle-free process
- The sharp threshold for making squares
- Cycles in triangle-free graphs of large chromatic number
- Saturation problems in the Ramsey theory of graphs, posets and point sets
- On Ramsey numbers \(R(K_4-e, K_t)\)
- Packing nearly optimal Ramsey R(3,t) graphs
- Bipartite induced density in triangle-free graphs
- The bipartite \(K_{2,2}\)-free process and bipartite Ramsey number \(b(2, t)\)
- The sum-free process
- Random triangle removal
- Phase transitions in Ramsey-Turán theory
- Independence number of graphs with a prescribed number of cliques
- Random cyclic triangle-free graphs of prime order
- A gentle introduction to the differential equation method and dynamic concentration
- Hypergraph Ramsey numbers: tight cycles versus cliques
- Coloring sparse hypergraphs
- 4-cycles at the triangle-free process
- On the minimum degree of minimal Ramsey graphs for multiple colours
- The independent neighborhoods process
- A small step forwards on the Erdős-Sós problem concerning the Ramsey numbers \(R(3, k)\)
- On the random greedy \(F\)-free hypergraph process
- On the random greedy F-free hypergraph process
- Lovász, vectors, graphs and codes
- Online Ramsey numbers and the subgraph query problem
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- The Kőnig graph process
- On the Ramsey-Turán number with small s-independence number
- scientific article; zbMATH DE number 1984539 (Why is no real title available?)
- On the average size of independent sets in triangle-free graphs
- Two Conjectures in Ramsey--Turán Theory
- Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers
- Balancing sums of random vectors
- On the size of a random maximal graph
- Generating random networks without short cycles
- Large triangle packings and Tuza's conjecture in sparse random graphs
- Ramsey numbers for nontrivial Berge cycles
- The -Ramsey problem for triangle-free graphs
- 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
- Improved Bounds for the Ramsey Number of Tight Cycles Versus Cliques
- Triangle-free subgraphs in the triangle-free process
- Counting Independent Sets in Hypergraphs
- On some open questions for Ramsey and Folkman numbers
- Ordered Ramsey numbers
- Combinatorics. Abstracts from the workshop held January 1--7, 2023
- Dynamic concentration of the triangle‐free process
- Occupancy fraction, fractional colouring, and triangle fraction
- On some generalized vertex Folkman numbers
- A note on pseudorandom Ramsey graphs
- Greedy maximal independent sets via local limits
This page was built for publication: Dynamic concentration of the triangle-free process
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5420011)
