We initiate the systematic study of the following Turán-type question. Suppose <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\Gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Γ</mi> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$1 - c$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>-</mo> <mi>c</mi> </mrow> </math></EquationSource> </InlineEquation>, for some t and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$c > 0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>. What is the largest number of edges in a subgraph <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$G \subseteq \Gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>⊆</mo> <mi mathvariant="normal">Γ</mi> </mrow> </math></EquationSource> </InlineEquation> which does not contain a fixed graph H as an induced subgraph or, more generally, which belongs to a hereditary property <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\mathcal {P}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">P</mi> </math></EquationSource> </InlineEquation>? This provides a common generalization of two recently studied cases, namely <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\Gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Γ</mi> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\Gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Γ</mi> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\Gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Γ</mi> </math></EquationSource> </InlineEquation>. 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.

The Largest Subgraph Without A Forbidden Induced Subgraph

期刊论文
发表日期：

2025年11月7日

查看全文

Jacob Fox,
Rajko Nenadov,
Huy Tuan Pham

摘要

We initiate the systematic study of the following Turán-type question. Suppose $\Gamma $ $Γ$ 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$ $1 - c$ , for some t and $c > 0$ $c > 0$ . What is the largest number of edges in a subgraph $G \subseteq \Gamma $ $G \subseteq Γ$ which does not contain a fixed graph H as an induced subgraph or, more generally, which belongs to a hereditary property $\mathcal {P}$ $P$ ? This provides a common generalization of two recently studied cases, namely $\Gamma $ $Γ$ 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 $\Gamma $ $Γ$ 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 $\Gamma $ $Γ$ . 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.