超图分数着色
《Discrete Applied Mathematics》:Fractional hypergraph coloring
【字体:
大
中
小
】
时间:2026年09月28日
来源:Discrete Applied Mathematics 1.1
编辑推荐:
摘要我们研究n-正则超图的(a:b)-分数染色问题,这是传统图整数染色的推广。每个顶点从一组a种颜色中被分配b种不同颜色,若某条边的所有顶点不同时共享某一种颜色,则称该边被正确染色。若超图的每条边都被正确染色,则称该超图是(a:b)-可染色的。我们证明:对于任意2≤b≤a?2
摘要我们研究n-正则超图的(a:b)-分数染色问题,这是传统图整数染色的推广。每个顶点从一组a种颜色中被分配b种不同颜色,若某条边的所有顶点不同时共享某一种颜色,则称该边被正确染色。若超图的每条边都被正确染色,则称该超图是(a:b)-可染色的。我们证明:对于任意2≤b≤a?2以及a≤n/(2ln n),每个满足|E(H)|≤(ab/3)^(-1/2)·(n ln n)^(1/2)·(a/b)^(n-1)的n-正则超图H都是(a:b)-可染色的。我们还给出了相应的概率上界,并讨论了若干特殊情况。
引言图染色是组合学中的一个经典课题,在调度、编码理论和资源分配等领域有着广泛的应用。在图G的正常顶点染色中,每个顶点被赋予一种颜色,且相邻顶点必须被赋予不同颜色。图的分数染色可以从两个互补的角度来引入。
第一个角度来自多色染色。图G的一种(a:b)-染色为每个顶点分配一个[a]的b元子集,使得相邻顶点获得的子集互不相交。满足此条件的最小整数a称为b重色数,记为χ_b(G)。分数色数则通过对这些多色染色进行归一化得到:χ_f(G)=inf_{b≥1} χ_b(G)/b。这种方法与Stahl[25]等人对图的多色染色的研究密切相关。
第二个等价的角度来自线性规划。不是选择有限个独立集的集合,而是为独立集分配非负权重。若I(G)表示G的独立集族,则χ_f(G)=min Σ_{I∈I(G)} w_I,满足:对每个v∈V(G),Σ_{I?v} w_I≥1,且w_I≥0。这种线性规划解释将分数染色与分数覆盖联系起来,并在分数图论中得到了系统发展;参见Lovász[15]、Gr?tschel, Lovász和Schrijver[10],以及Scheinerman和Ullman的专著[23]。
这些解释也说明了为什么分数染色在应用中自然出现。在调度和课表安排问题中,顶点可以代表任务,边代表不能被分配到同一时间槽的任务对。如果所有任务的处理时间均为单位时间,且每种颜色代表一个时间槽,那么冲突图的色数即为完成所有任务且不产生冲突所需的最少时间槽数量。分数染色通过允许任务或资源在多个时间段之间进行划分来细化这一模型。例如,参见图1,其中分数染色可以给出2.5小时而非3小时。更一般的染色型调度框架也得到了研究;例如,Machacek引入了由形式为x_i≠x_j的布尔约束定义的图式调度问题,它推广了正常的图和超图染色[16]。分数染色也出现在编码理论中,用于设计高效的纠错码以及控制重叠码字之间的冲突;参见[11]、[17]。
现在我们从图转向超图。超图是一个二元组H=(V,E),其中V是顶点集,E是V的若干子集族,称为边。若超图的每条边恰好包含n个顶点,则称其为n-正则的。在超图的传统正常染色中,每个顶点被赋予一种颜色,且不允许任何边被单色化。
在本文中,我们研究均匀超图的图分数染色的类似物。在超图的一种正常(a:b)-染色中,每个顶点从a种颜色的集合中被分配b种不同颜色。若某条边的所有顶点不同时共享某一种颜色,则称该边被正确染色。若超图的每条边都被正确染色,则称该超图是(a:b)-可染色的。当所有边的规模为2时,此定义与图的一般(a:b)-染色一致。
这一概念包含若干经典染色问题作为特殊情况。对于b=1,(a:1)-可染性即为超图的一般正常a-可染性。对于b=a?1,(a:a?1)-可染性等价于全色a-可染性。回忆一下,全色a-染色是指每个顶点从[a]中获得一种颜色,且每条边至少包含每种颜色的一个顶点的染色。这一等价性可以如下理解。在一种(a:a?1)-染色中,每个顶点恰好获得a?1种颜色,因此恰好缺少一种颜色。若将每个顶点缺失的颜色赋予该顶点,则在(a:a?1)-染色与标准的每个顶点恰好有一种颜色的a-染色之间建立了一个双射。一种正常的(a:a?1)-染色确保了每条边至少包含一个缺少颜色1的顶点、一个缺少颜色2的顶点,以此类推,对所有a种颜色均如此。考虑这些缺失颜色,这直接转化为一种全色a-染色,其中每条边包含所有a种颜色。反之,任何全色a-染色都可以通过为每个顶点赋予除其当前颜色外的所有颜色来转化为一种正常的(a:a?1)-染色。
经典的Erd?s–Hajnal问题要求找出一个不能被正常2-染色的n-正则超图所需的最小边数m(n)。在1963–1964年,Erd?s[6]、[7]证明了存在绝对常数c,C>0使得c·2^n≤m(n)≤C·2^n·n^2。后来,Radhakrishnan和Srinivasan[18]改进了下界,证明存在绝对常数c'>0使得m(n)≥c'·2^n·(n ln n)^(1/2)。
该问题自然推广到r>2种颜色的情形。设m(n,r)表示一个不能被正常r-染色的n-正则超图的最小边数。对于r远小于n的情形,已知最佳界的形式为c_1·(n ln n)^((r-1)/r)·r^(n-1)≤m(n,r)≤c_2·n^2·r^(n)·ln r,其中c_1,c_2>0为绝对常数。下界由Cherkashin和Kozik[5]证明,而上界来自Erd?s的一个结果;参见Kostochka的论文[12]中的证明。对于小n值时m(n)的界以及构造性例子,可参见例如[4]、[8]、[9]、[13]、[19]、[22]。
Kostochka[12]还研究了该问题的全色类似物。具体来说,他研究了不允许全色r-染色的n-正则超图的最小边数,并将此数记为p(n,r)。更多信息和最新结果请参见[1]、[3]以及综述文献[20]、[21]。
随机超图的分数可染性也得到了研究。随机超图H(n,k,p)有n个顶点,每个k元子集作为边以概率p独立地被包含。在[14]、[24]、[26]中,获得了H(n,k,p)的(4:2)-、(5:2)-和(a:a?1)-可染性的指数级尖锐阈值。这些结果特别有趣,因为对于a>2的经典正常a-染色,当p=c·n^(1/(-k))时,阈值常数c的下界和上界之间仍存在常数差距。
部分结果
定理1假设2≤b≤a?2且a≤n/(2 ln n)。那么每个满足|E(H)|≤(ab/3)^(-1/2)·(n ln n)^(1/2)·(a/b)^(n-1)的n-正则超图H都是(a:b)-可染色的。
应用Cherkashin–Kozik在有序链上的方法,如[5]中所述,可得如下界:当?a/b?≥2时,每个满足|E(H)|≤C_1·(n ln n)^(?a/b?-1)·?a/b?^(n-1)的n-正则超图H都是正常(a:b)-可染色的。这里C_1>0是一个绝对常数。
界(3)的产生原因是因为颜色被划分为k=?a/b?个互不相交的颜色组(1,2,…,b),(b+1,…,2b),…,((k?1)b+1,…,kb)。
定理1的证明假设H=(V,E)是一个满足|E(H)|≤c·(n ln n)^(1/2)·(a/b)^n的超图,其中常数c=c(a,b)将稍后确定。为构造H的一种正常(a:b)-分数染色,我们进行如下操作。首先,独立地为每个顶点v∈V从集合([a]^b)中随机选择一个由b种不同颜色组成的集合。其次,为每个顶点v分配一个从U(0,1)独立采样的随机权重σ(v),并按σ(v_1)< /><σ(v_|v|)重新排序顶点。最后,按新的顺序处理顶点……
利益冲突声明
作者声明他们不存在可能对本研究报告的工作产生影响的可知竞争性财务利益或个人关系。
致谢
m. akhmejanova的研究工作由wenner-gren基金会支持。
margarita akhmejanova | sean longbrake 利益冲突声明 作者声明他们不存在可能对本研究报告的工作产生影响的可知竞争性财务利益或个人关系。 致谢 m. akhmejanova的研究工作由wenner-gren基金会支持。 margarita akhmejanova | sean>σ(v_|v|)重新排序顶点。最后,按新的顺序处理顶点……
利益冲突声明
作者声明他们不存在可能对本研究报告的工作产生影响的可知竞争性财务利益或个人关系。
致谢
m. akhmejanova的研究工作由wenner-gren基金会支持。
margarita akhmejanova | sean longbrake>
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号