The Ramsey number R(3, t) has order of magnitude t²/log t

DOI10.1002/rsa.3240070302zbMath0832.05084OpenAlexW2100437838WikidataQ29543378 ScholiaQ29543378MaRDI QIDQ4851927

Publication date: 8 February 1996

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240070302

zbMATH Keywords

Ramsey number order of magnitude

Mathematics Subject Classification ID

Combinatorial probability (60C05) Generalized Ramsey theory (05C55)

Related Items

On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies, On the Minimum Degree of Minimal Ramsey Graphs for Cliques Versus Cycles, Concentration of non‐Lipschitz functions and applications, List coloring triangle-free hypergraphs, A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation, Local Clique Covering of Claw-Free Graphs, Counting independent sets in triangle-free graphs, Ramsey-type results for semi-algebraic relations, The $\chi$-Ramsey Problem for Triangle-Free Graphs, The diamond-free process, Lower Bounds for On-line Graph Colorings, Independent sets in hypergraphs omitting an intersection, On the average size of independent sets in triangle-free graphs, Edge clique covers in graphs with independence number two, Coloring of some crown-free graphs, Clique-factors in graphs with sublinear -independence number, Dynamic concentration of the triangle‐free process, Down‐set thresholds, 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 proof of the Erdős-Faber-Lovász conjecture, The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘), On Ramsey Size-Linear Graphs and Related Questions, Signed Ramsey numbers, Unnamed Item, Polynomial $\chi$-binding functions for $t$-broom-free graphs, Coloring triangle-free L-graphs with $O (\log \log n)$ colors, A note on pseudorandom Ramsey graphs, The asymptotics of $r(4,t)$, Coloring lines and Delaunay graphs with respect to boxes, Improved Bounds for the Ramsey Number of Tight Cycles Versus Cliques, Triangle-free subgraphs with large fractional chromatic number, Unnamed Item, Ordered Ramsey numbers, Colouring Squares of Claw-free Graphs, Lovász, Vectors, Graphs and Codes, Online Ramsey Numbers and the Subgraph Query Problem, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Two Conjectures in Ramsey--Turán Theory, Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers, Turán and Ramsey Properties of Subcube Intersection Graphs, Coloring graphs with fixed genus and girth, Strong Turán stability, On independent sets in hypergraphs, When does the K₄‐free process stop?, Hypergraph Ramsey numbers, Large Independent Sets in Triangle-Free Planar Graphs, Short proofs of some extremal results III, Ramsey, Paper, Scissors, The Final Size of theC₄-Free Process, The Ramsey number of the clique and the hypercube, Counting Independent Sets in Hypergraphs, The C_ℓ‐free process, Some Results on Chromatic Number as a Function of Triangle Count, On Some Open Questions for Ramsey and Folkman Numbers, Hasse diagrams with large chromatic number, Ramsey Numbers for Nontrivial Berge Cycles, Triangle-free graphs and forbidden subgraphs, Tight bounds on the clique chromatic number, An approximate version of the tree packing conjecture, A note on multicolor Ramsey number of small odd cycles versus a large clique, Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4, On the closed Ramsey numbers $R^{ cl }( \omega + n, 3)$, Square-free graphs with no induced fork, A fast network-decomposition algorithm and its applications to constant-time distributed computation, A characterization of claw-free CIS graphs and new results on the order of CIS graphs, On the minimum degree of minimal Ramsey graphs for multiple colours, Almost orthogonal subsets of vector spaces over finite fields, On the chromatic number of $2 K_2$-free graphs, The independent neighborhoods process, Scott's Induced Subdivision Conjecture for Maximal Triangle-Free Graphs, On the power of random greedy algorithms, A small step forwards on the Erdős-Sós problem concerning the Ramsey numbers $R(3, k)$, Fractional v. integral covers in hypergraphs of bounded edge size, Multicolor Ramsey Numbers For Complete Bipartite Versus Complete Graphs, Coloring graph classes with no induced fork via perfect divisibility, Nearly perfect matchings in regular simple hypergraphs, Off-diagonal hypergraph Ramsey numbers, Disjoint cycles in graphs with restricted independence number, Homogeneous sets, clique-separators, critical graphs, and optimal $\chi$-binding functions, Ramsey theory and integrality gap for the independent set problem, Bounding $\chi$ by a fraction of $\Delta$ for graphs without large cliques, Triangle-free graphs of tree-width $t$ are $\lceil (t+3)/2 \rceil$-colorable, Large chromatic number and Ramsey graphs, Claw-free graphs. VI: Colouring, Almost-equidistant sets, Bounds for two multicolor Ramsey numbers concerning quadrilaterals, An improved bound for the stepping-up lemma, Some recent results on Ramsey-type numbers, Packing nearly optimal Ramsey $R(3,t)$ graphs, Graphs with $\alpha _1$ and $\tau _1$ both large, Off-diagonal ordered Ramsey numbers of matchings, Independence number of graphs with a prescribed number of cliques, On graphs with a large chromatic number that contain no small odd cycles, Bipartite induced density in triangle-free graphs, The Ramsey number $R(3,K_{10}-e)$ and computational bounds for $R(3,G)$, A gentle introduction to the differential equation method and dynamic concentration, Colouring squares of claw-free graphs, Semi-algebraic Ramsey numbers, A stability theorem on fractional covering of triangles by edges, On upper bounds for the independent transversal domination number, Local and global colorability of graphs, Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions, A few remarks on Ramsey--Turán-type problems, Ramsey numbers involving large dense graphs and bipartite Turán numbers, Ramsey numbers of $K_3$ and $K_{n,n}$, Independent sets and matchings in subcubic graphs, Independent dominating sets in triangle-free graphs, The bipartite $K_{2,2}$-free process and bipartite Ramsey number $b(2, t)$, Some remarks on vertex Folkman numbers for hypergraphs, Colouring, constraint satisfaction, and complexity, Substitution and $\chi$-boundedness, Independence numbers of hypergraphs with sparse neighborhoods., On degree sums of a triangle-free graph, New bounds on the Ramsey number $r ( I_m , L_n )$, Ramsey numbers of some bipartite graphs versus complete graphs, Classes of graphs with low complexity: the case of classes with bounded linear rankwidth, Polynomial $\chi $-binding functions and forbidden induced subgraphs: a survey, On girth and the parameterized complexity of token sliding and Token Jumping, Two results on Ramsey-Turán theory, Independent sets in graphs, Cycles in triangle-free graphs of large chromatic number, The extremal function for cycles of length $\ell$ mod $k$, Almost all graphs with high girth and suitable density have high chromatic number, Bounds on some van der Waerden numbers, $K_r$-factors in graphs with low independence number, Triangle-free graphs whose independence number equals the degree, On forbidden induced subgraphs for $K_{1, 3}$-free perfect graphs, Coloring triangle-free rectangle overlap graphs with $O(\log \log n)$ colors, Gallai colorings of non-complete graphs, On the existence of $k$-partite or $K_p$-free total domination edge-critical graphs, Remarks on generic stability in independent theories, Some constructive bounds on Ramsey numbers, Some remarks on Hajós' conjecture, The early evolution of the $H$-free process, The chromatic gap and its extremes, Hall ratio of the Mycielski graphs, Hypergraph Ramsey numbers: tight cycles versus cliques, Saturation problems in the Ramsey theory of graphs, posets and point sets, Vertex elimination orderings for hereditary graph classes, Ramsey numbers involving graphs with large degrees, Multicolor Ramsey numbers via pseudorandom graphs, A Ramsey-type result for geometric $\ell$-hypergraphs, List-coloring claw-free graphs with small clique number, Linear chromatic bounds for a subfamily of $3K_{1}$-free graphs, The triangle-free process, Revisiting a theorem by Folkman on graph colouring, Near-optimal, distributed edge colouring via the nibble method, A note on the random greedy independent set algorithm, Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture, Partitioning graphs into complete and empty graphs, Locating-dominating sets: from graphs to oriented graphs, Graph imperfection. II, On off-diagonal ordered Ramsey numbers of nested matchings, Phase transitions in Ramsey-Turán theory, The Erdös-Hajnal Conjecture-A Survey, The Erdős-Hajnal conjecture for three colors and triangles

Cites Work

The Ramsey number R(3, t) has order of magnitude t2/log t

The Ramsey number R(3, t) has order of magnitude t²/log t