Tighter Bounds on Directed Ramsey Number R(7)

被引:0
作者
David Neiman
John Mackey
Marijn Heule
机构
[1] Carnegie Mellon University,
来源
Graphs and Combinatorics | 2022年 / 38卷
关键词
Ramsey theory; Tournaments; Satisfiability; Encoding;
D O I
暂无
中图分类号
学科分类号
摘要
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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ TT _k$$\end{document}. We include a computer-assisted proof of a conjecture by Sanchez-Flores in Graphs Combinatorics 14(2), 181–200 (1998), that all TT6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ TT _6$$\end{document}-free tournaments on 24 and 25 vertices are subtournaments of ST27\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ ST _{27}$$\end{document}, the unique largest TT6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ TT _6$$\end{document}-free tournament. We also classify all TT6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ TT _6$$\end{document}-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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$34 \le R(7) \le 47$$\end{document}.
引用
收藏
相关论文
共 6 条
  • [1] Erdős Paul(1964)On the representation of directed graphs as unions of orderings Math. Inst. Hung. Acad. Sci 9 125-132
  • [2] Moser Leo(2021)Semidefinite programming and ramsey numbers SIAM J. Discret. Math. 35 2328-2344
  • [3] Lidicky Bernard(1994)On tournaments and their largest transitive subtournaments Graphs Combinatorics 10 367-376
  • [4] Pfender Florian(1998)On tournaments free of large transitive subtournaments Graphs Combinatorics 14 181-200
  • [5] Sanchez-Flores Adolfo(undefined)undefined undefined undefined undefined-undefined
  • [6] Sanchez-Flores Adolfo(undefined)undefined undefined undefined undefined-undefined