偶一致超图划分问题的若干结果

Some results on partition problems of even uniform hypergraphs

划分问题因其在多个领域的重要应用一直是图论的研究热点.利用张量的特征值研究超图的划分与奇划分,并结合边割的界给出最大奇割、平均最小割、等周数等超图拓扑指标的界.当k取2时,这些结果与对应的图谱理论中的经典结论一致,因此可视为这些结论在超图的推广.

Because of the widespread applications in many fields, partition problems play an important role in graph theory. We study partition and odd-partition problems of hypergraphs by eigenvalues of the Laplacian tensor. Joined with the bound for cardinality of edge cuts, we introduce some bounds for max-odd-cut, averaged minimal cut and isoperimetric number of hypergraphs. These bounds generalize, to the case of hypergraphs, some classical results in spectral graph theory.