论文标题
纯对。 viii。不包括稀疏图
Pure pairs. VIII. Excluding a sparse graph
论文作者
论文摘要
$ g $中的一对尺寸$ t $是$ a，b $ b $ discoint的$ t $ vertices集，以便$ a $是$ b $的完整或反填充。众所周知，对于每个森林$ h $，$ n \ ge2 $顶点上的每张图都不包含$ h $，或者作为诱导子图的补充都具有纯$ω（n）$；此外，仅当$ h $或其补充是森林时，这才能成立。 在本文中，我们查看了$ n^{1-c} $的纯对，其中$ 0 <c <1 $。令$ h $为图：$ n \ ge2 $顶点上的每张图都不包含$ h $或它的补充，因为诱导子图具有纯对$ a，b $，带有$ | a |，| b | b | \geΩ（| g |^{1-c}）$，？答案与$ h $的拥塞有关，最高$ 1-（| j | -1）/| e（j）| $在所有子图上$ j $ $ j $ h $都具有边缘。 （拥塞是非负的，当$ h $是森林时，完全等于零。）让$ d $成为$ h $和$ h $和$ \ overline {h} $的拥塞中的较小。我们表明，如果$ d \ le c/（9+15c）$，则上述问题的答案是“是”，如果$ d> c $，则“否”。
A pure pair of size $t$ in a graph $G$ is a pair $A,B$ of disjoint sets of $t$ vertices such that $A$ is either complete or anticomplete to $B$. It is known that, for every forest $H$, every graph on $n\ge2$ vertices that does not contain $H$ or its complement as an induced subgraph has a pure pair of size $Ω(n)$; furthermore, this only holds when $H$ or its complement is a forest. In this paper, we look at pure pairs of size $n^{1-c}$, where $0<c<1$. Let $H$ be a graph: does every graph on $n\ge2$ vertices that does not contain $H$ or its complement as an induced subgraph have a pure pair $A,B$ with $|A|,|B|\ge Ω(|G|^{1-c})$,? The answer is related to the congestion of $H$, the maximum of $1-(|J|-1)/|E(J)|$ over all subgraphs $J$ of $H$ with an edge. (Congestion is nonnegative, and equals zero exactly when $H$ is a forest.) Let $d$ be the smaller of the congestions of $H$ and $\overline{H}$. We show that the answer to the question above is "yes" if $d\le c/(9+15c)$, and "no" if $d>c$.
