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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
I. Algor and N. Alon,The star-arboricity of graphs, Discrete Math.75 (1989), 11–22.
N. Alon and D. J. Kleitman,Sum-free subsets, inA Tribute to Paul Erdös (A. Baker, B. Bollobás and A. Hajnal, eds.), Cambridge Univ. Press, 1990, pp. 13–26.
N. J. Calkin,On the number of sum-free sets, to appear.
P. J. Cameron,Portrait of a typical sum-free set, inSurveys in Combinatorics 1987 (C. Whitehead, ed.), London Math. Soc. Lecture Notes123, Cambridge Univ. Press, 1987, pp. 13–42.
P. J. Cameron and P. Erdös,On the number of sets of integers with various properties, inProceedings of the 1988 Canadian Number Theory Conference at Banff (R. Mollin, ed.), to appear.
P. Erdös and L. Lovász,Problems and results on 3-chromatic hypergraphs and some related questions, inInfinite and Finite Sets (A. Hajnalet al., eds.), North-Holland, Amsterdam, 1975, pp. 609–628.
P. Erdös and J. Spencer,Probabilistic Methods in Combinatorics, Akadémiai Kiadó, Budapest, 1974, p. 18.
R. L. Graham, B. L. Rothschild and J. H. Spencer,Ramsey Theory, Wiley, New York, 1980.
G. O. H. Katona,A theorem on finite sets, inTheory of Graphs (P. Erdös and G. O. H. Katona, eds.), Akadémiai Kiadó, Budapest, 1968, pp. 187–207.
J. B. Kruskal,The number of simplices in a complex, inMathematical Optimization Techniques, Univ. of California Press, Berkeley, 1963, pp. 251–278.
W. D. Wallis, Anne Penfold Street and Jennifer Seberry Wallis,Combinatorics, Room Squares, Sum-free Sets, Hadamard Matrices, Lecture Notes in Mathematics292, Springer-Verlag, Berlin, Heidelberg and New York, 1972, Part 3, pp. 123–277.
Author information
Authors and Affiliations
Additional information
Research supported in part by the United States-Israel Binational Science Foundation and by a Bergmann Memorial Grant.
Rights and permissions
About this article
Cite this article
Alon, N. Independent sets in regular graphs and sum-free subsets of finite groups. Israel J. Math. 73, 247–256 (1991). https://doi.org/10.1007/BF02772952
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02772952