大均匀超图中大最小集体度的完美匹配
184 浏览量
更新于2024-07-14
收藏 386KB PDF 举报
"这篇文章是Vojtech Rödl, Andrzej Ruciński和Endre Szemerédi合著的，发表在2009年的《组合论杂志，系列A》上，探讨了大尺寸均匀超图中完美匹配与最小集体度的关系。研究集中在当k>=3时，超图中最小(k-1)度（δk−1(H)）如何影响完美匹配的存在性。文章提出了t(k,n)这个术语，表示n个节点的k均匀超图至少需要满足的δk−1(H)阈值，以便保证存在完美匹配。对于大的n值且能被k整除的情况，作者们完全确定了t(k,n)的值。"
在这篇论文中，作者们关注的是组合数学中的一个重要领域——超图的完美匹配问题。超图是图论的一个扩展，其中边可以连接多个节点，而不仅仅是两个。在标准图中，完美匹配是指每对节点都恰好被一条边连接，使得所有节点都被覆盖且没有多余的边。在k-统一超图中，完美匹配定义为包含⌊n/k⌋个不相交的边，这些边覆盖了所有的n个节点。
最小集体度（δk−1(H)）是超图的一个关键属性，它指的是超图中任意(k-1)个节点都至少共同参与了d条边。这个度量反映了超图的连通性和密集程度。在研究中，作者们试图找出δk−1(H)的下限，使得超图一定存在完美匹配。他们定义的t(k,n)就是这个下限，即只要超图的δk−1(H)大于或等于t(k,n)，那么这个k-统一超图就一定能找到一个完美匹配。
论文的重点在于分析这个下限t(k,n)与超图大小n以及均匀度k之间的关系。对于n能被k整除的大规模超图，作者们成功地给出了t(k,n)的确切值，这为理解和构建大尺寸均匀超图的完美匹配提供了理论基础。此外，这项工作还涉及到图论和组合优化中的其他关键概念，如图的连通性、度分布和匹配理论。
关键词：超图、完美匹配、最小度、组合优化
该论文的接收日期为2007年10月2日，于2008年11月17日在线发布，并由Ronald L. Graham推荐。这是一项深入的理论研究，对于理解大规模组合结构的性质以及在实际应用中寻找最优解决方案具有重要意义，特别是在数据建模、网络设计和算法开发等领域。
V. Rödl et al. / Journal of Combinatorial Theory, Series A 116 (2009) 613–636 617
tices (see Fig. 3). Thus, there are at least δ
k−1
(H) − j −1choicesof
v
j
,
j
=k −2, k −1, k
.Altogether,
there are at least
(n − 2
k
)
k−3
choices of
v
1
,...,v
k−3
, followed by at least (δ
k−1
(H) − 2
k
)
3
choices
of
v
k−2
, v
k−1
, v
k
.Forlarge
n
,thisyieldstherequiredbound. 2
Fact 2.3. For all c > 0 there exist C > 0 and n
0
such that if H is a k-uniform hypergraph with n n
0
vertices
and
δ
k−1
(H) cn, then there exists a matching M
in H of size |M
| C
log
nandsuchthatforevery(k +1)-
tuple S of vertices of H , the number of S-absorbing edges in M
is at least k −2.
Proof. The proof is probabilistic. Select a random subset
M
of
H
, where each edge is chosen inde-
pendently with probability
p
= C (log
n
)n
−k
. Then, the expected size of
M
is at most
n
k
p < n
k
p/k!,
and the expected number of intersecting pairs of edges in
M
is at most
n
2
k
−1
p
2
= o(1).Hence,by
Markov’s inequality,
M
is a matching of size at most
C
log
n
with probability at least 1 − 1/k!−o(1).
For every
(k + 1)-tuple of vertices
S
,let
X
S
be the number of
S
-absorbing edges in
M
. Then, by
Fact 2.2,
E X
S
c
3
n
k
p
2
k
!
=
Cc
3
log
n
2
k
!
.
By Chernoff’s bound (see, e.g., [2, Theorem 2.1]),
P
X
S
1
2
E X
S
exp
−
1
8
E X
S
exp
−
Cc
3
log
n
16
k
!
=
o
n
−k−1
if
C
> 16(k + 1)!/c
3
. Thus, with probability 1 −o(1),foreach(k +1)-tuple
S
of the vertices in
V
(H),
there are at least
1
4k!
c
3
C log n > 4(k + 1) log n k −2
S-absorbing edges in M
. In conclusion, with positive probability M
has all the properties listed in
the statement of Fact 2.3, and thus such a matching M
exists. 2
Now we are ready to give a short proof of the upper bound in Proposition 2.1.
Proof of Proposition 2.1. Let H be a k-uniform hypergraph with
δ
k−1
(H) n/k + Cklogn and n ver-
tices, n
n
0
, where C and n
0
are determined by Fact 2.3 with c = 1/k.LetM
be a matching in H
as described in Fact 2.3 and let H
= H − V (M
) be the sub-hypergraph of H induced by V \ V (M
).
Note that n
:= |V (H
)|=n −k|M
|, |M
| C log n, and
δ
k−1
(H
) δ
k−1
(H) −Cklog n
n
k
>
n
k
.
Thus,byFact2.1,thereisinH
amatchingM
of size |M
| n
/k−k +2. This matching leaves at
most
(k −2)k +k −1verticesofH
uncovered.
Let T
= V (H) \ V (M
∪ M
), |T | (k − 2)k +k − 1. As long as the number of uncovered vertices
remains at least k
+ 1, we repeat the following absorbing procedure. Recall that for every (k + 1)-
tuple S of the vertices of H , the number of S-absorbing edges in M
is at least k − 2. Take a set S
of k
+ 1 uncovered vertices and find in M
an S-absorbing edge e.ReplaceM
by M
S
:= M
\{e}∪
{
e
1
, e
2
} (see Definition 2.1), decreasing the number of uncovered vertices by k. Since we only have at
most k
−2 iterations, there will always be an available (unused) S-absorbing edge in M
.Intheend,
we obtain a matching
M
with V (M
) ⊆ V (M
) ∪ T and |M
|=|M
|+|T |/k.Butthen|M
∪ M
|=
n/k as needed. 2
We conjecture that for all k 3, if n ≡0 (mod k) then t(k, n) =n/k.
Remark 2. 1 . For
1 and n k,lett
()
(k,n) be the smallest integer t such that for every k-uniform
hypergraph H on n vertices and with
δ
k−1
(H) t,wehaveν(H) n/k−. Using Fact 2.1 and
剩余23页未读，继续阅读
点击了解资源详情
点击了解资源详情
点击了解资源详情
2021-04-22 上传
2021-04-22 上传
2021-04-22 上传
2021-04-22 上传
2021-04-22 上传
2021-04-22 上传
代码加烟，法力无边
- 粉丝: 183
我的内容管理
展开
最新资源
- pymatgen库安装指南：适用于macOS的Python扩展
- 深入解析MySQL分区及其优化应用
- Python挑战：深入解压缩包子文件技术
- 提升读写速度的DELL H310/H710磁盘阵列驱动
- 响应式视差效果的6页模板设计与CSS应用
- 电子企业商务网页模板设计指南
- CSS技术应用：tarea-clase-8解析
- Python库PyMatching-0.2.2版本安装包发布
- STM8CubeMX软件安装包 - PC端初始化代码生成器
- Parsley开源工具的源码分析
- 生化试剂指南：现代化学试剂手册第三分册详述
- UnCT：开源的通用系统管理与配置工具
- BSumangHelloWorld:Java语言入门测试示例
- 深入解析HTML格式化技术要点
- Python脚手架：轻松构建深度学习模型的解决方案
- STM32F103驱动AGS01DB传感器实现IIC通信测量TVOC与CO2
