Fractional clique decompositions of dense graphs and hypergraphs
Fractional clique decompositions of dense graphs and hypergraphs
复制标题
稠密图和超图的分数派分解
DOI：
10.1016/j.jctb.2017.05.005
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Barber B
中科院分区：
文献类型：
--
作者：
Barber B
我们的主要结果是：任意n≥ 104 r3阶且最小度δ（G）≥（1 - 1/104 r3/2）n的图G都有分数Kr-分解.结合这一结果与最近的工作巴伯，库恩，洛和Osthus导致最知名的最小度阈值精确（非分数）F-分解的广泛的一类图F（包括大集团）。对于一般的k-一致超图，我们给出了一个简短的证明：存在一个常数ck> 0，使得任意n阶k-一致超图G的最小余度至少为（1− ck/r2 k− 1）n，都有一个分数Kr（k）-分解，其中Kr（k）是r阶完全k-一致超图.（三角形的相关分数分解结果由Dross获得，超图团的相关分数分解结果由Dukes和Yuster获得。所有上述新结果涉及纯组合参数。特别是，这产生了威尔逊定理的组合证明，即每个大的F-可分完全图都有一个F-分解。
Our main result is that every graph G on n≥ 10 4 r 3 vertices with minimum degree δ (G)≥(1− 1/10 4 r 3/2) n has a fractional K r-decomposition. Combining this result with recent work of Barber, Kühn, Lo and Osthus leads to the best known minimum degree thresholds for exact (non-fractional) F-decompositions for a wide class of graphs F (including large cliques). For general k-uniform hypergraphs, we give a short argument which shows that there exists a constant c k> 0 such that every k-uniform hypergraph G on n vertices with minimum codegree at least (1− c k/r 2 k− 1) n has a fractional K r (k)-decomposition, where K r (k) is the complete k-uniform hypergraph on r vertices.(Related fractional decomposition results for triangles have been obtained by Dross and for hypergraph cliques by Dukes as well as Yuster.) All the above new results involve purely combinatorial arguments. In particular, this yields a combinatorial proof of Wilson's theorem that every large F-divisible complete graph has an F-decomposition.
登录
查看更多内容
“稠密超图的有理分解和一些相关特征值估计”的勘误 [线性代数应用 436 (9) (2012) 3736–3746]
DOI：
--
发表时间：
2015
期刊：
影响因子：
--
作者：
P. Dukes
通讯作者：
P. Dukes
DOI：
10.1017/s0963548317000165
发表时间：
2016
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
R. Montgomery
通讯作者：
R. Montgomery
DOI：
10.1016/j.jcta.2017.04.005
发表时间：
2017
期刊：
Journal of Combinatorial Theory, Series A
影响因子：
--
作者：
Barber B
通讯作者：
Barber B
DOI：
10.1016/j.jctb.2019.02.010
发表时间：
2019
期刊：
Journal of Combinatorial Theory, Series B
影响因子：
--
作者：
Glock S
通讯作者：
Glock S
具有大最小度的图中的分数三角形分解
DOI：
10.1137/15m1014310
发表时间：
2015
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
François Dross
通讯作者：
François Dross