- TRAN, Tuan
- 이산수학 그룹

Two problems in graph Ramsey theory

- Title
- Two problems in graph Ramsey theory

- Author(s)
- Tuan Tran

- Publication Date
- 2022-08

- Journal
- European Journal of Combinatorics, v.104

- Publisher
- Academic Press

- Abstract
- We study two problems in graph Ramsey theory. In the early 1970s, Erdős and O'Neil considered a generalization of Ramsey numbers. Given integers n,k,s and t with n≥k≥s,t≥2, they asked for the least integer N=fk(n,s,t) such that in any red–blue coloring of the k-subsets of {1,2,…,N}, there is a set of size n such that either each of its s-subsets is contained in some red k-subset, or each of its t-subsets is contained in some blue k-subset. Erdős and O'Neil found an exact formula for fk(n,s,t) when k≥s+t−1. In the arguably more interesting case where k=s+t−2, they showed [Formula presented] for sufficiently large n. Our main result closes the gap between these lower and upper bounds, determining the logarithm of fs+t−2(n,s,t) up to a multiplicative factor. Recently, Damásdi, Keszegh, Malec, Tompkins, Wang and Zamora initiated the investigation of saturation problems in Ramsey theory, wherein one seeks to minimize n such that there exists an r-edge-coloring of Kn for which any extension of this to an r-edge-coloring of Kn+1 would create a new monochromatic copy of Kk. We obtain essentially sharp bounds for this problem.

- ISSN
- 0195-6698

- Appears in Collections:
- Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)

- Files in This Item:
- There are no files associated with this item.