Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Induced Subgraphs of K<sub>r</sub>-Free Graphs and the Erdos-Rogers Problem
 
research article

Induced Subgraphs of Kr-Free Graphs and the Erdos-Rogers Problem

Gishboliner, Lior
•
Janzer, Oliver  
•
Sudakov, Benny
April 1, 2025
Combinatorica

For two graphs F, H and a positive integer n, the function fF,H (n) denotes the largest m such that every H-free graph on n vertices contains an F-free induced subgraph on m vertices. This function has been extensively studied in the last 60 years when F and H are cliques and became known as the Erdos-Rogers function. Recently, Balogh, Chen and Luo, and Mubayi and Verstra & euml;te initiated the systematic study of this function in the case where F is a general graph. Answering, in a strong form, a question of Mubayi and Verstra & euml;te, we prove that for every positive integer r and every Kr-1-free graph F, there exists some epsilon F > 0 such that fF,Kr (n) = O(n1/2-epsilon F ). This result is tight in two ways. Firstly, it is no longer true if F contains Kr-1 as a subgraph. Secondly, we show that for all r >= 4 and epsilon > 0, there exists a Kr-1-free graph F for which fF,Kr (n) = ETX(n1/2-epsilon). Along the way of proving this, we show in particular that for every graph F with minimum degree t, we have fF,K4 (n) = ETX(n1/2-6/ root t ). This answers (in a strong form) another question ofMubayi and Verstra & euml;te. Finally, we prove that there exist absolute constants 0 < c < C such that for each r >= 4, if F is a bipartite graph with sufficiently large minimum degree, then ETX(n c log r ) <= fF,Kr (n) <= O(n C log r ). This shows that for graphs F with large minimum degree, the behaviour of fF,Kr (n) is drastically different from that of the corresponding off-diagonal Ramsey number fK2,Kr (n)

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

10.1007_s00493-025-00147-1.pdf

Type

Main Document

Version

Published version

Access type

openaccess

License Condition

CC BY

Size

405.15 KB

Format

Adobe PDF

Checksum (MD5)

bc444e0728d42e1ca9bb1f372c49a11c

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés