Independence numbers of graphs and generators of ideals

Shuo Yen Robert Li; Wen Ch ing Winnie Li

doi:10.1007/BF02579177

Independence numbers of graphs and generators of ideals

Shuo Yen Robert Li, Wen Ch ing Winnie Li

Mathematics

Research output: Contribution to journal › Article › peer-review

32 Scopus citations

Abstract

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 of t-designs. The main theorem suggests a new approach to the Clique Problem which is NP-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.

Original language	English (US)
Pages (from-to)	55-61
Number of pages	7
Journal	Combinatorica
Volume	1
Issue number	1
DOIs	https://doi.org/10.1007/BF02579177
State	Published - Mar 1981

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/BF02579177

Cite this

@article{75e738f8001340daa7205bba7e53484d,

title = "Independence numbers of graphs and generators of ideals",

abstract = "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 of t-designs. The main theorem suggests a new approach to the Clique Problem which is NP-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{\'a}n's theorem on the maximum graphs with a prescribed clique number.",

author = "Li, {Shuo Yen Robert} and Li, {Wen Ch ing Winnie}",

year = "1981",

month = mar,

doi = "10.1007/BF02579177",

language = "English (US)",

volume = "1",

pages = "55--61",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "1",

}

TY - JOUR

T1 - Independence numbers of graphs and generators of ideals

AU - Li, Shuo Yen Robert

AU - Li, Wen Ch ing Winnie

PY - 1981/3

Y1 - 1981/3

N2 - 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 of t-designs. The main theorem suggests a new approach to the Clique Problem which is NP-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.

AB - 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 of t-designs. The main theorem suggests a new approach to the Clique Problem which is NP-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.

UR - http://www.scopus.com/inward/record.url?scp=51249180619&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51249180619&partnerID=8YFLogxK

U2 - 10.1007/BF02579177

DO - 10.1007/BF02579177

M3 - Article

AN - SCOPUS:51249180619

SN - 0209-9683

VL - 1

SP - 55

EP - 61

JO - Combinatorica

JF - Combinatorica

IS - 1

ER -

Independence numbers of graphs and generators of ideals

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this