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
(50)- Ordered Ramsey numbers
- The bipartite \(K_{2,2}\)-free process and bipartite Ramsey number \(b(2, t)\)
- Coloring sparse hypergraphs
- Large girth approximate Steiner triple systems
- Online Ramsey numbers and the subgraph query problem
- Occupancy fraction, fractional colouring, and triangle fraction
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Cycles in triangle-free graphs of large chromatic number
- Ramsey numbers for nontrivial Berge cycles
- scientific article; zbMATH DE number 1984539 (Why is no real title available?)
- Dynamic concentration of the triangle‐free process
- Packing nearly optimal Ramsey R(3,t) graphs
- Bipartite induced density in triangle-free graphs
- On the minimum degree of minimal Ramsey graphs for multiple colours
- The triangle-free process
- The -Ramsey problem for triangle-free graphs
- Saturation problems in the Ramsey theory of graphs, posets and point sets
- On some open questions for Ramsey and Folkman numbers
- The sharp threshold for making squares
- Counting Independent Sets in Hypergraphs
- The independent neighborhoods process
- Improved Bounds for the Ramsey Number of Tight Cycles Versus Cliques
- On the random greedy F-free hypergraph process
- On the random greedy \(F\)-free hypergraph process
- On Ramsey numbers \(R(K_4-e, K_t)\)
- On the average size of independent sets in triangle-free graphs
- Hypergraph Ramsey numbers: tight cycles versus cliques
- Independence number of graphs with a prescribed number of cliques
- Random triangle removal
- Generating random networks without short cycles
- Random cyclic triangle-free graphs of prime order
- 4-cycles at the triangle-free process
- A small step forwards on the Erdős-Sós problem concerning the Ramsey numbers \(R(3, k)\)
- A gentle introduction to the differential equation method and dynamic concentration
- The sum-free process
- The Kőnig graph process
- Lovász, vectors, graphs and codes
- Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers
- Balancing sums of random vectors
- The triangle-free process and the Ramsey number \(R(3,k)\)
- Combinatorics. Abstracts from the workshop held January 1--7, 2023
- On the Ramsey-Turán number with small s-independence number
- Two Conjectures in Ramsey--Turán Theory
- Phase transitions in Ramsey-Turán theory
- Greedy maximal independent sets via local limits
- Large triangle packings and Tuza's conjecture in sparse random graphs
- On some generalized vertex Folkman numbers
- Triangle-free subgraphs in the triangle-free process
- Closing the random graph gap in Tuza's conjecture through the online triangle packing process
- A note on pseudorandom Ramsey graphs
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)
