MathDB 361178 的反例

一、反例

对图 $X$，记 $Z^+_{(1)}(X)$ 为它的 1-泄漏正半定强迫数。MathDB 361178 的猜想断言：对任意图 $X$ 和任意边 $f\in E(X)$，

$$Z^+_{(1)}(X)-Z^+_{(1)}(X-f)\le 1.$$

取顶点集

$$V(G)=\{0,1,\ldots,8\},$$

边集

$$\begin{aligned} E(G)=\{&03,05,06,07,08,14,15,16,17,18,27,\\ &35,37,38,46,48,57,68\}. \end{aligned}$$

取 $e=05$，并记

$$H=G-e.$$

图 $G$ 的 graph6 编码为 HCRUVjY。下面将证明

$$Z^+_{(1)}(G)\ge 6, \qquad Z^+_{(1)}(H)\le 4.$$

因此

$$Z^+_{(1)}(G)-Z^+_{(1)}(G-e) \ge 6-4=2>1,$$

故 $(G,e)$ 是该猜想的反例。

二、证明

在正半定强迫过程中，设当前蓝点集为 $B$，而 $W$ 是白点诱导子图 $X-B$ 的一个连通分支。如果蓝点 $u$ 在 $W$ 中恰有一个邻点 $v$，则允许执行强迫 $u\to v$。泄漏点可以是蓝点或白点，也可以被其他顶点强迫，但不能作为强迫箭头的起点。

先证明 $Z^+_{(1)}(H)\le4$。取初始蓝点集

$$B=\{1,2,6,8\}.$$

下表对泄漏点的每一种可能位置给出一条合法的正半定强迫序列。

泄漏点	强迫序列
$0$	$2\to7,\ 1\to5,\ 5\to3,\ 3\to0,\ 1\to4$
$1$	$2\to7,\ 6\to0,\ 0\to3,\ 6\to4,\ 3\to5$
$2$	$6\to0,\ 8\to3,\ 1\to4,\ 0\to7,\ 1\to5$
$3$	$2\to7,\ 1\to5,\ 5\to3,\ 6\to0,\ 1\to4$
$4$	$2\to7,\ 1\to5,\ 5\to3,\ 3\to0,\ 1\to4$
$5$	$2\to7,\ 1\to5,\ 6\to0,\ 0\to3,\ 1\to4$
$6$	$2\to7,\ 1\to5,\ 5\to3,\ 3\to0,\ 1\to4$
$7$	$2\to7,\ 1\to5,\ 5\to3,\ 3\to0,\ 1\to4$
$8$	$2\to7,\ 1\to5,\ 5\to3,\ 3\to0,\ 1\to4$

每一行都避开了以该行泄漏点为起点的箭头，并最终将九个顶点全部染成蓝色。因此 $B$ 是 $H$ 的一个 1-泄漏正半定强迫集，从而

$$Z^+_{(1)}(H)\le4.$$

下面证明 $Z^+_{(1)}(G)\ge6$。称非空连通点集 $F\subseteq V(G)$ 为一个堡垒，如果 $F$ 外至多有一个顶点在 $F$ 中恰有一个邻点。

任何 1-泄漏正半定强迫集都必须与这样的堡垒 $F$ 相交。事实上，假设初始蓝点集与 $F$ 不交。如果存在唯一一个在 $F$ 中恰有一个邻点的外部顶点，就把它指定为泄漏点；如果不存在，就任取一个泄漏点。考虑蓝色第一次进入 $F$ 的时刻。在此之前，$F$ 全部为白色，并且由于 $G[F]$ 连通，$F$ 的全部顶点属于同一个白色连通分支。堡垒外的蓝点若在 $F$ 中没有邻点，就不能强迫进入 $F$；若有至少两个邻点，也不能在该白色分支中进行唯一邻点强迫；唯一可能只有一个 $F$-邻点的外部顶点又被指定成了泄漏点。因此蓝色不可能第一次进入 $F$，矛盾。

在图 $G$ 中，下列各集合都是堡垒。第二列给出唯一可能在该堡垒中恰有一个邻点的外部顶点；横线表示不存在这样的外部顶点。

堡垒 $F$	唯一可能的外部顶点
$2$	$7$
$03$	$6$
$46$	$0$
$57$	$2$
$68$	$3$
$3478$	$2$
$3458$	—
$178$	$2$
$158$	—
$138$	—
$1367$	$2$
$156$	$3$
$1347$	$2$
$1345$	—
$0478$	$2$
$058$	$4$
$018$	—
$016$	$3$
$015$	$4$
$0147$	$2$

这里例如 $3478$ 表示点集 $\{3,4,7,8\}$。各集合的连通性以及第二列所列性质都可由边集直接核对。

反设 $G$ 存在一个大小至多为五的 1-泄漏正半定强迫集。由于增加初始蓝点不会破坏强迫性质，可以把它补成一个恰有五个顶点的强迫集 $S$。堡垒 $\{2\}$ 迫使

$$2\in S.$$

堡垒 $03,46,57,68$ 又迫使四点集 $S\setminus\{2\}$ 同时与这四个集合相交。满足该条件的四点集恰有以下二十个。每一行右侧给出的堡垒都与左侧四点集不交。

$S\setminus\{2\}$	与之不交的堡垒	$S\setminus\{2\}$	与之不交的堡垒
$0156$	$3478$	$0167$	$3458$
$0356$	$178$	$0367$	$158$
$0456$	$138$	$0458$	$1367$
$0467$	$138$	$0478$	$156$
$0567$	$138$	$0568$	$1347$
$0678$	$1345$	$1356$	$0478$
$1367$	$058$	$3456$	$018$
$3458$	$016$	$3467$	$015$
$3478$	$015$	$3567$	$018$
$3568$	$0147$	$3678$	$015$

因此无论怎样选择五点集 $S$，它都会漏掉上述某个堡垒。这与每个 1-泄漏正半定强迫集必须击中所有堡垒矛盾。故

$$Z^+_{(1)}(G)\ge6.$$

最后，结合已经证明的 $Z^+_{(1)}(H)\le4$，得到

$$Z^+_{(1)}(G)-Z^+_{(1)}(G-e) \ge 2,$$

从而 MathDB 361178 的猜想不成立。