2024/05/09 by Jacob Fox, Fox, Jacob, Rajko Nenadov +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2405.05902
openalex publication_date 2024/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We initiate the systematic study of the following Turán-type question. Suppose Γ is a graph with n vertices such that the edge density between any pair of subsets of vertices of size at least t is at most 1 - c, for some t and c > 0. What is the largest number of edges in a subgraph G ⊆ Γ which does not contain a fixed graph H as an induced subgraph or, more generally, which belongs to a hereditary property P? This provides a common generalization of two recently studied cases, namely Γ being a (pseudo-)random graph and a graph without a large complete bipartite subgraph. We focus on the interesting case where H is a bipartite graph. We determine the answer up to a constant factor with respect to n and t, for certain bipartite H and for Γ either a dense random graph or a Paley graph with a square number of vertices. In particular, our bounds match if H is a tree, or if one part of H has d vertices complete to the other part, all other vertices in that part have degree at most d, and the other part has sufficiently many vertices. As applications of the latter result, we answer a question of Alon, Krivelevich, and Samotij on the largest subgraph with a hereditary property which misses a bipartite graph, and determine up to a constant factor the largest number of edges in a string subgraph of Γ. The proofs are based on a variant of the dependent random choice and a novel approach for finding induced copies by inductively defining probability distributions supported on induced copies of smaller subgraphs.