Repository logo
 

Improved bounds for the Erdős-Rogers function

Published version
Peer-reviewed

Type

Article

Change log

Authors

Gowers, WT 
Janzer, O 

Abstract

The Erd\H{o}s-Rogers function fs,t measures how large a Ks-free induced subgraph there must be in a Kt-free graph on n vertices. While good estimates for fs,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+2≤t≤2s−1. For each such pair we obtain for the first time a proof that fs,tnαs,t+o(1) with an exponent αs,t<1/2, answering a question of Dudek, Retter and R"{o}dl.

Description

Keywords

math.CO, math.CO, 05D40, 05D10

Journal Title

Advances in Combinatorics, 2020:3, 27pp

Conference Name

Journal ISSN

2517-5599
2517-5599

Volume Title

Publisher

Alliance of Diamond Open Access Journals
Sponsorship
EPSRC (1951090)