Ramsey numbers and a general Erdős-Rogers function

• Published in: Discrete mathematics 2024-12, Vol.347 (12), p.114203, Article 114203
• Main Authors: Hu, Xinyu, Lin, Qizhong
• Format: Article
• Language: English
• Subjects: Erdős-Rogers problem; Hypergraph container method; Ramsey number; Random block construction
• ISSN: 0012-365X
• DOI: 10.1016/j.disc.2024.114203

Given a graph F, let L(F) be a fixed finite family of graphs consisting of a C4 and some bipartite graphs relying on an s-partite subgraph partitioning of edges of F. Define (m,n,a,b)-graph by an m×n bipartite graph with n≥m such that all vertices in the part of size n have degree a and all vertices in the part of size m have degree b≥a. In this paper, building upon the work of Janzer and Sudakov (2023+) and combining with the idea of Conlon, Mattheus, Mubayi and Verstraëte (2023+) we obtain that for each s≥2, if there exists an L(F)-free (m,n,a,b)-graph, then there exists an F-free graph H⁎ with at least na−1s−1−1 vertices in which every vertex subset of size ma−ss−1log3⁡(an) contains a copy of Ks. As applications, we obtain some upper bounds of general Erdős-Rogers functions for some special graphs of F. Moreover, we obtain the multicolor Ramsey numbers rk+1(C5;t)=Ω˜(t3k7+1) and rk+1(C7;t)=Ω˜(tk4+1), which improve that by Xu and Ge (2022) [24].