On K_s-free subgraphs in K_s+k-free graphs and vertex Folkman numbers

DOI10.1007/S00493-011-2626-3MaRDI QIDQ653983zbMATH OpenOpenAlexFDO

Authors Andrzej Dudek, Vojtěch Rödl

Publication date 20 December 2011

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-011-2626-3

zbMATH Keywords

\(K_s\)-free subgraphsforbiddenRamsey numbersvertex Folkman numbers

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55)

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}. \]

Recommendations

• An almost quadratic bound on vertex Folkman numbers
• Bounds for some generalized vertex Folkman numbers
• Chromatic vertex Folkman numbers
• New Upper Bound on Vertex Folkman Numbers
• Upper bounds for the vertex Folkman number F_v(3,3,3;4) and F_v(3,3,3;5).

Cites work

• K^s-Free Graphs Without Large K^r-Free Subgraphs
• A Canonical Ramsey Theorem
• A new lower bound for a Ramsey-type problem
• A Ramsey type problem concerning vertex colourings
• An almost quadratic bound on vertex Folkman numbers
• Bounding Ramsey numbers through large deviation inequalities
• Constructive bounds for a Ramsey-type problem
• Graphs with Monochromatic Complete Subgraphs in Every Edge Coloring
• Graphs without large triangle free subgraphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 749960 (Why is no real title available?)
• Large K_r‐free subgraphs in K_s‐free graphs and some other Ramsey‐type problems
• New upper bound for a class of vertex Folkman numbers
• New Upper Bound on Vertex Folkman Numbers
• On minimal Folkman graphs
• On the triangle vertex Folkman numbers
• The Construction of Certain Graphs
• The Ramsey property for graphs with forbidden complete subgraphs

Cited in

(28)

• A Ramsey type problem concerning vertex colourings
• On the nonexistence of some generalized Folkman numbers
• Chromatic vertex Folkman numbers
• \(K_4\)-free graphs without large induced triangle-free subgraphs
• A new lower bound for a Ramsey-type problem
• On the minimum degree of minimal Ramsey graphs for multiple colours
• Dependent random choice
• On the Ramsey-Turán number with small s-independence number
• K^s-Free Graphs Without Large K^r-Free Subgraphs
• On generalized Ramsey numbers of Erdős and Rogers
• Large K_r‐free subgraphs in K_s‐free graphs and some other Ramsey‐type problems
• On the stability of the graph independence number
• Improved bounds for the Erdős-Rogers function
• Short proofs of some extremal results
• When does the \(K_{4}\)-free process stop?
• On graphs with subgraphs having large independence numbers
• On generalized Ramsey numbers for 3-uniform hypergraphs
• On some open questions for Ramsey and Folkman numbers
• The minimum degree of minimal Ramsey graphs for cliques
• On some generalized vertex Folkman numbers
• Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
• On vertex Ramsey graphs with forbidden subgraphs
• The asymptotics of r(4,t)
• Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
• On the use of senders for asymmetric tuples of cliques in Ramsey theory
• A note on the minimum degree of minimal Ramsey graphs
• Induced subgraphs of K_r-free graphs and the Erdős-Rogers problem
• Improved bounds for the Erdős-Rogers (s, s+2)-problem

This page was built for publication: On \(K_s\)-free subgraphs in \(K_{s+k}\)-free graphs and vertex Folkman numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q653983)