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

Research output: Contribution to journalArticle

76 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 languageEnglish (US)
Pages (from-to)247-256
Number of pages10
JournalIsrael Journal of Mathematics
Volume73
Issue number2
DOIs
StatePublished - Jun 1 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Independent sets in regular graphs and sum-free subsets of finite groups'. Together they form a unique fingerprint.

  • Cite this