Independent sets in regular graphs and sum-free subsets of finite groups |
| |
Authors: | Noga Alon |
| |
Institution: | (1) Department of Mathematics Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel |
| |
Abstract: | It is shown that there exists a function∈(k) which tends to 0 ask tends to infinity, such that anyk-regular graph onn 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.
Research supported in part by the United States-Israel Binational Science Foundation and by a Bergmann Memorial Grant. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|