r-一致D-超图的最大边数

The Maximum Number of Hyperedges of An r-Uniform D-Hypergraph

摘要:

混合超图H=（X,C,D）是一个三元组，其中X为H的顶点集。C为X的子集族，记作C-边。D为X的子集族，记作D-边。C=∅的混合超图称为D-超图，D=∅的混合超图称为C-超图。H=（X,C,D）是一混合超图，r是不小于2的正整数，若满足对任意的C-超边和D-超边，都有|C|=r，|D|=r，则称混合超图H为r-一致混合超图。特别地，若又有C=∅，则称混合超图H为r-一致D超图。在本文中，我们解决当χ（H）=k时，r-一致D-超图H的最大边数这一问题。

Abstract: A mixed hypergraph on a finite set X is a triple H=（X,C,D）, where C and D are families of subset of X. The member of C is called C-edge and the member of D is called D-edge. A mixed hypergraph is called C-hypergraph when D=∅, a mixed hypergraph is called D-hypergraph when C=∅. Let H=（X,C,D） be a mixed hypergraph, r is a positive integer not less than 2. For an arbitrary C-edge and D-edge, if we have |C|=r，|D|=r, then the mixed hypergraph H is called r-uniform mixed hypergraph. In particular, if , the mixed hypergraph H is called r-uniform mixed D-hypergraph. In this paper, we solve the problem about the maximum number of hyperedges of an r-uniform D-hypergraph when χ（H）=k.

1. 引言

1995年，Vitaly Voloshin [1] 对于超图的染色理论提出了其对偶问题，即：使某些超边中至少有两个点染相同的颜色，此类超边称为C-边，传统超边称为D-边，同时包含C-边和D-边的超图称为混合超图，记为 $H=\left(X,C,D\right)$ 。这两种超图的主要区别体现在染色上。的混合超图称为D-超图，的混合超图称为C-超图。

设是一混合超图，H的一个正常的k-染色是一个映射 $\phi$ ： $X\to \left\{1,2,\cdots ,k\right\}$ ，使得下述条件成立：

1) 每条C-边中至少有两个顶点染相同的颜色；

2) 每条D-边中至少有两个顶点染不同的颜色。

混合超图 $H=\left(X,C,D\right)$ 的一个k色严格染色是一个正常的k-染色且恰使用了k种染色。使混合超图 $H=\left(X,C,D\right)$ 有一个严格染色所需的最多(最少)的颜色数被称为H的上色数(下色数)，记作 $\bar{\chi }\left(H\right)$ ( $\chi \left(H\right)$ )。

混合超图的概念一经提出，关于混合超图的新的问题也随之产生，如对C-超图的染色的研究。C-超图的染色理论是最大顶点染色理论，因为对于C-超图来说，存在1色严格染色。而在超图中所用的最多颜色数即为超图的顶点数，故超图的染色理论是最小顶点染色理论。因此，对于混合超图来说，最小最大顶点染色理论都是有意义的。对于D-超图的染色问题已有许多结果，本文中我们将研究r-一致D-超图，我们首先给出r-一致D-超图的概念：

设 $H=\left(X,C,D\right)$ 是一混合超图，r是不小于2的正整数，若满足对任意的C-超边和D-超边，都有 $\left|C\right|=r$ ， $\left|D\right|=r$ ，则称混合超图H为r-一致混合超图。特别地，若又有 $C=\varnothing$ ()，则称H为r-一致D-超图(r-一致C-超图)。

极值问题在超图与混合超图中是有趣的而又极具挑战性的。在参考文献 [1] [2] [3] [4] 中已有一些关于混合超图的最小点数，最小边数等问题的结果。Vitaly Voloshin 在文献 [3] 中提出一个公开问题：当 $\bar{\chi }\left(H\right)\ge k$ 时，r-一致C-超图H的最大边数是多少？该问题已经在文献 [5] 中得到解决。在本文中，我们解决当 $\chi \left(H\right)=k$ 时，r-一致D-超图H的最大边数这一问题。

2. 定理及其证明

定理1 设是具有n个顶点的r-一致D-超图， $\phi$ 是顶点集X的一个k-染色且 $\chi \left(H\right)=k$ 。则H的最大边数为 $k^{r-1}c$ ，其中r充分大时，对任意的 $\lambda <\sqrt{2}$ ， $c=\lambda {\left(r/\ln r\right)}^{1/2}$ 。

断言1 存在 $p\in \left[0,1\right]$ 使得 $c{\left(1-p\right)}^r+c^{2}p<1$ 。

因为 $1-p\le {\text{e}}^{-p}$ 。当 $p=\ln \left(r/c\right)/r$ 时，函数 $c{\text{e}}^{-pr}+c^{2}p$ 取得最小值。将p代入上面的函数，若

则断言1成立。当r充分大时，对任意的 $\lambda <\sqrt{2}$ ， $c=\lambda {\left(r/\ln r\right)}^{1/2}$ ，这个不等式是成立的。因此，断言1的证明完成。

设 $H=\left(X,D\right)$ 具有 $\epsilon \left(H\right)=k^{r-1}c$ 条边且p满足上述条件。首先我们随机地用中的一种颜色逐个给H的顶点着色。其次对于每个顶点v，我们抛掷硬币，出现正面的概率为p。另外，对V中的顶点随机排序。

步骤1. 随机地用 $\left\{1,2,\cdots ,k\right\}$ 中的一种颜色逐个给H的顶点着色，称之为第一次染色。令B表示位于某条(可能多条)单色边 $e\in E$ 中的点 $v\in V$ 的集合。

步骤2. 按V中顶点的顺序依次考虑B中的元素。当我们考虑b时，若存在某条(可能多条)包含b的边 $e\in H$ 在第一次染色中是单色的且这条边中至今没有顶点改变颜色，则称b仍然危险。若b不是仍然危险的，则保持原有染色。但若b是仍然危险的，则抛掷硬币。若出现正面则改变b的颜色，否则保持原有染色。我们称终止时的染色为最终染色。

坏事件 在最终的染色中，某条边是单色的。

在最终的染色中，边 $e\in E$ 是单色的有两种情况。要么在第一次染色中，边e是单色的且在最终的染色中，边e仍然是单色的；要么在第一次染色中，边e不是单色的但在最终的染色中，边e是单色的。第一种情况记作 $A_e$ ，第二种情况记作 $B_e$ 。在第一次染色中，边e是单色的概率为 ${\left(\frac{1}{k}\right)}^r$ ，在最终的染色中，所有的硬币出现反面的概率为，即边e仍然是单色的概率为 ${\left(\frac{1}{k}\right)}^r$ ，则

故

$k{\displaystyle \underset{e\in H}{\sum }\mathrm{Pr}\left[A_e\right]}=c{\left(1-p\right)}^r$

为了避免过度重染且得到更好的界，我们巧妙地界定 $\mathrm{Pr}\left[B_e\right]$ 。对于不同的边 $e,f\in E$ ，若

1) 边 $e,f$ 恰重叠一个元素，记作v；

2) 在第一次染色中边f是单色的且在最终的染色中e是单色的；

3) 在步骤2中，点v是边e中最后一个改变颜色的点；

4) 当考虑点v时，边f仍然是单色的；

则称边e取决于边f。

假设 $B_e$ 成立。因边e中的某些点会改变染色，故存在最后一个改变颜色的点v。但对于点v，为什么仍要抛掷硬币？因为点v一定存在于某条(可能多条)边f中，边f在第一次染色中是单色的且当考虑点v时，边f仍然是单色的。那么边 $e,f$ 会重叠另一个点 $v^{\prime }$ ？答案是否定的。因为点 $v^{\prime }$ 一定在点v之前改变颜色，则当考虑点v时，边f不再是完全单色的，与边f的假设矛盾。因此当 $B_e$ 成立时，边e取决于边f。令 $C_{ef}$ 表示事件边e取决于边f，则。

设边 $e,f$ 固定且 $e\cap f=\left\{v\right\}$ (否则 $C_{ef}$ 不发生)。顶点集V的随机排序导致了 $e\cup f$ 的一个随机排序 $\sigma$ 。令 $i=i\left(\sigma \right)$ ( $i>0$ )表示在点v之前点 $v^{\prime }\in e$ 的数量， $j=j\left(\sigma \right)$ 表示在点v之前的点 $v^{\prime }\in f$ 的数量。

由上述讨论知，计算 $\mathrm{Pr}\left[C_{ef}\right]$ 须同时满足以下几点。首先，在第一次染色中，边f是单色的，在最终的染色中，点v一定会改变颜色。其次，对点v之前的点 $v^{\prime }\in f$ 进行抛掷硬币时全部是反面朝上。再者，点v之后的点 $v^{\prime }\in e$ 的颜色起初就相同(因为点v是边e中最后一个改变颜色的顶点)。最后，随机从 $\left\{1,2,\cdots ,k\right\}$ 中选择颜色对点v之前的点进行染色且最终染色与点v之后的顶点颜色相同。

固定得到

$\mathrm{Pr}\left[C_{ef}|\sigma \right]\le {\left(\frac{1}{k}\right)}^{r}p{\left(1-p\right)}^j{\left(\frac{1}{k}\right)}^{r-i-1}{\left(\frac{1+p}{k}\right)}^i$

故

$\mathrm{Pr}\left[C_{ef}\right]\le k^{1-2r}pE\left[{\left(1+p\right)}^i{\left(1-p\right)}^j\right]$

引理4 [6] $E\left[{\left(1+p\right)}^i{\left(1-p\right)}^j\right]\le 1$ 。

因为至多存在对边 $e,f$ 且边 $e\ne f$ ，则

因此坏事件出现的概率为 $c{\left(1-p\right)}^k+c^{2}p$ 。由断言1，坏事件不发生的概率为正。这表明存在一种无单色边e的染色。因此，定理1的证明完成。

致谢

感谢导师蔡建生教授给我们介绍混合超图的相关知识，并对本文进行了全面的修改。最后，向各位尊敬的评审专家致以诚挚的感谢，谢谢你们对本论文做出的评审以及提出的宝贵意见。