Tighter Bounds on Directed Ramsey Number R(7)

被引：2

作者：

Neiman, David ^{[1
]}

Mackey, John ^{[1
]}

Heule, Marijn ^{[1
]}

机构：

[1] Carnegie Mellon Univ, Pittsburgh, PA 15213 USA

来源：

GRAPHS AND COMBINATORICS | 2022年 / 38卷 / 05期

关键词：

Ramsey theory; Tournaments; Satisfiability; Encoding; TOURNAMENTS;

D O I：

10.1007/s00373-022-02560-5

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Tournaments are orientations of the complete graph. 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 TTk. We include a computer-assisted proof of a conjecture by Sanchez-Flores in Graphs Combinatorics 14(2), 181-200 (1998), that all TT6-free tournaments on 24 and 25 vertices are subtournaments of ST27, the unique largest TT6-free tournament. We also classify all TT6-free tournaments on 23 vertices. We use these results, combined with assistance from a SAT solver, to obtain the following improved bounds on R(7): 34 <= R(7) <= 47.

引用

页数：17

共 10 条

[1] Biere A., 2018, DEP COMPUTER SCI S B, VB-2018-1, P13
[2] Effective preprocessing in SAT through variable and clause elimination
Eén, N
Biere, A
[J]. THEORY AND APPLICATIONS OF SATISFIABILITY TESTING, PROCEEDINGS, 2005, 3569 : 61 - 75
[3] Erdos P., 1964, MATH I HUNG ACAD SCI, V9, P125
[4] Gent IP, 2002, FRONT ARTIF INTEL AP, V77, P121
[5] SEMIDEFINITE PROGRAMMING AND RAMSEY NUMBERS
Lidicky, Bernard
Pfender, Florian
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (04) : 2328 - 2344
[6] Lohn Evan., 2022, P FMCAD 2022
[7] McKay B., DIGRAPHS
[8] Moon J.W., 1968, Topics on Tournaments
[9] On tournaments free of large transitive subtournaments
Sanchez-Flores, A
[J]. GRAPHS AND COMBINATORICS, 1998, 14 (02) : 181 - 200
[10] ON TOURNAMENTS AND THEIR LARGEST TRANSITIVE SUBTOURNAMENTS
SANCHEZFLORES, A
[J]. GRAPHS AND COMBINATORICS, 1994, 10 (04) : 367 - 376

← 1 →