Independent sets in regular graphs and sum-free subsets of finite groups

Noga Alon

doi:10.1007/BF02772952

Independent sets in regular graphs and sum-free subsets of finite groups

Noga Alon

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

87 Scopus citations

Abstract

It is shown that there exists a function ∈(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+∈(k))n} independent sets. This settles a conjecture of A. Granville and has several applications in Combinatorial Group Theory.

Original language	English (US)
Pages (from-to)	247-256
Number of pages	10
Journal	Israel Journal of Mathematics
Volume	73
Issue number	2
DOIs	https://doi.org/10.1007/BF02772952
State	Published - Jun 1991
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Access to Document

10.1007/BF02772952

Cite this

@article{0a21cf2de8a04ef3bfd4a78dc94eeca5,

title = "Independent sets in regular graphs and sum-free subsets of finite groups",

abstract = "It is shown that there exists a function ∈(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+∈(k))n independent sets. This settles a conjecture of A. Granville and has several applications in Combinatorial Group Theory.",

author = "Noga Alon",

year = "1991",

month = jun,

doi = "10.1007/BF02772952",

language = "English (US)",

volume = "73",

pages = "247--256",

journal = "Israel Journal of Mathematics",

issn = "0021-2172",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Independent sets in regular graphs and sum-free subsets of finite groups

AU - Alon, Noga

PY - 1991/6

Y1 - 1991/6

N2 - It is shown that there exists a function ∈(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+∈(k))n independent sets. This settles a conjecture of A. Granville and has several applications in Combinatorial Group Theory.

AB - It is shown that there exists a function ∈(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+∈(k))n independent sets. This settles a conjecture of A. Granville and has several applications in Combinatorial Group Theory.

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

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

U2 - 10.1007/BF02772952

DO - 10.1007/BF02772952

M3 - Article

AN - SCOPUS:51249178473

SN - 0021-2172

VL - 73

SP - 247

EP - 256

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

IS - 2

ER -

Independent sets in regular graphs and sum-free subsets of finite groups

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this