On Ramsey Numbers R(K4-e,Kt)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(K_4-e, K_t)$$\end{document}

被引:0
作者
Yu Jiang
Meilian Liang
Yongqi Sun
Xiaodong Xu
机构
[1] Beibu Gulf University,College of Electronics and Information Engineering
[2] Guangxi University,School of Mathematics and Information Science
[3] Beijing Jiaotong University,School of Computer and Information Technology
[4] Guangxi Academy of Sciences,undefined
关键词
Ramsey number; Triangle-free process;
D O I
10.1007/s00373-020-02262-w
中图分类号
学科分类号
摘要
Let G and H be finite undirected graphs. The Ramsey number R(G, H) is the smallest integer n such that for every graph F of order n, either F contains a subgraph isomorphic to G or its complement F¯\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\overline{F}}$$\end{document} contains a subgraph isomorphic to H. An (s, t)-graph is a graph that contains neither a clique of order s nor an independent set of order t. In this paper we obtain some inequalities involving Ramsey numbers of the form R(K4-e,Kt)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(K_4-e,K_t)$$\end{document}. In particular, a constructive proof implies that if G is a (k,s+1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(k,s+1)$$\end{document}-graph, H is a (k,t+1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(k,t+1)$$\end{document}-graph, and both G and H contain a (Kk-e)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(K_k-e)$$\end{document}-free graph M as an induced subgraph, then we have R(Kk+1-e,Ks+t+1)>|V(G)|+|V(H)|+|V(M)|.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(K_{k+1}-e,K_ {s+t+1}) > |V(G)| + |V(H)| + |V(M)|.$$\end{document} Furthermore, if s≤t\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s \le t$$\end{document}, then R(K4-e,Ks+t+1)≥R(3,s+1)+R(3,t+1)+s\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(K_4-e,K_ {s+t+1}) \ge R(3,s+1)+R(3,t+1)+s$$\end{document}. In the experimental part, we use the (K4-e)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(K_4-e)$$\end{document}-free graph generation process to construct graphs witnessing lower bounds for R(K4-e,Kt)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(K_4-e,K_t)$$\end{document}, and compare the results obtained by this approach to the results obtained by analogous triangle-free process. Finally, some open problems involving Ramsey numbers of the form R(K4-e,Kt)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(K_4-e,K_t)$$\end{document} and their asymptotics are posed.
引用
收藏
页码:651 / 661
页数:10
相关论文
共 24 条
  • [1] Burr SA(1989)On the difference between consecutive Ramsey numbers Util. Math. 35 115-118
  • [2] Erdos P(2012)The chromatic gap and its extremes J. Comb. Theory Ser. B 102 1155-1178
  • [3] Faudree RJ(2019)The cyclic triangle-free process Symmetry 11 955-200
  • [4] Schelp R(2019)On a diagonal conjecture for classical Ramsey numbers Discrete Appl. Math. 267 195-87
  • [5] Gyárfás A(1983)A note on the independence number of triangle-free graphs Discrete Math. 46 83-239
  • [6] Sebő A(2004)A constructive approach for the lower bounds on the Ramsey numbers R(s, t) J. Graph Theory 47 231-400
  • [7] Trotignon N(2011)More constructive lower bounds on classical Ramsey numbers SIAM J. Discrete Math. 25 394-221
  • [8] Jiang Y(2016)A small step forwards on the Erdős–Sós problem concerning the Ramsey numbers R(3, k) Discrete Appl. Math. 214 216-undefined
  • [9] Liang M(undefined)undefined undefined undefined undefined-undefined
  • [10] Teng Y(undefined)undefined undefined undefined undefined-undefined