On the Maximum F$ F $‐Free Induced Subgraphs in Kt$ {K}_t $‐Free Graphs
Authors:
- 6 December 2024
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 66 (1)
Abstract
For graphs and , let be the minimum possible size of a maximum ‐free induced subgraph in an ‐vertex ‐free graph. This notion generalizes the Ramsey function and the Erdős–Rogers function. Establishing a container lemma for the ‐free subgraphs, we give a general upper bound on , assuming the existence of certain locally dense ‐free graphs. In particular, we prove that for every graph with , where , we have For the cases where is a complete multipartite graph, letting , we prove that We also make an observation which improves the bounds of by a polylogarithmic factor.Keywords
Funding Information
- National Science Foundation (DMS‐1764123, DMS‐1937241, DMS‐2152488)
- University of Illinois at Urbana-Champaign
This publication has 22 references indexed in Scilit:
- On the number of linear hypergraphs of large girthJournal of Graph Theory, 2019
- Hypergraph containersInventiones Mathematicae, 2015
- On Generalized Ramsey Numbers for 3‐Uniform HypergraphsJournal of Graph Theory, 2013
- Pseudo-random Graphs2006
- A New Lower Bound For A Ramsey-Type ProblemCombinatorica, 2005
- Large Kr‐free subgraphs in Ks‐free graphs and some other Ramsey‐type problemsRandom Structures & Algorithms, 2004
- An Extremal Problem For Random Graphs And The Number Of Graphs With Large Even-GirthCombinatorica, 1998
- The Ramsey number R(3, t) has order of magnitude t2/log tRandom Structures & Algorithms, 1995
- Bounding Ramsey numbers through large deviation inequalitiesRandom Structures & Algorithms, 1995
- On cycle—Complete graph ramsey numbersJournal of Graph Theory, 1978