Independence numbers of graphs and generators of ideals
Independence numbers of graphs and generators of ideals
复制标题
图的独立数和理想生成元
作者：
S. Li;W. Li
本文研究了与具有有界独立数的图相关的某些齐次理想的生成元。这些理想最早出现在设计理论中。主要定理为解决团问题提供了一种新的途径。这个定理在交换代数中有一个更一般的形式，处理与线性簇的并集有关的理想。这个一般定理在文章中陈述;它的一个推论推广了图兰关于具有指定团数的最大图的定理。
This article investigates the generators of certain homogeneous ideals which are associated with graphs with bounded independence numbers. These ideals first appeared in the theory oft-designs. The main theorem suggests a new approach to the Clique Problem which isNP-complete. This theorem has a more general form in commutative algebra dealing with ideals associated with unions of linear varieties. This general theorem is stated in the article; a corollary to it generalizes Turán’s theorem on the maximum graphs with a prescribed clique number.