Improved bounds for the Erdős-Rogers function

DOI10.19086/AIC.12048MaRDI QIDQ5126754zbMATH OpenOpenAlexWikidataFDO

Authors Oliver Janzer, W. Timothy Gowers

Publication date 20 October 2020

Published in Advances in Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1804.11302

zbMATH Keywords

Ramsey theory

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Ramsey theory (05D10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: The ErdH{o}s-Rogers function $f_{s,t}$ measures how large a $K_s$-free induced subgraph there must be in a $K_t$-free graph on $n$ vertices. While good estimates for $f_{s,t}$ are known for some pairs $(s,t)$, notably when $t=s+1$, in general there are significant gaps between the best known upper and lower bounds. We improve the upper bounds when $s+2leqtleq2s-1$. For each such pair we obtain for the first time a proof that $f_{s,t}leq{n}^{alph{a}_{s,t}+o(1)}$ with an exponent $alph{a}_{s,t}<1/2$, answering a question of Dudek, Retter and R"{o}dl.

Recommendations

• On generalized Ramsey numbers of Erdős and Rogers
• On \(K_s\)-free subgraphs in \(K_{s+k}\)-free graphs and vertex Folkman numbers
• On graphs with subgraphs having large independence numbers
• On the stability of the graph independence number
• K^s-Free Graphs Without Large K^r-Free Subgraphs

Cited in

(13)

• Improved Bounds on Brun’s Constant
• On generalized Ramsey numbers of Erdős and Rogers
• On the stability of the graph independence number
• A new exponential upper bound for the Erd\H{o}s-Ginzburg-Ziv constant
• Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
• An upper bound on the mean value of the Erdős–Hooley Delta function
• The asymptotics of r(4,t)
• Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
• Ramsey numbers and a general Erdős-Rogers function
• Induced subgraphs of K_r-free graphs and the Erdős-Rogers problem
• Counting sparse induced subgraphs in locally dense graphs
• Improved bounds for the Erdős-Rogers (s, s+2)-problem
• On the order of the classical Erdős-Rogers functions

This page was built for publication: Improved bounds for the Erdős-Rogers function

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