The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘)

DOI10.1090/memo/1274zbMath1439.05001arXiv1302.6279OpenAlexW3010068861MaRDI QIDQ5108704

Gonzalo Fiz Pontiveros, Simon Griffiths, Robert Morris

Publication date: 6 May 2020

Published in: Memoirs of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

triangle-free graphrandom graphrandom graph process\(R(3,k)\)

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Generalized Ramsey theory (05C55)

Related Items (44)

On the Minimum Degree of Minimal Ramsey Graphs for Cliques Versus Cycles ⋮ The Early Evolution of the Random Graph Process in Planar Graphs and Related Classes ⋮ The independent neighborhoods process ⋮ On the Random Greedy $F$-Free Hypergraph Process ⋮ On the power of random greedy algorithms ⋮ On the Ramsey-Turán number with small \(s\)-independence number ⋮ The $\chi$-Ramsey Problem for Triangle-Free Graphs ⋮ Random cyclic triangle-free graphs of prime order ⋮ Packing nearly optimal Ramsey \(R(3,t)\) graphs ⋮ Independence number of graphs with a prescribed number of cliques ⋮ Bipartite induced density in triangle-free graphs ⋮ A gentle introduction to the differential equation method and dynamic concentration ⋮ Friendly bisections of random graphs ⋮ On the average size of independent sets in triangle-free graphs ⋮ Dynamic concentration of the triangle‐free process ⋮ Counting extensions revisited ⋮ Occupancy fraction, fractional colouring, and triangle fraction ⋮ Bounds on Ramsey games via alterations ⋮ Graph and hypergraph colouring via nibble methods: a survey ⋮ Off-diagonal book Ramsey numbers ⋮ Making an H $H$‐free graph k $k$‐colorable ⋮ A variant of the Erdős–Rényi random graph process ⋮ A note on pseudorandom Ramsey graphs ⋮ The asymptotics of \(r(4,t)\) ⋮ Prominent examples of flip processes ⋮ Ramsey-Turán problems with small independence numbers ⋮ Improved Bounds for the Ramsey Number of Tight Cycles Versus Cliques ⋮ The bipartite \(K_{2,2}\)-free process and bipartite Ramsey number \(b(2, t)\) ⋮ The \(Q_2\)-free process in the hypercube ⋮ Ordered Ramsey numbers ⋮ Lovász, Vectors, Graphs and Codes ⋮ Online Ramsey Numbers and the Subgraph Query Problem ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Balancing sums of random vectors ⋮ Closing the Random Graph Gap in Tuza's Conjecture through the Online Triangle Packing Process ⋮ Saturation problems in the Ramsey theory of graphs, posets and point sets ⋮ The sum-free process ⋮ A sharp threshold for bootstrap percolation in a random hypergraph ⋮ On Ramsey numbers \(R(K_4-e, K_t)\) ⋮ Coloring Sparse Hypergraphs ⋮ Ramsey, Paper, Scissors ⋮ The Kőnig graph process ⋮ Large triangle packings and Tuza’s conjecture in sparse random graphs ⋮ Ramsey Numbers for Nontrivial Berge Cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Achlioptas process phase transitions are continuous
• On the Ramsey number of the triangle and the cube
• A note on the random greedy triangle-packing algorithm
• A new upper bound for diagonal Ramsey numbers
• Birth control for giants
• The early evolution of the \(H\)-free process
• The triangle-free process
• A note on the independence number of triangle-free graphs
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• Expose-and-merge exploration and the chromatic number of a random graph
• A note on Ramsey numbers
• A dense infinite Sidon sequence
• Intersection theorems with geometric consequences
• Ramsey's theorem - a new lower bound
• On tail probabilities for martingales
• Explicit Ramsey graphs and orthonormal labelings
• Random graph processes with maximum degree 2
• Counting designs
• Differential equations for random processes and random graphs
• Constrainted graph processes
• Random triangle removal
• Avoiding a giant component
• Anatomy of a young giant component in the random graph
• Emergence of Scaling in Random Networks
• The Final Size of theC₄-Free Process
• SIR epidemics on random graphs with a fixed degree sequence
• Graph Theory and Probability. II
• Factors in random graphs
• The Evolution of Random Graphs
• An upper bound for some ramsey numbers
• Random Graph Processes with Degree Restrictions
• The chromatic number of dense random graphs
• On the size of a random maximal graph
• Random maximalH-free graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The birth of the giant component
• Product rule wins a competitive game
• Creating a Giant Component
• The phase transition in inhomogeneous random graphs
• When does the K₄‐free process stop?
• Dynamic concentration of the triangle-free process
• Hamiltonicity of random graphs produced by 2‐processes
• The C_ℓ‐free process
• Solutions of ordinary differential equations as limits of pure jump markov processes
• Some remarks on the theory of graphs
• Explosive Percolation in Random Networks
• The chromatic number of random graphs
• The two possible values of the chromatic number of a random graph

This page was built for publication: The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘)