问题描述

设 $n$ 是正整数，$n$ 阶简单无向图 $G$ 的一个子图 $H$ 称为好的：如果 $H$ 的每个连通分支不是一条边就是一个圈。 若 $G$ 的每个好子图 $H$ 顶点数不超过 $\dfrac45n$，证明或证伪：$G$ 的边数不超过 $\dfrac8{25}n^2$。

解答

命题成立。事实上，对任意正整数 $n$，均有严格不等式

$$e(G)<\frac{8}{25}n^2.$$

记 $\mu(G)$ 为 $G$ 的好子图所能覆盖的最大顶点数。首先建立一个关于 $\mu(G)$ 的公式。

引理

对任意图 $G=(V,E)$，有

$$\mu(G) = |V|-\max_{X\subseteq V}\bigl(|X|-|N(X)|\bigr),$$

其中 $N(X)$ 表示 $X$ 中顶点的所有邻点组成的集合，允许 $N(X)$ 与 $X$ 相交。并且上式中的最大值可以只在独立集 $X$ 中选取。

引理证明

构造二部图 $B$：左右两侧各放置一份 $V$，分别记为 $V_L,V_R$；当 $uv\in E(G)$ 时，在 $B$ 中加入边 $u_Lv_R$ 和 $v_Lu_R$。

设 $B$ 的最大匹配数为 $\nu(B)$。

若 $H$ 是覆盖 $q$ 个顶点的好子图，则：

• 对于 $H$ 的一个边分支 $uv$，在 $B$ 中选取 $u_Lv_R$ 和 $v_Lu_R$；
• 对于圈 $v_1v_2\cdots v_kv_1$，在 $B$ 中选取$$(v_1)_L(v_2)_R,\ (v_2)_L(v_3)_R,\ldots,(v_k)_L(v_1)_R.$$

不同分支之间顶点不相交，所以这些二部图边构成一个大小为 $q$ 的匹配。因此

$$\nu(B)\geq \mu(G).$$

反过来，设 $B$ 中有一个大小为 $q$ 的匹配。将匹配边 $u_Lv_R$ 看作有向边 $u\to v$。所得有向图中每个顶点的入度、出度均不超过 $1$，故每个含边的弱连通分支是一条有向路或一个有向圈。

• 有向圈若长度至少为 $3$，其无向边构成 $G$ 中的一个圈；长度为 $2$ 时，对应 $G$ 中的一条边。
• 一条有 $\ell$ 条边的有向路，在其无向路上交替选边，可以覆盖$$2\left\lfloor\frac{\ell+1}{2}\right\rfloor\geq \ell$$个顶点。

于是可以在 $G$ 中得到一个覆盖至少 $q$ 个顶点的好子图。因此

$$\mu(G)\geq \nu(B),$$

从而

$$\mu(G)=\nu(B).$$

再使用 Hall 定理的缺陷形式。令

$$d=\max_{X\subseteq V}\bigl(|X|-|N(X)|\bigr).$$

对任何匹配，集合 $X$ 中至多有 $|N(X)|$ 个顶点被匹配，因此至少有 $d$ 个左侧顶点未匹配，故

$$\nu(B)\leq n-d.$$

另一方面，在 $B$ 的右侧加入 $d$ 个新顶点，并让它们与所有左侧顶点相邻。对任意 $X\subseteq V_L$，有

$$|N_B(X)|+d\geq |X|.$$

由 Hall 定理，新二部图存在饱和全部 $n$ 个左侧顶点的匹配。删除与新顶点相连的至多 $d$ 条匹配边后，原二部图中仍有一个大小至少为 $n-d$ 的匹配。因此

$$\nu(B)=n-d.$$

最后说明最大值可以在独立集中取得。对任意 $X\subseteq V$，令

$$I=X\setminus N(X).$$

$I$ 是独立集，并且

$$N(I)\subseteq N(X)\setminus X.$$

因此

$$\begin{aligned} |I|-|N(I)| &\geq |X\setminus N(X)|-|N(X)\setminus X|\\ &=|X|-|N(X)|. \end{aligned}$$

故最大缺陷确实可以由某个独立集达到，引理得证。

---

回到原问题。题设给出

$$\mu(G)\leq \frac45n.$$

由引理，存在独立集 $I\subseteq V(G)$，使得

$$|I|-|N(I)| =n-\mu(G) \geq \frac15n.$$

记

$$i=|I|,\qquad S=N(I),\qquad s=|S|.$$

于是

$$i-s\geq \frac15n.$$

令

$$R=V(G)\setminus(I\cup S).$$

因为 $I$ 是独立集，且 $S=N(I)$，所以：

• $I$ 内部没有边；
• $I$ 与 $R$ 之间没有边。

因此，$G$ 的边只可能位于 $V\setminus I$ 内部，或者连接 $I$ 与 $S$。于是

$$e(G)\leq \binom{n-i}{2}+is \leq \frac12(n-i)^2+is.$$

令

$$a=\frac{i}{n},\qquad b=\frac{s}{n}.$$

由 $i-s\geq n/5$ 以及 $i+s\leq n$，得到

$$a-b\geq\frac15,\qquad a+b\leq1.$$

也就是

$$b\leq \min\left\{a-\frac15,\,1-a\right\}, \qquad a\geq\frac15.$$

同时

$$\frac{e(G)}{n^2} \leq \frac12(1-a)^2+ab.$$

分两种情况讨论。

情况一：$\dfrac15\leq a\leq\dfrac35$。

此时 $a-\dfrac15\leq1-a$，所以

$$b\leq a-\frac15.$$

从而

$$\frac{e(G)}{n^2} \leq \frac12(1-a)^2+a\left(a-\frac15\right) = \frac12-\frac65a+\frac32a^2.$$

右端是关于 $a$ 的凸二次函数，因为其二阶导数为 $3>0$，所以它在区间 $\left[\frac15,\frac35\right]$ 上的最大值出现在端点。两个端点处均有

$$\frac12-\frac65a+\frac32a^2=\frac8{25}.$$

故

$$e(G)\leq\frac8{25}n^2.$$

情况二：$\dfrac35\leq a\leq1$。

此时利用 $b\leq1-a$，得到

$$\begin{aligned} \frac{e(G)}{n^2} &\leq \frac12(1-a)^2+a(1-a)\\ &=\frac12(1-a^2)\\ &\leq\frac12\left(1-\frac9{25}\right) =\frac8{25}. \end{aligned}$$

两种情况均得到

$$\boxed{e(G)\leq\frac8{25}n^2}.$$

所以题目中的命题为真。

此外，这个二次项常数不能改小。例如当 $5\mid n$ 时，取大小分别为 $\frac35n$ 和 $\frac25n$ 的集合 $I,S$，令 $I$ 为独立集、$S$ 为完全图，并加入 $I$ 与 $S$ 之间的所有边。此时

$$\mu(G)=\frac45n$$

且

$$e(G) = \frac35n\cdot\frac25n+\binom{\frac25n}{2} = \frac8{25}n^2-\frac15n.$$

因此 $\frac8{25}$ 是渐近最优的常数。

检查

• “好子图”被准确转化为由互不相交的边和圈组成的顶点覆盖，没有加入孤立点或路径分支。
• 二部图匹配与好子图最大覆盖顶点数之间的两个方向均已证明；有向路产生的好子图至少覆盖匹配边数对应的顶点数。
• Hall 缺陷公式给出了独立集 $I$，满足 $|I|-|N(I)|\geq n/5$，完整使用了题设条件。
• 由于 $I$ 独立且 $N(I)=S$，边数估计$$e(G)\leq\binom{n-i}{2}+is$$ 没有遗漏任何可能的边。
• 参数约束 $a-b\geq1/5$、$a+b\leq1$ 均已使用，分界点 $a=3/5$ 来自$$a-\frac15=1-a.$$
• 两种参数范围覆盖全部可能情形，端点计算均为 $8/25$。
• 当 $n$ 不能被 $5$ 整除时，$\mu(G)$ 的整数性只会使条件更强，不影响证明。
• 实际上使用$$\binom{n-i}{2}<\frac12(n-i)^2$$ 并结合其余等号条件可知正整数 $n$ 时最终等号不会真正取得，但题目要求的非严格上界完全成立；所给构造说明二次项常数渐近最优。

核心思路总结

最关键的步骤是把“边和圈的不交并”转化为图的二部双覆盖中的匹配。Hall 定理的缺陷形式随后给出一个独立集 $I$，其顶点数比邻集 $N(I)$ 至少多 $n/5$。

这一独立集形成了边数结构上的障碍：$I$ 内无边，且 $I$ 与其邻集之外的顶点之间也无边。因此所有边只能位于 $V\setminus I$ 内部或连接 $I$ 与 $N(I)$。最后只需对两个归一化参数做一个分段二次函数估计，即得到常数 $8/25$。

核心工具是：

• 二部双覆盖；
• Hall 婚配定理的缺陷形式；
• 独立集与邻集的边数分割；
• 简单的凸二次函数极值估计。

参考资料

无。

---

问题描述

设 $p$ 为奇素数，$S$ 是 $\{1,2,\cdots,p-1\}$ 的一个至少有 $p^{\frac34}$ 个元素的集合。证明 $S\cdot S+S\cdot S=\{ab+cd:a,b,c,d\in S\}$ 覆盖 mod $p$ 的所有非零余数。

解答

把 $\{1,2,\dots,p-1\}$ 看作有限域 $\mathbb F_p$ 的非零元素集合。记

$$n=|S|,\qquad P=S\times S\subseteq \mathbb F_p^2,\qquad m=|P|=n^2.$$

任取 $x\in\mathbb F_p^\times$。我们证明存在 $\boldsymbol u,\boldsymbol v\in P$，使得

$$\boldsymbol u\cdot\boldsymbol v=x.$$

若写成

$$\boldsymbol u=(a,c),\qquad \boldsymbol v=(b,d),$$

这就等价于 $ab+cd=x$，其中 $a,b,c,d\in S$。

对每个 $\boldsymbol u\in\mathbb F_p^2$，定义

$$\nu(\boldsymbol u) = \left|\left\{\boldsymbol v\in P: \boldsymbol u\cdot\boldsymbol v=x\right\}\right|.$$

于是所求表示的总数为

$$N_x=\sum_{\boldsymbol u\in P}\nu(\boldsymbol u).$$

下面估计 $\nu(\boldsymbol u)$ 的二阶矩。

首先，因为 $P$ 中的向量都是非零向量，所以对每个固定的 $\boldsymbol v\in P$，方程

$$\boldsymbol u\cdot\boldsymbol v=x$$

关于 $\boldsymbol u$ 的解组成一条仿射直线，恰有 $p$ 个解。因此

$$\sum_{\boldsymbol u\in\mathbb F_p^2}\nu(\boldsymbol u)=pm.$$

其次，

$$\sum_{\boldsymbol u\in\mathbb F_p^2}\nu(\boldsymbol u)^2$$

等于三元组 $(\boldsymbol u,\boldsymbol v,\boldsymbol w)$ 的个数，其中 $\boldsymbol v,\boldsymbol w\in P$，并且

$$\boldsymbol u\cdot\boldsymbol v=x, \qquad \boldsymbol u\cdot\boldsymbol w=x.$$

分别讨论 $\boldsymbol v,\boldsymbol w$：

• 若 $\boldsymbol v,\boldsymbol w$ 线性无关，则这两个线性方程唯一确定 $\boldsymbol u$，因而恰有一个解；
• 若 $\boldsymbol v=\boldsymbol w$，则只有一个非退化线性方程，恰有 $p$ 个解；
• 若 $\boldsymbol v,\boldsymbol w$ 线性相关但不相等，设 $\boldsymbol w=\lambda\boldsymbol v$，其中 $\lambda\ne1$。两个方程将给出$$x=\boldsymbol u\cdot\boldsymbol w =\lambda(\boldsymbol u\cdot\boldsymbol v) =\lambda x.$$因为 $x\ne0$，这将迫使 $\lambda=1$，产生矛盾，所以此时无解。

设 $D$ 是 $P^2$ 中线性相关且不相等的有序向量对数。线性无关的有序对数为 $m^2-m-D$，故

$$\begin{aligned} \sum_{\boldsymbol u\in\mathbb F_p^2}\nu(\boldsymbol u)^2 &=(m^2-m-D)+pm\\ &=m^2+(p-1)m-D\\ &\le m^2+(p-1)m. \end{aligned}$$

由于 $\mathbb F_p^2$ 有 $p^2$ 个元素，而 $\nu$ 在整个平面上的平均值为 $m/p$，所以

$$\begin{aligned} \sum_{\boldsymbol u\in\mathbb F_p^2} \left(\nu(\boldsymbol u)-\frac{m}{p}\right)^2 &= \sum_{\boldsymbol u}\nu(\boldsymbol u)^2 -\frac{2m}{p}\sum_{\boldsymbol u}\nu(\boldsymbol u) +p^2\left(\frac{m}{p}\right)^2\\ &= \sum_{\boldsymbol u}\nu(\boldsymbol u)^2-m^2\\ &\le (p-1)m. \end{aligned}$$

因此由柯西不等式，

$$\begin{aligned} \left|N_x-\frac{m^2}{p}\right| &= \left| \sum_{\boldsymbol u\in P} \left(\nu(\boldsymbol u)-\frac{m}{p}\right) \right|\\ &\le \sqrt{|P|} \left( \sum_{\boldsymbol u\in\mathbb F_p^2} \left(\nu(\boldsymbol u)-\frac{m}{p}\right)^2 \right)^{1/2}\\ &\le m\sqrt{p-1}. \end{aligned}$$

从而

$$N_x\ge \frac{m^2}{p}-m\sqrt{p-1} =m\left(\frac{m}{p}-\sqrt{p-1}\right).$$

题设给出 $n\ge p^{3/4}$，所以

$$m=n^2\ge p^{3/2}.$$

于是

$$\frac{m}{p}\ge \sqrt p>\sqrt{p-1},$$

故 $N_x>0$。因此存在 $a,b,c,d\in S$，使得

$$ab+cd\equiv x\pmod p.$$

由于 $x$ 是任意非零余数，得到

$$S\cdot S+S\cdot S\supseteq\mathbb F_p^\times.$$

也就是说，$S\cdot S+S\cdot S$ 覆盖模 $p$ 的所有非零余数。

值得指出的是，上述证明实际上对任意素数 $p$ 都成立，因此题目中的条件 $p\equiv1\pmod4$ 是一个可以去掉的冗余条件。

检查

• 已将 $S$ 中元素视为 $\mathbb F_p^\times$ 中的元素，没有混淆整数运算与模 $p$ 运算。
• $P=S\times S$ 中不含零向量，因此方程 $\boldsymbol u\cdot\boldsymbol v=x$ 对固定 $\boldsymbol v\in P$ 确有 $p$ 个解。
• 二阶矩中完整讨论了线性无关、相等、线性相关但不等三种情形；第三种情形用到了目标余数 $x\ne0$。
• 柯西不等式中的求和范围从 $P$ 扩大到 $\mathbb F_p^2$，被求和项为平方，因此方向正确。
• 临界规模下仍有严格正性，因为$$\sqrt p>\sqrt{p-1}.$$ 所以即使 $|S|$ 恰好达到允许的最小整数，也不会出现主项与误差相等的问题。
• 结论对每个 $x\in\mathbb F_p^\times$ 分别成立，因而确实覆盖全部非零余数。
• 另对 $p=5,13$ 的所有满足规模条件的集合进行了穷举核验，未发现反例。

核心思路总结

最关键的构造是把

$$ab+cd=x$$

改写为二维向量的点积方程

$$(a,c)\cdot(b,d)=x.$$

随后对点积关联数 $\nu(\boldsymbol u)$ 计算二阶矩。两个非零向量线性无关时，相应的两个线性方程有唯一解；线性相关但不相等时，由于 $x\ne0$，方程组无解。这给出误差估计

$$\left|N_x-\frac{|S|^4}{p}\right| \le \sqrt{p-1}\,|S|^2.$$

最后利用 $|S|\ge p^{3/4}$，证明主项严格大于误差。核心工具是二维线性方程组计数、二阶矩方法和柯西不等式。

参考资料

无。