Pure pairs. VIII. Excluding a sparse graph
Pure pairs. VIII. Excluding a sparse graph
复制标题
纯对。
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
M. Chudnovsky
中科院分区：
文献类型：
--
作者：
A. Scott;P. Seymour;S. Spirkl;M. Chudnovsky
图中 $G$ 中大小为 $t$ 的纯对是一对 $A,B$ 不相交的 $t$ 顶点集，使得 $A$ 对于 $B$ 是完全的或反完全的。众所周知，对于每个森林 $H$，$n\ge2$ 顶点上不包含 $H$ 或其补集作为导出子图的每个图都有一对大小为 $\Omega(n)$ 的纯对；此外，只有当 $H$ 或其补充是森林时，这才成立。在本文中，我们研究大小为 $n^{1-c}$ 的纯对，其中 $0<c<1$。设 $H$ 为图：$n\ge2$ 顶点上不包含 $H$ 或其补集作为导出子图的每个图是否都具有纯对 $A,B$ 和 $|A|,|B|\ge \Omega(|G|^{1-c})$,？答案与$H$的拥塞有关，即$H$的所有带边的子图$J$上$1-(|J|-1)/|E(J)|$的最大值。 （拥塞度是非负值，当 $H$ 是森林时，拥塞度正好为零。）令 $d$ 为 $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 $\Omega(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 \Omega(|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$.
纯对 VI：排除有序树
影响因子：
0.8
作者：
Scott, Alex;Seymour, Paul;Spirkl, Sophie
通讯作者：
Spirkl, Sophie