Counting independent sets in graphs
Abstract.
In this short survey article, we present an elementary, yet quite powerful, method of enumerating independent sets in graphs. This method was first employed more than three decades ago by Kleitman and Winston and has subsequently been used numerous times by many researchers in various contexts. Our presentation of the method is illustrated with several applications of it to ‘real-life’ combinatorial problems. In particular, we derive bounds on the number of independent sets in regular graphs, sum-free subsets of , and -free graphs and give a short proof of an analogue of Roth’s theorem on -term arithmetic progressions in sparse random sets of integers which was originally formulated and proved by Kohayakawa, Łuczak, and Rödl.
1. Introduction
Many well-studied problems in combinatorics concern characterising discrete structures that satisfy certain ‘local’ constraints. For example, the celebrated theorem of Szemerédi [42] gives an upper bound on the maximum size of a subset of the first integers which does not contain an arithmetic progression of a fixed length . To give another example, the archetypal problem studied in extremal graph theory, dating back to the work of Mantel [32] and Turán [43], is that of characterising graphs which do not contain a fixed graph as a subgraph.
Problems of this type fall into the following general framework. We are given a finite set and a collection of subsets of . What can be said about sets that do not contain any member of ? Such a collection is often called a hypergraph with vertex set , members of are termed edges, and any set that contains no edge is called an independent set. In view of this, one might say that a large part of combinatorics is concerned with studying independent sets in various hypergraphs. For instance, in the first example from the previous paragraph, is the set and is the collection of all -term arithmetic progressions contained in ; stated in this language, Szemerédi’s theorem says that for every positive constant , every independent set in has fewer than elements, provided that is sufficiently large. In the second example, is the edge set of a complete graph on a given set of vertices and is the family of all sets of edges that form a copy of in the complete graph; in this notation, if is a clique with vertices, then Turán’s theorem says that the largest independent sets in are precisely the edge sets of the complete balanced -partite subgraphs of the complete graph with edge set and the well-known theorem of Kolaitis, Prömel, and Rothschild [29] states that almost all independent sets of are -partite, that is, the number of independent sets in that are not the edge sets of -partite subgraphs of the complete graph with edge set satisfies as .
For a hypergraph , let denote the family of all independent sets in , let , and let be the largest cardinality of an element of , usually called the independence number of . There are two natural problems that one usually poses about a specific hypergraph :
-
(i)
Determine and describe all with elements.
-
(ii)
Estimate and describe a ‘typical’ member of .
Let us remark here that providing a precise characterisation of a typical element of usually yields a precise estimate for .
An apparent connection between problems (i) and (ii) may be easily observed in the following two inequalities, which are trivial consequences of the above definitions and the fact that the family is closed under taking subsets:
(1) |
Note that, unless is very close to , the lower and upper bounds on given in (1) are quite far apart. Since for many interesting hypergraphs this naive lower bound is actually fairly close to being best possible, the efforts of many researchers have been focused on improving the upper bound.
In this short survey article, we present an elementary, yet very powerful, method for proving stronger upper bounds in the case when all edges of have size two, that is, when is a graph. This method was first described more than three decades ago by Kleitman and Winston, who used it to obtain upper bounds on the number of lattices111A lattice is a partially ordered set in which every two elements have a supremum and an infimum. [25] and graphs without cycles of length four [26]. Variations of this method were subsequently rediscovered by several researchers, most notably by Sapozhenko, in the context of enumerating independent sets in regular graphs [1, 36] and sum-free sets in abelian groups [1, 31, 37]. We shall illustrate our presentation of this method with several applications of it to ‘real-life’ combinatorial problems. We would like to stress here that none of the results or proof techniques presented here are new, but we hope that there is some value in seeing them next to one another.
2. The Kleitman–Winston algorithm
Suppose that we are given an arbitrary graph with vertices. Our goal is to give an upper bound on , the number of independent sets in . The idea of Kleitman and Winston was to devise an algorithm that, given a particular independent set , would encode in an invertible way. Crucially, the encoding should be performed in a way which makes it easy to estimate the total number of outputs of the algorithm. Since for every invertible encoding, the total number of outputs is precisely , in this way one could derive an upper bound on this quantity.
The crucial idea of Kleitman and Winston was to consider the vertices of ordered according to their degrees and encode each independent set as a sequence of positions of the elements of in that ordering. We make this precise below.
Definition.
Let be a graph and fix an arbitrary total order on . For every , the max-degree ordering of is the ordering of all elements of , where for each , is the maximum-degree vertex in the subgraph of induced by ; ties are broken by giving preference to vertices that come earlier in the fixed total order on .
The Algorithm.
Suppose that a graph , an , and an integer are given. Set and . For , do the following:
-
(a)
Let be the max-degree ordering of .
-
(b)
Let be the minimal index such that .
-
(c)
Move from to .
-
(d)
Delete from .
-
(e)
Delete from .
Output and .
For each output sequence and every , denote by and the sets and at the end of the th iteration of the algorithm (run on some input that produces this particular sequence ), respectively. Observe that these definitions do not depend on the choice of as the sequence uniquely determines how the sets and evolve throughout the algorithm. More precisely, if running the algorithm on two inputs produces the same sequence , then both these executions will also yield the same sets and . Indeed, all the modifications of the sets and in the th iteration of the algorithm depend solely on .
Note crucially that and for every . Indeed, by the minimality of and the assumption that is independent, the only vertices of that are deleted from are moved to . It follows that one may recover the set from the output of the algorithm, as . We also note for future reference that the sequence can be recovered from the set . Indeed, if running the algorithm on some input produces a sequence and , then the same sequence will be produced by running the algorithm with replaced by . Finally, let us observe that , as in steps (c) and (d) of the th iteration of the main loop, we removed from some vertices.
Let be the number of independent sets in that have precisely elements. The above observations readily imply that for every and with ,
(2) |
where the above sums range over all output sequences . In particular, letting ,
(3) |
In view of (2) and (3), it is in our interest to make the set as small as possible, uniformly for all values of . This is why we consider the vertices of listed according to the max-degree ordering. (An attentive reader might have already noticed that this particular ordering maximises in each iteration of the algorithm.) Suppose that we are at the th iteration of the main loop of the algorithm and let , where is as at the start of this iteration, that is, . By the definition of the max-degree ordering,
In particular, if , then the right-hand side of the above inequality is . Consequently, the number of vertices that are removed from during the th iteration of the main loop of the algorithm is at least , which is at least , as and . In other words, as long as the density of the subgraph induced by the set exceeds some , each iteration of the main loop of the algorithm shrinks by a factor of at most .
The following two lemmas, which are both implicit in the work of Kleitman and Winston, summarise the above discussion. The first lemma gives a simple bound on the number of independent sets of a given size in a graph which satisfies a certain local density condition. The exact statement of this lemma is taken from [27]. The second lemma characterises the family of all independent sets in such a locally dense graph. The statement of this lemma is inspired by the statement of the main result of [7].
Lemma 1.
Let be a graph on vertices and assume that an integer and reals and satisfy
(4) |
Suppose that the number of edges induced in by every set with satisfies
(5) |
Then, for every integer with ,
(6) |
Proof.
Since there are exactly sequences satisfying and for each , the sum in the right-hand side of (2) has at most terms. Therefore, it suffices to show that for each sequence that is outputted by the algorithm, the set has at most elements. If this were not the case, then there would be some sequence such that for each , the set in the th iteration of the main loop of the algorithm (run on some input that results in this particular sequence) would have more than elements and therefore induce in a subgraph with edge density at least . It follows from our discussion that each of the iterations would shrink the set by a factor of at most . Since at the start of the algorithm, then, by (4),
a contradiction. ∎
Lemma 2.
Let be a graph on vertices and assume that an integer and reals and satisfy
(7) |
Suppose that the number of edges induced in by every set with satisfies
(8) |
Then there exists a collection of -element subsets of and two mappings and such that for each and for every with at least elements.
Proof.
We define the mappings and and the family as follows. We simply run the algorithm with input for each with at least elements and let and be the final sets and , respectively. Moreover, we let be the family of all such , that is, the set of values taken by . The discussion in the paragraph following the description of the algorithm should convince us that this is a valid definition of , that for each as above, and that consists solely of -element subsets of . It suffices to check that for each such . If this were not the case, then there would be some sequence such that for each , the set in the th iteration of the main loop of the algorithm (run on an input that generates this sequence) would have more than elements and therefore induce in a subgraph with average degree at least . But then, each of the iterations would remove from at least vertices. Since at the start of the algorithm, then by (7),
a contradiction. ∎
Before we close this section, let us make several final remarks. First, the conclusion of Lemma 2 is stronger than the conclusion of Lemma 1. This is simply because the existence of and as in the statement of the second lemma imply the bound on asserted by the first lemma. Moreover, it should be clear from the proofs that the assumptions of the two lemmas are ‘interchangeable’ in the following sense. If a graph satisfies the assumptions of Lemma 1 with some , , and , then the conclusion of Lemma 2 holds for with the same and ; and vice-versa, if a graph satisfies the assumptions of Lemma 2 with some , , and , then the conclusion of Lemma 1 holds for with the same and . (The latter statement is redundant because, as we have already noted above, the conclusion of Lemma 2 is stronger than the conclusion of Lemma 1.)
3. Applications
3.1. Independent sets in regular graphs
During a number theory conference at Banff in 1988, Granville conjectured (see [1]) that an -vertex -regular graph can have no more than independent sets, where is some function that tends to as . A few years later, this was shown to be true by Alon [1], who proved that in fact
for every -vertex -regular graph . As our first application of Lemma 1, we derive a somewhat stronger estimate, which was obtained several years later by Sapozhenko [36], using arguments very similar to those presented in Section 2.
Theorem 3 ([36]).
There is an absolute constant such that every -vertex -regular graph satisfies
Alon [1] speculated that when is divisible by , then the disjoint union of complete bipartite graphs has the maximum number of independent sets among all -regular graphs with vertices. A slightly stronger statement (Theorem 4 below) was later conjectured by Kahn [23], who proved it under the additional assumption that is bipartite, using a beautiful entropy argument. This assumption was recently shown to be unnecessary by Zhao [45], who gave a short and elegant argument showing that for every -vertex -regular graph , there exists a -vertex -regular bipartite graph such that . The results of Kahn and Zhao yield the following.
Theorem 4 ([23, 45]).
For every -vertex -regular graph ,
Proof of Theorem 3.
Let be an -vertex -regular graph. We shall in fact estimate for each and deduce the claimed bound on by summing over all . Since and is an arbitrary constant, we may assume that is sufficiently large (and therefore is sufficiently large). We consider two cases. First, if , then we simply note that
(9) |
where we used the well-known inequality valid for all and .
In the complementary case, , we shall apply Lemma 1. To this end, let and note that
(10) |
Fix an arbitrary , let , and observe that if , then (10) yields
(11) |
Assume that and let . By Lemma 1, since
then for every with ,
(12) |
Summing (9) and (12) over all yields
We obtain the claimed bound by letting ; we note that as we assumed that is large. ∎
We ought to indicate here that one may significantly improve the upper bound given by Theorem 3 by a somewhat more careful analysis of the execution of the Kleitman–Winston algorithm than the one given in the proof of Lemma 1. The main reason why one should expect such an improvement to be possible is the crudeness of the second inequality in (11) in the case when is much larger than . The proof of Lemma 1 uses (11) to show that in each step of the algorithm, the set loses at least elements whereas in reality will lose many more elements as long as is not very close to . By considering the ‘evolution’ of partitioned into ‘dyadic’ intervals , where , one may prove that there is an absolute constant such that every -vertex -regular graph satisfies
One rigorous way of tracking this ‘evolution’ of is to repeatedly invoke Lemma 2 with and for . We leave filling in the details as an exercise for the reader.
3.2. Sum-free sets
The conjecture of Granville mentioned in the previous section was motivated by a problem posed by Cameron and Erdős at the same number theory conference. A set of elements of an abelian group is called sum-free if there are no satisfying . Let denote the set . Cameron and Erdős raised the question of determining the number of sum-free sets contained in the set . They noted that any set containing either only odd integers or only integers greater than is sum-free, and that it is unlikely that there is another large collection of sum-free sets that are not essentially of one of the above two types. In view of this, they conjectured that . Soon afterwards, Alon [1] showed that the aforementioned conjecture of Granville implies the following weaker estimate on , which will serve as a second example application of Lemma 1.
Theorem 5 ([1]).
The set has at most sum-free subsets.
The Cameron–Erdős conjecture was solved some fifteen years later by Green [18] and, independently, by Sapozhenko [38]. The solution due to Sapozhenko uses a method akin to the Kleitman–Winston algorithm presented in Section 2, while the one due to Green uses discrete Fourier analysis.222However, one might still argue that the general ‘philosophy’ behind Green’s proof is similar. We do not discuss either of their arguments here, but instead refer the interested reader to the original papers. Finally, we mention that strong estimates on the number of sum-free subsets of with a given number of elements, which imply the conjecture, were recently obtained in [3]; the proof there employs the ideas presented in Section 2.
Proof of Theorem 5.
Observe first that the number of all subsets of which contain fewer than elements from is at most . Therefore, we may restrict our attention to sum-free sets that contain at least elements strictly smaller than . For each such set , let be the set of smallest elements of .
Given a set , define an auxiliary graph with vertex set by letting
and note that is -regular, as and hence and contain different residues modulo . The crucial observation is that for every sum-free as above, the set is an independent set in the graph . Indeed, otherwise there would be and an with ; since , this is only possible when . In particular, for a given , there are at most sum-free sets satisfying . By Theorem 3, we conclude that
Before closing this section, we remark that the paper of Alon [1] started a very successful line of inquiry into the closely related problem of determining the number of sum-free sets contained in an arbitrary finite abelian group; see, e.g., [2, 19, 20, 31, 37]. In many of these works, variations of the ideas presented in Section 2 play a prominent role.
3.3. Independent sets in regular graphs without small eigenvalues
Since every -vertex bipartite graph satisfies and hence it contains at least independent sets, the upper bounds for proved in Section 3.1 are essentially best possible whenever is bipartite. It is natural to ask whether these bounds can be improved when one assumes that is ‘far’ from being bipartite. An affirmative answer to this question was given by Alon and Rödl [5].
Recall that the adjacency matrix of an -vertex graph is a real-valued symmetric matrix and therefore it has real eigenvalues. Denote these eigenvalues by , where . It is well known that the quantity , called the second eigenvalue of , is closely tied with, among other parameters, the expansion properties of . We shall be interested only in the smallest eigenvalue of , which we denote by . It was first proved by Hoffman [21] that every -regular -vertex graph satisfies . This was later significantly strengthened333In particular, Lemma 6 implies that for every with more than vertices. by Alon and Chung [4], who established the following relation between and the number of edges induced by large sets of vertices in , cf. the expander mixing lemma (see, e.g., [22]).
Lemma 6 ([4]).
Let be an -vertex -regular graph. For all ,
Alon and Rödl [5] were the first to prove that if is much larger than , then each such has far fewer than independent sets. As our next application of Lemma 1, we derive a similar estimate, originally proved in [2].
Theorem 7 ([2]).
For every , there exists a constant such that the following holds. If is an -vertex -regular graph with , then
provided that .
Proof of Theorem 7.
Fix some , let be an -vertex -regular graph, and let . We may assume that as otherwise there is nothing to prove. Let be an arbitrary set with . Lemma 6 implies that
Let , , and and observe that . If follows from Lemma 1 that for every with ,
(13) |
Let denote the right-hand side of (13) with replaced by . We may clearly assume that , as otherwise . An elementary calculation shows that
and hence
where we used the inequalities and valid whenever . Finally, if is sufficiently large (as a function of ) and , then for every with ,
which completes the proof of the theorem. ∎
We close this section with several remarks. First, the constant in the assertion of the theorem is optimal as for many values of , , and , there are -vertex -regular graphs with . Second, the assumption that cannot be relaxed as for every , every -vertex -regular graph satisfies whenever . (To see this, consider the greedy process of constructing an independent set which repeatedly picks an arbitrary vertex of and removes it and all of its neighbours from .) Third, the above theorem implies the conjecture of Granville stated in Section 3.1 as for every -regular graph . Finally, we refer the interested reader to [2] and [5], where Theorem 7 was used to obtain upper bounds on the number of sum-free sets in abelian groups of even order and lower bounds on some multicolor Ramsey numbers, respectively.
3.4. The number of -free graphs
As our next example, we present the main result from one of the papers of Kleitman and Winston [26] which introduced the methods described in Section 2. Call a graph -free if it does not contain a cycle of length four and let denote the maximum number of edges in a -free graph with vertices. A classical result of Kővári, Sós, and Turán [30] together with a construction due to Brown [10] and Erdős, Rényi, and Sós [16] imply that
Let be the number of (labeled) -free graphs on the vertex set . Since each subgraph of a -free graph is itself -free, we have
which yields
(14) |
Answering a question of Erdős, Kleitman and Winston [26] showed that the lower bound in (14) is tight up to a constant factor.
Theorem 8 ([26]).
There is a positive constant such that
Before we continue with the proof of the theorem, let us make a few comments. In fact, Erdős asked whether for an arbitrary that contains a cycle. This was shown to be the case by Erdős, Frankl, and Rödl [15] under the assumption that . Very recently, Morris and Saxton [33] proved that for infinitely many . But the notoriously difficult problem of determining whether or not for every bipartite that is not a forest remains unsolved, apart from the following two special cases: is a cycle length four [26], six [24], or ten [33] or is an unbalanced complete bipartite graph [8, 9]. More exactly, it is proved in [9] and [33] that whenever and that for every , respectively. As it is commonly believed that whenever and that , both these results are most likely best possible. Finally, we mention that the proofs of most of the results mentioned in this paragraph use either a variant of Lemma 1 or extensions of the ideas presented in Section 2 to hypergraphs, see Section 4.2.
Proof of Theorem 8.
Note that one can order the vertices of every -vertex graph as in such a way that for every , letting ,
Indeed, one may obtain such an ordering by iteratively letting be a minimum-degree vertex of for . In particular, every labeled -vertex graph can be constructed in the following way. First, choose an ordering of the vertices and let be the empty graph with vertex set . Second, for each , build a graph by adding to the graph a vertex labeled in such a way that its degree (in ) satisfies . Finally, we let . Observe that is -free if and only if is -free for each .
Now, given integers and with , let denote the maximum number of ways to attach a vertex of degree to an -vertex -free graph with minimum degree at least in such a way that the resulting graph remains -free. This number is well defined as clearly . Moreover, let . The argument given in the previous paragraph proves that
(15) |
Indeed, there are ways to order as and for each such ordering, there are at most choices for the sequence of degrees. In view of (15), the following claim easily implies the assertion of the theorem.
Claim.
There exists a constant such that for all .
Without loss of generality, we may assume that is large. Thus, if , then
Therefore, we shall from now on assume that . Let be a -free graph on vertices with . Let be the square of , that is, the graph with and
Crucially, observe that adding to will result in a -free graph if and only if the neighbourhood of is an independent set in . Hence, is an upper bound on the number of -free extensions of by a vertex of degree . We shall estimate using Lemma 1.
To this end, we show that subgraphs of induced by large subsets of have reasonably high density. Since is -free, every edge of corresponds to a unique vertex such that and are edges of . Therefore, for each ,
where the last inequality is Jensen’s inequality applied to the convex function . Since
then assuming that implies
Finally, let , , and . Since and is large, then and therefore . If follows from Lemma 1 that
where we used the assumption that is large and the fact that . ∎
3.5. Roth’s theorem in random sets
As our final example, we present a short proof of a well-known result of Kohayakawa, Łuczak, and Rödl [28]. Recall that denotes the set . A famous theorem of Roth [34] asserts that for every positive , any set of at least integers from contains a -term arithmetic progression (-term AP), provided that is sufficiently large (as a function of only). Given a positive , we shall say that a set is -Roth if each satisfying contains a -term AP. We may now restate Roth’s theorem as follows. For every positive , there exists an such that the set is -Roth whenever . With the aim of showing that there exist ‘smaller’ and ‘sparser’ -Roth sets Kohayakawa, Łuczak, and Rödl [28] proved the following result.
Theorem 9 ([28]).
For every positive , there exists a constant such that if , then the probability that a uniformly chosen random -element subset of is -Roth tends to as .
We shall deduce Theorem 9 as an easy corollary of the following upper bound for the number of subsets of of a given cardinality that do not contain a -term AP, originally proved in [7] and [39] in a much more general form. This upper bound will be derived from Roth’s theorem using Lemma 2 with one additional twist which was previously considered in [2].
Theorem 10.
For every positive , there exists a constant such that if ,
Proof of Theorem 9.
Our proof of Theorem 10 will use the following simple consequence of Roth’s theorem, observed first by Varnavides [44], as a ‘black box’.
Proposition 11 ([34, 44]).
For every positive , there exist an integer and a positive such that if , then every set of at least integers from contains at least -term APs.
Proof of Theorem 10.
Fix a positive , let and be the constants from the statement of Proposition 11 invoked with , and suppose that . Given an arbitrary set and integers and , let
Our aim is to show that , provided that for some constant which depends only on . This inequality will follow from the trivial observation that for all and and the following claim.
Claim.
If and , then .
Let be the -uniform hypergraph with vertex set whose edges are all triples of numbers which form a -term AP. Let be an arbitrary -element subset of . By Proposition 11, . Let be the set of all vertices of , the subhypergraph of induced by , whose degree is at least . In other words, is the set of all numbers in that belong to at least three-term APs contained in . Since the maximum degree of is at most , we have .
We first estimate the number of -element subsets of with no -term AP that contain fewer than elements of . Since each such set may be partitioned into and , where and , there are at most such sets. We may therefore focus on counting subsets of that contain at least elements of . We shall obtain a suitable upper bound for their number using Lemma 2.
Let be an arbitrary subset of and consider the auxiliary graph with vertex set whose edges are all pairs such that for some . Since for a given pair , there are at most three different such that , it follows that and the maximum degree of is no more than . It follows that for an arbitrary subset of with at least elements,
(16) |
Observe crucially that if some set contains no -term APs, then is an independent set in the graph .
Let and fix some with . We shall prove an upper bound on the number of ways one can extend to an -element subset of that contains no -term APs. By our above discussion, if is such a set, then is an independent set of with elements. Let be the family of sets and let and be the maps whose existence is postulated by Lemma 2 with , , , and . Note that the assumptions of the lemma are satisfied by our discussion above, see (16). Since clearly for each extension of to an -element subset of with no -term APs, contains no -term APs, the number of extensions of satisfies
We conclude that
which, since was an arbitrary -element subset of , proves the claim.
Let and suppose that . We recursively invoke the claim times to obtain
(17) |
As in the proof of Theorem 7, denote by the right-hand side of (17) with replaced by . We may clearly assume that as otherwise by Roth’s theorem (we may assume that is sufficiently large). An elementary calculation shows that
and hence, letting ,
Finally, if is sufficiently large as a function of and , then for every with , we have
which completes the proof of the theorem. ∎
4. Concluding remarks and further reading
4.1. Other applications of the Kleitman–Winston method
There have been quite a few successful applications of the Kleitman–Winston method other than the ones presented in Section 3. In particular, variants of Lemma 1 were used in the following works: Kleitman and Wilson [24] proved that the number of -vertex graphs with girth larger than is ; Dellamonica, Kohayakawa, Lee, Rödl, and the author [13, 14, 27] proved sharp bounds on the number of subsets of with a given cardinality which contain no non-trivial solutions to the equation for every ; Balogh, Das, Delcourt, Liu, and Sharifzadeh [6] and Gauy, Hàn, and Oliveira [17] proved sharp bounds for the number of intersecting families of -element subsets of with a given cardinality and for the typical size of the largest intersecting subfamily contained in a random collection of -element subsets of .
4.2. Extensions of the Kleitman–Winston method to hypergraphs
It seems natural to seek a generalisation of the Kleitman–Winston method that would yield non-trivial upper bounds for the number of independent sets in a hypergraphs of higher uniformity. Perhaps somewhat surprisingly, such generalisations were considered only fairly recently. To the best of our knowledge this was first done in [8, 9], where sharp upper bounds for the number of -vertex graphs which do not contain a copy of a fixed complete bipartite subgraph were proved using a generalisation of the argument presented in Section 3.4. Around the same time, similar ideas were developed by Saxton and Thomason, who used them to establish lower bounds for the list chromatic number of regular uniform hypergraphs [40]. Inspired by the groundbreaking work of Conlon and Gowers [12] and Schacht [41], these efforts culminated in far-reaching generalisations of the Kleitman–Winston method to arbitrary uniform hypergraphs, obtained independently by Saxton and Thomason [39], and by Balogh, Morris, and the author [7]. For further details, we refer the interested reader to [7, 11, 12, 35, 39, 41].
Acknowledgments. I would like to thank Noga Alon, Józsi Balogh, Domingos Dellamonica, Yoshi Kohayakawa, Sang June Lee, Rob Morris, and Vojta Rödl for many interesting discussions on the topics of independent sets in graphs and the Kleitman–Winston method and its applications over the past several years. These discussions have greatly influenced the content of this paper. I would also like to thank David Conlon, Asaf Ferber, and Rob Morris for their careful reading of an earlier version of this manuscript and many valuable comments which helped me improve the exposition and saved me from making several embarrassing mistakes. Finally, special thanks to Jarik Nešetřil for his encouragement to write this survey.
References
- [1] N. Alon, Independent sets in regular graphs and sum-free subsets of finite groups, Israel J. Math. 73 (1991), 247–256.
- [2] N. Alon, J. Balogh, R. Morris, and W. Samotij, Counting sum-free sets in abelian groups, Israel J. Math. 199 (2014), 309–344.
- [3] by same author, A refinement of the Cameron-Erdős conjecture, Proc. Lond. Math. Soc. (3) 108 (2014), 44–72.
- [4] N. Alon and F. R. K. Chung, Explicit construction of linear sized tolerant networks, Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), vol. 72, 1988, pp. 15–19.
- [5] N. Alon and V. Rödl, Sharp bounds for some multicolor Ramsey numbers, Combinatorica 25 (2005), 125–141.
- [6] J. Balogh, S. Das, M. Delcourt, H. Liu, and M. Sharifzadeh, The typical structure of intersecting families of discrete structures, arXiv:1408.2559 [math.CO].
- [7] J. Balogh, R. Morris, and W. Samotij, Independent sets in hypergraphs, to appear in J. Amer. Math. Soc.
- [8] J. Balogh and W. Samotij, The number of -free graphs, Combinatorica 31 (2011), 131–150.
- [9] by same author, The number of -free graphs, J. Lond. Math. Soc. (2) 83 (2011), 368–388.
- [10] W. G. Brown, On graphs that do not contain a Thomsen graph, Canad. Math. Bull. 9 (1966), 281–285.
- [11] D. Conlon, Combinatorial theorems relative to a random set, arXiv:1404.3324 [math.CO].
- [12] D. Conlon and W. T. Gowers, Combinatorial theorems in sparse random sets, arXiv:1011.4310 [math.CO].
- [13] D. Dellamonica Jr., Y. Kohayakawa, S. Lee, V. Rödl, and W. Samotij, The number of -sets of a given cardinality, submitted.
- [14] by same author, On the number of -sets, to appear in Combin. Probab. Comput.
- [15] P. Erdős, P. Frankl, and V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin. 2 (1986), 113–121.
- [16] P. Erdős, A. Rényi, and V. T. Sós, On a problem of graph theory, Studia Sci. Math. Hungar. 1 (1966), 215–235.
- [17] M. M. Gauy, H. Hàn, and I. C. Oliveira, Erdős–Ko–Rado for random hypergraphs: asymptotics and stability, arXiv:1409.3634 [math.CO].
- [18] B. Green, The Cameron-Erdős conjecture, Bull. London Math. Soc. 36 (2004), 769–778.
- [19] B. Green and I. Z. Ruzsa, Counting sumsets and sum-free sets modulo a prime, Studia Sci. Math. Hungar. 41 (2004), 285–293.
- [20] by same author, Sum-free sets in abelian groups, Israel J. Math. 147 (2005), 157–188.
- [21] A. J. Hoffman, On eigenvalues and colorings of graphs, Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., 1969), Academic Press, New York, 1970, pp. 79–91.
- [22] S. Hoory, N. Linial, and A. Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), 439–561 (electronic).
- [23] J. Kahn, An entropy approach to the hard-core model on bipartite graphs, Combin. Probab. Comput. 10 (2001), 219–237.
- [24] D. J. Kleitman and D. B. Wilson, On the number of graphs which lack small cycles, manuscript, 1996.
- [25] D. J. Kleitman and K. J. Winston, The asymptotic number of lattices, Ann. Discrete Math. 6 (1980), 243–249, Combinatorial mathematics, optimal designs and their applications (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978).
- [26] by same author, On the number of graphs without -cycles, Discrete Math. 41 (1982), 167–172.
- [27] Y. Kohayakawa, S. Lee, V. Rödl, and W. Samotij, The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers, to appear in Random Structures Algorithms.
- [28] Y. Kohayakawa, T. Łuczak, and V. Rödl, Arithmetic progressions of length three in subsets of a random set, Acta Arith. 75 (1996), 133–163.
- [29] Ph. G. Kolaitis, H. J. Prömel, and B. L. Rothschild, -free graphs: asymptotic structure and a - law, Trans. Amer. Math. Soc. 303 (1987), 637–671.
- [30] T. Kővari, V. T. Sós, and P. Turán, On a problem of K. Zarankiewicz, Colloquium Math. 3 (1954), 50–57.
- [31] V. F. Lev, T. Łuczak, and T. Schoen, Sum-free sets in abelian groups, Israel J. Math. 125 (2001), 347–367.
- [32] W. Mantel, Problem 28, Wiskundige Opgaven 10 (1907), 60–61.
- [33] R. Morris and D. Saxton, The number of -free graphs, arXiv:1309.2927 [math.CO].
- [34] K. F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104–109.
- [35] W. Samotij, Stability results for random discrete structures, Random Structures Algorithms 44 (2014), 269–289.
- [36] A. A. Sapozhenko, On the number of independent sets in extenders, Diskret. Mat. 13 (2001), 56–62.
- [37] by same author, Asymptotics of the number of sum-free sets in abelian groups of even order, Dokl. Akad. Nauk 383 (2002), 454–457.
- [38] by same author, The Cameron-Erdős conjecture, Dokl. Akad. Nauk 393 (2003), 749–752.
- [39] D. Saxton and A. Thomason, Hypergraph containers, arXiv:1204.6595 [math.CO].
- [40] by same author, List colourings of regular hypergraphs, Combin. Probab. Comput. 21 (2012), 315–322.
- [41] M. Schacht, Extremal results for random discrete structures, submitted.
- [42] E. Szemerédi, On sets of integers containing no elements in arithmetic progression, Acta Arith. 27 (1975), 199–245.
- [43] P. Turán, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941), 436–452.
- [44] P. Varnavides, On certain sets of positive density, J. London Math. Soc. 34 (1959), 358–360.
- [45] Y. Zhao, The number of independent sets in a regular graph, Combin. Probab. Comput. 19 (2010), 315–320.