New values for the bipartite Ramsey number of the four-cycle versus stars

被引：6

作者：

Hatala, Imre ^{[1
]}

Heger, Tamas ^{[2
]}

Mattheus, Sam ^{[3
]}

机构：

[1] Eotvos Lorand Univ, Budapest, Hungary

[2] Eotvos Lorand Univ, Dept Comp Sci, ELKH ELTE Geometr & Algebra Combinator Res Grp, Pazmany P Setany 1-C, H-1117 Budapest, Hungary

[3] Vrije Univ Brussel, Dept Math, Pl Laan 2, B-1050 Brussels, Belgium

来源：

DISCRETE MATHEMATICS | 2021年 / 344卷 / 05期

关键词：

Ramsey number; Quadrilateral-free; Projective plane; Incidence graph; Marginal set; GRAPHS; BOUNDS; GIRTH; C-4;

D O I：

10.1016/j.disc.2021.112320

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We provide new values of the bipartite Ramsey number R-B(C-4, K-1,K-n) using induced subgraphs of the incidence graph of a projective plane. The approach, based on deleting subplanes of projective planes, has been used in related extremal problems and allows us to unify previous results and extend them. More importantly, using deep stability results on 2 mod p sets and double blocking sets, we can show some of the limits of this technique when the projective plane is Desarguesian of large enough square order. Finally, we also disprove two conjectures about R-B(C-4, K-1,K-n). (C) 2021 The Authors. Published by Elsevier B.V.

引用

页数：14

共 32 条

[1]

[Anonymous], 1968, THEORY GRAPHS

[2] Constructions of Small Regular Bipartite Graphs of Girth 6 [J].