On \(K_s\)-free subgraphs in \(K_{s+k}\)-free graphs and vertex Folkman numbers
type: Item
instance of: scholarly article
title: On \(K_s\)-free subgraphs in \(K_{s+k}\)-free graphs and vertex Folkman numbers
zbMATH Open document ID: 1249.05197
author: Andrzej Dudek
author: Vojtěch Rödl
published in: Combinatorica
publication date: 2011-12-20T00:00:00Z
review text: For fixed integers \(2 \leq s < t\), define \[ f_{s,t}(n) = \min\{\max\{| S| ~ : ~ S\subseteq V(H) ~ \text{and} ~ \langle S\rangle_H ~ \text{contains no} ~ K_s\}\} \] where the min is taken over all \(K_t\)-free graphs \(H\) of order \(n\). Bounds on this Ramsey function are investigated, and the following surprising result is proved. For every integer \(s \geq 2\), there is a positive constant \(c = c(s)\) so that for every integer \(n\), \[ f_{s,s+1}(n) \leq cn^{2/3}. \] Previously, it was suggested that for any given \(\epsilon > 0\), \(f_{s,s+1}(n) \geq n^{1 - \epsilon}\). The following more general result along with a corollary was proved. Given any \(\epsilon > 0\) and integer \(k \geq 2\), there is a constant \(s_0 = s_0(\epsilon, k)\) such that for \(s \geq s_0\), \[ c_1n^{1/(1 + (\frac{s}{s-1})^{k-1})} \leq f_{s, s+k}(n) \leq c_2n^{\frac{k+1}{2k+1} + \epsilon}, \] where \(c_1\) and \(c_2\) are positive constants depending only on \(s\). An immediate corollary of this for \(k\) sufficiently large is the following: \[ c_1n^{\frac12 - \epsilon} \leq f_{s, s+k}(n) \leq c_2n^{\frac12 + \epsilon}, \] where \(c_1\) and \(c_2\) are constants depending on \(k\) and \(s\). These results are applied to the vertex Folkman number \(F(r,s,t)\) for \(s < t\), which is the smallest integer \(n\) such that there exists a \(K_t\)-free graph \(G\) of order \(n\) such that every \(r\)-coloring of the vertices of \(G\) yields a monochromatic \(K_s\). Each of the results on the function \(f_{s, t}(n)\) yields a corresponding result on the vertex Folkman number. For example, in the case of the corollary there is the following result: For any \(\epsilon > 0\) and sufficiently large \(s\), \(t\), \(k\), \(c_1\) and \(c_2\), \[ c_1r^{2 - \epsilon} \leq F(r, s, s + k) \leq c_1r^{2 + \epsilon}. \]
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 5990941
zbMATH Keywords: \(K_s\)-free subgraphs
zbMATH Keywords: vertex Folkman numbers
zbMATH Keywords: Ramsey numbers
zbMATH Keywords: forbidden
MaRDI profile type: Publication
full work available at URL: s00493-011-2626-3
OpenAlex ID: W1984962604
cites work: Constructive bounds for a Ramsey-type problem
cites work: Graphs without large triangle free subgraphs
cites work: A Ramsey type problem concerning vertex colourings
cites work: An almost quadratic bound on vertex Folkman numbers
cites work: New Upper Bound on Vertex Folkman Numbers
cites work: A Canonical Ramsey Theorem
cites work: The Construction of Certain Graphs
cites work: Graphs with Monochromatic Complete Subgraphs in Every Edge Coloring
cites work: Q2716030
cites work: New upper bound for a class of vertex Folkman numbers
cites work: Bounding Ramsey numbers through large deviation inequalities
cites work: Ks-Free Graphs Without Large Kr-Free Subgraphs
cites work: On minimal Folkman graphs
cites work: On the triangle vertex Folkman numbers
cites work: The Ramsey property for graphs with forbidden complete subgraphs
cites work: Large Kr‐free subgraphs in Ks‐free graphs and some other Ramsey‐type problems
cites work: A new lower bound for a Ramsey-type problem
cites work: Q4764145
DOI: 10.1007/S00493-011-2626-3
description: scientific article; zbMATH DE number 5990941