Semidefinite programming and Ramsey numbers

DOI10.1137/18M1169473MaRDI QIDQ5163505zbMATH OpenFDO

Authors Bernard Lidický, Florian Pfender

Publication date 4 November 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

flag algebraRamsey numberssemidefinite programmingsmall graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55) Hypergraphs (05C65) Ramsey theory (05D10) Semidefinite programming (90C22)

Abstract: Finding exact Ramsey numbers is a problem typically restricted to relatively small graphs. The flag algebra method was developed to find asymptotic results for very large graphs, so it seems that the method is not suitable for finding small Ramsey numbers. But this intuition is wrong, and we will develop a technique to do just that in this paper. We find new upper bounds for many small graph and hypergraph Ramsey numbers. As a result, we prove the exact values $R(K_4^{-},K_4^{-},K_4^{-})=28$, $R(K_8,C_5)=29$, $R(K_9,C_6)=41$, $R(Q_3,Q_3)=13$, $R(K_{3,5},K_{1,6})=17$, $R(C_3,C_5,C_5)=17$, and $R(K_4^{-},K_5^{-};3)=12$. We hope that this technique will be adapted to address other questions for smaller graphs with the flag algebra method.

Recommendations

• Linear programming in some Ramsey problems
• Ramsey goodness and beyond
• The Ramsey number \(R(3,K_{10}-e)\) and computational bounds for \(R(3,G)\)
• New bounds for Ramsey numbers \(R ( K_k - e , K_l - e )\)
• Exact values for some generalized Ramsey numbers

Cites work

• A problem of Erdős on the minimum number of k-cliques
• Bounds on Ramsey numbers of certain complete bipartite graphs
• Computation of some generalized Ramsey numbers
• CSDP, A C library for semidefinite programming
• Cycle-complete graph Ramsey numbers \(r(C_4,K_9)\) \(,r(C_5,K_8)\leq 33\)
• Finitely forcible graphons and permutons
• Flag algebras
• scientific article; zbMATH DE number 5850550 (Why is no real title available?)
• scientific article; zbMATH DE number 5079855 (Why is no real title available?)
• scientific article; zbMATH DE number 5138353 (Why is no real title available?)
• scientific article; zbMATH DE number 4033787 (Why is no real title available?)
• scientific article; zbMATH DE number 1161386 (Why is no real title available?)
• scientific article; zbMATH DE number 5206705 (Why is no real title available?)
• scientific article; zbMATH DE number 3221981 (Why is no real title available?)
• Hypergraphs do jump
• Limits of order types
• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
• Minimum Number of Monotone Subsequences of Length 4 in Permutations
• Monochromatic triangles in three-coloured graphs
• New upper bounds for Ramsey numbers
• On crossing numbers of complete tripartite and balanced complete multipartite graphs
• On ramsey numbers for books
• On Some Multicolor Ramsey Numbers Involving K₃+e and K₄-e
• On some Ramsey numbers for quadrilaterals
• On the maximum quartet distance between phylogenetic trees
• On the number of pentagons in triangle-free graphs
• On tournaments free of large transitive subtournaments
• Pentagons in triangle-free graphs
• Small Ramsey numbers
• The clique density theorem
• The codegree threshold for 3-graphs with independent neighborhoods
• The multi-color Ramsey number of an odd cycle
• The ramsey number of k5 - e
• Three color Ramsey number of \(K_ 4-e\)
• Three color Ramsey numbers for graphs with at most 4 vertices

Cited in

(16)

• Linear programming in some Ramsey problems
• Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth
• Tighter bounds on directed Ramsey number \(R(7)\)
• Integer sequences and semidefinite programming
• scientific article; zbMATH DE number 1210327 (Why is no real title available?)
• Decomposing graphs into edges and triangles
• Lower bounds for book Ramsey numbers
• Small Ramsey numbers for books, wheels, and generalizations
• The Rado multiplicity problem in vector spaces over finite fields
• On the minimum density of monotone subwords
• \({\mathcal{R}}(K_6-e,K_4) =30^\ast\)
• Disproofs of four conjectures on Gallai-Ramsey numbers
• Bounds on small Ramsey numbers by semidefinite programming
• The four-color Ramsey multiplicity of triangles
• Generalized Turán problem for complete hypergraphs
• Getting to the root of the problem: sums of squares for limits of trees

Describes a project that uses

Uses Software

• Flagmatic
• CSDP
• SDPA

This page was built for publication: Semidefinite programming and Ramsey numbers

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