INDEPENDENT SETS IN REGULAR GRAPHS AND SUM-FREE SUBSETS OF FINITE-GROUPS

被引：79

作者：

ALON, N

机构：

[1] Department of Mathematics Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv

来源：

ISRAEL JOURNAL OF MATHEMATICS | 1991年 / 73卷 / 02期

关键词：

D O I：

10.1007/BF02772952

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It is shown that there exists a function-epsilon (k) which tends to 0 as k tends to infinity, such that any k-regular graph on n vertices contains at most 2(1/2 + epsilon (k))n independent sets. This settles a conjecture of A. Granville and has several applications in Combinatorial Group Theory.

引用

页码：247 / 256

页数：10