论文标题
Rödl定理的进一步扩展
A further extension of Rödl's theorem
论文作者
论文摘要
修复$ \ varepsilon> 0 $和无null图$ h $。 80年代的Rödl定理的一个著名定理说，每个图$ g $都没有$ h $的诱导副本包含一个线性大小的$ \ varepsilon $限制的套件$ s \ subseteq v（g）$，这意味着$ s $在最大的$ \ varepsilon $ \ varepsilon comprement $ f pert $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ gert in这个结果有两个扩展： $ \ bullet $定量，Nikiforov（和后来的Fox和Sudakov）放松了“最多$κ\ vert g \ vert g \ vert g \ vert^{\ vert h \ vert} $诱导$ h $ $ h $的副本的条件，最多$κ\ vert g \ vert g \ vert g \ vert^{\ vert h \ vert} $ h $ to $κ> 0 $ to $κ> 0 $ tho $ h $ and $ h $ and $ \ varepsilon $ $ \ varepsilon $;和 $ \ bullet $从定性上，Chudnovsky，Scott，Seymour和Spikl最近表明，存在$ n> 0 $，具体取决于$ h $和$ \ varepsilon $，因此$ g $是$（n，\ varepsilon）$ - 限制了$ n $ n $ n $ n是$ n是$ n是$ n是$ n是$ n是$ n是$ n是$ n是$ n是。 这两个断言的自然常见概括，每张图$ g $最多都$κ\ vert g \ vert^{\ vert h \ vert} $诱导的$ h $的副本为$（n，\ varepsilon）$ - 限制了某些$κ，n> 0 $，根据$ h $ h $ h $和$ h $ \ varepsilon $ $ \ varepsilon $。不幸的是，这是错误的，但是我们证明，每$ \ varepsilon> 0 $，$κ$和$ n $仍然存在，以便每$ d \ ge0 $，每张图最多可$κD^{\ vert h \ vert h \ vert h \ vert} $诱导的副本$ h $（$ h $顶点。这统一了上述两个定理，每个值的$ d $最佳和最佳$κ$和$ n $。
Fix $\varepsilon>0$ and a nonnull graph $H$. A well-known theorem of Rödl from the 80s says that every graph $G$ with no induced copy of $H$ contains a linear-sized $\varepsilon$-restricted set $S\subseteq V(G)$, which means $S$ induces a subgraph with maximum degree at most $\varepsilon\vert S\vert$ in $G$ or its complement. There are two extensions of this result: $\bullet$ quantitatively, Nikiforov (and later Fox and Sudakov) relaxed the condition "no induced copy of $H$" into "at most $κ\vert G\vert^{\vert H\vert}$ induced copies of $H$ for some $κ>0$ depending on $H$ and $\varepsilon$"; and $\bullet$ qualitatively, Chudnovsky, Scott, Seymour, and Spirkl recently showed that there exists $N>0$ depending on $H$ and $\varepsilon$ such that $G$ is $(N,\varepsilon)$-restricted, which means $V(G)$ has a partition into at most $N$ subsets that are $\varepsilon$-restricted. A natural common generalization of these two asserts that every graph $G$ with at most $κ\vert G\vert^{\vert H\vert}$ induced copies of $H$ is $(N,\varepsilon)$-restricted for some $κ,N>0$ depending on $H$ and $\varepsilon$. This is unfortunately false, but we prove that for every $\varepsilon>0$, $κ$ and $N$ still exist so that for every $d\ge0$, every graph with at most $κd^{\vert H\vert}$ induced copies of $H$ has an $(N,\varepsilon)$-restricted induced subgraph on at least $\vert G\vert-d$ vertices. This unifies the two aforementioned theorems, and is optimal up to $κ$ and $N$ for every value of $d$.
