Tighter bounds on directed Ramsey number R(7)

DOI10.1007/S00373-022-02560-5MaRDI QIDQ2676760zbMATH OpenOpenAlexFDO

Authors David Neiman, John Mackey, Marijn J. H. Heule

Publication date 28 September 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

encodingRamsey theorysatisfiabilitytournaments

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: Tournaments are orientations of the complete graph, and the directed Ramsey number $R(k)$ is the minimum number of vertices a tournament must have to be guaranteed to contain a transitive subtournament of size $k$, which we denote by $T{T}_k$. We include a computer-assisted proof of a conjecture by Sanchez-Flores that all $T{T}_6$-free tournaments on 24 and 25 vertices are subtournaments of $S{T}_{27}$, the unique largest TT_6-free tournament. We also classify all $T{T}_6$-free tournaments on 23 vertices. We use these results, combined with assistance from SAT technology, to obtain the following improved bounds: $34leqR(7)leq47$.

Recommendations

• scientific article; zbMATH DE number 4008439
• On tournaments free of large transitive subtournaments
• An application of the Ramsey theorem to ordered r-tournaments

Cites work

• scientific article; zbMATH DE number 3221981 (Why is no real title available?)
• On tournaments and their largest transitive subtournaments
• On tournaments free of large transitive subtournaments
• Semidefinite programming and Ramsey numbers
• Theory and Applications of Satisfiability Testing

Cited in

(3)

• scientific article; zbMATH DE number 4035876 (Why is no real title available?)
• The packing chromatic number of the infinite square grid is 15
• A Mathon-type construction for digraphs and improved lower bounds for Ramsey numbers

Describes a project that uses

Uses Software

• Treengeling
• Plingeling
• Lingeling
• MiniSat

This page was built for publication: Tighter bounds on directed Ramsey number \(R(7)\)

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