Lower Bounds for Ramsey Numbers of Kn with a Small Subgraph Removed

【作者(必填)】Ye Wang Yusheng Li

【文题(必填)】Lower Bounds for Ramsey Numbers of Kn with a Small Subgraph Removed

【年份(必填)】2012

【全文链接或数据库名称(选填)】http://www.sciencedirect.com/sci ... i/S0166218X12001680

只能传压缩后的文件，下载后自己解压

帮帮忙，现在不在学校。多谢！

Lower bounds for Ramsey numbers of Kn with a smallsubgraph removed✩Ye Wang∗, Yusheng LiDepartment of Mathematics, Tongji University, Shanghai 200092, China

1. Introduction
For graphs H1 and H2, the Ramsey number r(H1, H2) is defined to be the smallest N such that any red–blue edge-coloring
of KN contains either a red H1 or a blue H2. We write r(H) for r(H, H).
Let F be a graph of order at most n, size at most n − 2 without isolated vertex. Denote Kn − F a graph obtained from Kn
by deleting edges of a copy of F . Let e be an edge, mP2m independent edges, and P3 a path on three vertices. It is known that
r(K4 − e) = 10 in [1] and r(K5 − e) = 22 in [2]. More results on r(Kn − e) can be found in [4]. We focus on r(Kn − F ) for
some small F in this note.
If the removed subgraph is F = P3, then we have a trivial relation r(Kn − P3) ≥ r(Kn−1). If F = 2P2, the trivial bound is
r(Kn − 2P2) ≥ r(Kn−2), which is much weaker.
We shall use Paley graphs Qp, which is defined in the next section, to give a lower bound for r(Kn −F ), where F is a small
graph