Some constructive bounds on Ramsey numbers

DOI10.1016/J.JCTB.2010.01.003MaRDI QIDQ974470zbMATH OpenOpenAlexFDO

Authors Vojtěch Rödl, Alexandr Kostochka, Pavel Pudlák

Publication date 3 June 2010

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2010.01.003

zbMATH Keywords

classical Ramsey numbersconstructive boundssuperline graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55)

Review text

Graphs are constructed that provide lower bounds for the classical Ramsey number \(R(k,m)\) for \(k = 4, 5, 6\). More specifically, the bounds are \(R(4,m)\geq \Omega(m^{8/5})\), \(R(5,m)\geq \Omega(m^{5/3})\), and \(R(6,m)\geq \Omega(m^{2})\). The techniques involve a variety of constructions and structures, including the ``superline graphs and similar constructions using bipartite graphs, and classical projective planes. These bounds do not have the same order of magnitude of the best lower bounds for the classical Ramsey number proved using probabilistic methods, but they are the best know constructive lower bounds.

Recommendations

• Constructive bounds for a Ramsey-type problem
• Bounding some Ramsey functions
• New bounds on some Ramsey numbers
• An upper bound for some ramsey numbers
• More constructive lower bounds on classical Ramsey numbers
• scientific article; zbMATH DE number 2237376
• Lower bounds for some Ramsey numbers
• An Upper Bound for Constrained Ramsey Numbers
• A constructive approach for the lower bounds on the Ramsey numbersR (s, t)
• scientific article; zbMATH DE number 4106899

Cites work

• Asymptotic lower bounds for Ramsey functions
• Constructive lower bounds for off-diagonal Ramsey numbers
• Explicit Concentrators from Generalized N-Gons
• Explicit Ramsey graphs and orthonormal labelings
• Norm-graphs: Variations and applications
• On Graphs that do not Contain a Thomsen Graph
• On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph
• Polarities and \(2k\)-cycle-free graphs
• Some structural properties of low-rank matrices related to computational complexity
• The Ramsey number R(3, t) has order of magnitude t²/log t

Cited in

(20)

• Constructive bounds for a Ramsey-type problem
• On the chromatic number of the Erdős-Rényi orthogonal polarity graph
• Independent sets in polarity graphs
• More constructive lower bounds on classical Ramsey numbers
• A small step forwards on the Erdős-Sós problem concerning the Ramsey numbers \(R(3, k)\)
• Ramsey classes: examples and constructions
• scientific article; zbMATH DE number 4023329 (Why is no real title available?)
• Some recent results on Ramsey-type numbers
• scientific article; zbMATH DE number 6813638 (Why is no real title available?)
• Hasse diagrams with large chromatic number
• scientific article; zbMATH DE number 4193722 (Why is no real title available?)
• Some Aspects of the Ramsey Theory of Real Numbers
• On some open questions for Ramsey and Folkman numbers
• Constructive lower bounds for off-diagonal Ramsey numbers
• A note on pseudorandom Ramsey graphs
• Two-colored Ramsey-Turán densities involving triangles
• The automorphism group of projective norm graphs
• The number of edge colorings with small independence number and no monochromatic H
• A construction for Ramsey numbers for \(K_{m,n}\)
• Subgraphs of the projective norm graph

This page was built for publication: Some constructive bounds on Ramsey numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q974470)