请教一个图论问题

maomaoxiangcao

一个二部图，左边有 12 个点，对于左边的任意大小为 8 的点集，右边都恰有 16 个点与之相连；对于左边的任意大小为 10 的点集，右边都恰有 20 个点与之相连，求证：右边共有 24 个点和左边的点有联边。

Czhang271828

hbghlyj 发表于 2023-8-1 04:00
设左边的顶点为$A_1,\dots,A_{12}$，
对于10个点$A_1,\dots,A_{10}$右边恰有 20 个点与之相连，记为集合$\m ...

对 $\geq$ 的简单证明.

显然对任意大小为 $10-8=2$ 的点集, 总有至少 $20-16=4$ 个点与之相连. 设右侧共 $n$ 个点, 则对任意大小为 $12-10=2$ 的点集, 至少有 $n-20$ 个点与之相连, 从而 $n-20\geq 4$.

以上表明"左侧 $2$ 点恰连右侧 $4$ 点", 类似的取等条件如"左侧 $4$ 点恰连右侧 $8$ 点". 因此二部图的结构是"左侧每 $2$ 点连右侧 $4$ 点, 分作 $6$ 个连通分支".

以及好久没回论坛了.

hbghlyj

hbghlyj 发表于 2023-8-1 04:00
设左边的顶点为$A_1,\dots,A_{12}$，
对于10个点$A_1,\dots,A_{10}$右边恰有 20 个点与之相连，记为集合$\mathcal B_1$
对于10个点$A_3,\dots,A_{12}$右边恰有 20 个点与之相连，记为集合$\mathcal B_2$
对于8个点$A_3,\dots,A_{10}$右边恰有 16 个点与之相连，记为集合$\mathcal B_3$
因为$\{A_1,\dots,A_{10}\}\cup\{A_3,\dots,A_{12}\}=\{A_1,\dots,A_{12}\}$，要证的等价于$\abs{\mathcal B_1\cup\mathcal B_2}=24$.
因为$\{A_1,\dots,A_{10}\}\cap\{A_3,\dots,A_{12}\}=\{A_3,\dots,A_{10}\}$，所以$\mathcal B_3\subseteq\mathcal B_1\cap\mathcal B_2$
\begin{align*}\abs{\mathcal B_1\cup\mathcal B_2}&=\abs{\mathcal B_1}+\abs{\mathcal B_2}-\abs{\mathcal B_1\cap\mathcal B_2}\\
&\le\abs{\mathcal B_1}+\abs{\mathcal B_2}-\abs{\mathcal B_3}\\
&=20+20-16=24\end{align*}
还剩证$\ge$不会

我转发到 math.stackexchange.com/questions/4966892/
相關資料：essay.utwente.nl/92667/1/Tilburg_BA_CS_EEMCS.pdf
Theorem 3.6. Given a bipartite graph $G = (V_0, V_1, E)$, the coverage function $f$ is sub-modular.
Proof. Since $N (X)∩N (Y ) ⊇ N (X ∩Y )$ and $N (X)∪N (Y ) = N (X ∪Y )$, the non-negativity of the cardinality function implies at once the submodular inequality.

hbghlyj

如何理解藍色文字

Matthias Kaul answered 2023-9-5
($|N(X)| \leq 4$):

This direction is a bit harder. Observe that any two element set $X'$ fulfills the following:
$$
|N(X') \setminus N(Y)| \geq 4 \; \forall Y \subseteq U \setminus X', |Y| \leq 8.
$$This follows directly from submodularity of the neighbourhood function and the fact that the reduced value of every two element set is known to be $4$ respective to any disjoint set of cardinality $8$.
If this does not make you happy, it can also be seen by purely combinatorial means, but this is left as an exercise for the reader.

hbghlyj

$|X'|=2,|Y|=8,X'\cap Y=\emptyset$
$|N(Y)|=16,N(X'\cup Y)=N(X')\cup N(Y)$
$|N(X')\setminus N(Y)|+|N(Y)|=|N(X'\cup Y)|=20,$
$\implies|N(X') \setminus N(Y)|=4$. 证明是这样的吗？