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

DOI10.1002/rsa.3240070302zbMath0832.05084MaRDI 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

60C05: Combinatorial probability

05C55: Generalized Ramsey theory

Related Items

Coloring graphs with fixed genus and girth, Concentration of non‐Lipschitz functions and applications, Turán and Ramsey Properties of Subcube Intersection Graphs, Large Independent Sets in Triangle-Free Planar Graphs, On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies, On independent sets in hypergraphs, When does the K₄‐free process stop?, The Ramsey number of the clique and the hypercube, Counting Independent Sets in Hypergraphs, The C_ℓ‐free process, On Some Open Questions for Ramsey and Folkman Numbers, Ordered Ramsey numbers, Strong Turán stability, An approximate version of the tree packing conjecture, 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)\), Large chromatic number and Ramsey graphs, An improved bound for the stepping-up lemma, Some recent results on Ramsey-type numbers, The Ramsey number \(R(3,K_{10}-e)\) and computational bounds for \(R(3,G)\), A stability theorem on fractional covering of triangles by edges, Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions, Ramsey numbers of \(K_3\) and \(K_{n,n}\), Independent sets and matchings in subcubic graphs, Independent dominating sets in triangle-free graphs, Some remarks on vertex Folkman numbers for hypergraphs, Colouring, constraint satisfaction, and complexity, Substitution and \(\chi\)-boundedness, On degree sums of a triangle-free graph, Independent sets in graphs, The extremal function for cycles of length \(\ell\) mod \(k\), On the existence of \(k\)-partite or \(K_p\)-free total domination edge-critical graphs, Claw-free graphs. VI: Colouring, Ramsey numbers of some bipartite graphs versus complete graphs, Some remarks on Hajós' conjecture, The chromatic gap and its extremes, Ramsey numbers involving graphs with large degrees, A Ramsey-type result for geometric \(\ell\)-hypergraphs, List-coloring claw-free graphs with small clique number, Semi-algebraic Ramsey numbers, Local and global colorability of graphs, Bounds on some van der Waerden numbers, Triangle-free graphs whose independence number equals the degree, Gallai colorings of non-complete graphs, Some constructive bounds on Ramsey numbers, The early evolution of the \(H\)-free process, Linear chromatic bounds for a subfamily of \(3K_{1}\)-free graphs, The triangle-free process, Partitioning graphs into complete and empty graphs, Near-optimal, distributed edge colouring via the nibble method, Fractional v. integral covers in hypergraphs of bounded edge size, Nearly perfect matchings in regular simple hypergraphs, A few remarks on Ramsey--Turán-type problems, Ramsey numbers involving large dense graphs and bipartite Turán numbers, Independence numbers of hypergraphs with sparse neighborhoods., Triangle-free graphs and forbidden subgraphs, Graph imperfection. II, On graphs with a large chromatic number that contain no small odd cycles, Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors, Phase transitions in Ramsey-Turán theory, Off-diagonal hypergraph Ramsey numbers, Hall ratio of the Mycielski graphs, Vertex elimination orderings for hereditary graph classes, Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture, Almost all graphs with high girth and suitable density have high chromatic number, Hypergraph Ramsey numbers: tight cycles versus cliques, A note on the random greedy independent set algorithm, The Erdös-Hajnal Conjecture-A Survey, Scott's Induced Subdivision Conjecture for Maximal Triangle-Free Graphs, Multicolor Ramsey Numbers For Complete Bipartite Versus Complete Graphs, The diamond-free process, Lower Bounds for On-line Graph Colorings, The Final Size of theC₄-Free Process, Counting independent sets in triangle-free graphs, Ramsey-type results for semi-algebraic relations, 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, Hypergraph Ramsey numbers

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