skip to main content

Kleitman-Winston Algorithm

Graph containers & bounds on the number of independent sets in a locally dense graph.


We will show that for a locally dense graph we can give a strong upper bound on the number of independent sets of a certain size. This specific method for graphs is an instance of the so-called container method, that allows to give bounds on structures appearing in larger objects with specific local properties. More specifically as applied to graph theory, this turns out to be quite helpful in proving lower bounds in Ramsey theory.

The proof presented here follows the one presented in the survey paper by Samotij [1] using methods originally presented in the paper by Winston and Kleitman [2]. Some elementary knowledge of graph theory is helpful, such as the notion of independent sets and induced subgraphs, but I try to be as explicit and clear as possible. I will try to stick to common graph theoretical notation, but for the sake of both readability and completeness an overview of notation is given at the end of the post.

Basic bounds

Let’s start with some basic bounds on the number of independent sets I(G)|\mathcal{I}(G)| in a graph GG. Recall that an independent set is a set of vertices in which no two are connected by an edge. If α(G)\alpha(G) refers to the independence number, ie. the size of the largest independent set in GG, we can certainly say that

2α(G)I(G)2^{\alpha(G)} \leq |\mathcal{I}(G)|

because every subset of the largest independent set is itself an independent set (recall that 2N2^{|N|} is the number of different subsets that can be formed from a set NN).

Similarly, we can give an upper bound of

I(G)k=0α(G)(V(G)k)|\mathcal{I}(G)| \leq \sum_{k=0}^{\alpha(G)} \binom{|V(G)|}{k}

as every independent set is a subset of size at most α(G)\alpha(G) over the vertices of GG.

Theorem Statement

We will now bound the number of independent sets of a certain size in a locally dense graph by showing that every independent set is part of a small container. These containers are constructed with the Kleitman-Winston algorithm. By counting these countainers, we can estimate the number of independent sets. The tightness property of the containers then allows us to give useful bounds on the number of independent sets.

Let us now turn to the actual theorem. For N,R,qNN, R, q \in \mathbb{N} and βR\beta \in \mathbb{R} with β[0,1]\beta \in [0, 1], let GG be a graph on NN vertices satisfying:

NReβq(1)\tag{1} N \leq R e^{\beta q}

In addition, we also require that G must be a β\beta-locally dense graph. That is, for every vertex subset AV(G)A \subseteq V(G) of size at least RR we have the following lower bound on the number of edges in the induced subgraph G[A]G[A]:

eG(A)β(A2)(2)\tag{2} e_G(A) \geq \beta \binom{|A|}{2}

Note that this corresponds to the situation where the subgraph spanned by AA over GG contains at least a β\beta-fraction of the edges of the corresponding complete graph over AA, or in other words, that the average degree of AA is at least β(A1)\beta (|A| - 1).


Given such a β\beta-locally dense graph GG satisfying (1) and (2), we can construct up to (Nq)\binom{N}{q} small containers C1,,CiC_1, \dots, C_i for 1i(Nq)1 \leq i \leq \binom{N}{q} of size at most R+qR + q. Every independent set of size exactly q+kq + k for kqk \leq q belongs to a container CiC_i.

For the number of independent sets in GG of size exactly q+kq + k we obtain:

I(G,q+k)(Nq)(Rk)(3)\tag{3} |\mathcal{I}(G, q + k)| \leq \binom{N}{q} \binom{R}{k}


Before describing the algorithm, let us fix a few technicalities. We need the notion of max-degree ordering to ensure high-degree vertices are quickly removed from the graph and the container quickly shrinks. For a vertex set AV(G)A \subseteq V(G), the max-degree ordering (v1,,vA)(v_1, \dots, v_{|A|}) is defined by the degree of vertices over the induced subgraph G[A]G[A] in descending order, where potential ties are broken by a fixed but arbitrary total order over V(G)V(G). In this case v1v_1 has the highest degree, etc.

The Kleitman-Winston algorithm works by iteratively removing high-degree vertices as outlined above:

Kleitman-Winston algorithm
  • Input: Independent set II(G)I \in \mathcal{I}(G), integer qIq \leq |I|
  • Output: selected vertices SS, available vertices AA
  • Procedure:
    1. Set available vertices A=V(G)A = V(G), selected vertices S=S = \varnothing
    2. Iterate for i=1,,qi=1, \dots, q:
      • Let A=(v1,,vA)A = (v_1, \dots, v_{|A|}) be ordered by max-degree
      • Let tit_i be the first index in the ordering of AA such that vtiIv_{t_i} \in I
        (i.e. first remaining vertex of II by max-degree ordering in induced subgraph G[A]G[A]).
      • Move vtiv_{t_i} from AA to SS
      • Remove higher-degree vertices Xi=(v1,,vti1)X_i = (v_1, \dots, v_{t_i - 1}) from AA:
        A=AXiA = A \setminus X_i
      • Remove vtiv_{t_i} and its neighborhood NA(vti)\mathcal{N}_A(v_{t_i}) from AA:
        A=A({vti}NA(vti))A = A \setminus (\{ v_{t_i} \} \cup \mathcal{N}_A(v_{t_i}))
    3. Output SS and AA

The container of II is given by C:=SAC := S \cup A. Notice that the tightness of the container is apparent in that fact that SICS \subseteq I \subseteq C.


The algorithm maintains a few invariants, that help prove correctness: A|A| decreases monotonically as we remove vertices in every iteration, while S|S| increases monotonically. Also notice that the previous observation SI(SA)S \subseteq I \subseteq (S \cup A) holds at every iteration of the algorithm.

It is clear that the algorithm always succeeds in constructing the set of selected vertices SS from qIq \leq |I| vertices of II. This is because the algorithm always selects the next highest degree vertex viv_i of II occuring in the subgraph G[A]G[A] at every step, i.e. no vertex viIv_i \in I is ever removed from AA and not added to SS as a discarded higher-degree vertex. In addition, the vertices of II form an independent set by assumption, and as such a vertex viv_i is never removed as part of the neighborhood of another selected vertex.

Size of A

To conclude tightness of the containers, we must show that the final AA returned from the algorithm is sufficiently small. In fact, we will show that AR|A| \leq R. In the following, we will denote by AiA_i the set of available vertices at the beginning of the i-th iteration of the algortithm, and by Ai=AiXiA'_i = A_i \setminus X_i the set of available vertices after removing higher-degree vertices but before remoing vtiIv_{t_i} \in I.

First, note that by the Handshaking lemmawe obtain an expression for the average degree of vertices:

1VvVdeg(v)=2EV(4)\tag{4} \frac{1}{|V|} \sum_{v \in V} deg(v) = \frac{2|E|}{|V|}

Suppose for sake of contradiction A>R|A| > R for the final set of available vertices. Then it must be that the vtiSv_{t_i} \in S selected in every iteration must have been selected from a set of size at least RR, even after removal of other higher-degree vertices (recall that A|A| decreases monotonically throughtout the algorithm). Or, in other words, at the start of the i-th iteration with currently available vertices AiA_i and higher-degree vertices XiX_i scheduled for removal, Ai:=AiXi>R|A'_i| := |A_i \setminus X_i| > R.

Using the bound (2) on the edge-count:

eG(Ai)β(Ai2)=βAi(Ai1)2e_G(A'_i) \geq \beta \binom{|A'_i|}{2} = \beta \frac{|A'_i|(|A'_i|-1)}{2}

As we choose vtiv_{t_i} with maximum degree from AiA'_i, we know vtiv_{t_i} must at least have the average degree (4) of AiA'_i:

degAi(vti)2eG(Ai)Aiβ(Ai1)\deg_{A'_i}(v_{t_i}) \geq \frac{2e_G(A'_i)}{|A'_i|} \geq \beta (|A'_i| - 1)

Recalling the definition of Ai|A'_i|:

Ai1=AiXi1=AiXi1Ai(ti1)1=Aiti\begin{aligned} |A'_i| - 1 = |A_i \setminus X_i| - 1 &= |A_i| - |X_i| - 1 \\ |A_i| - (t_i - 1) - 1 &= |A_i| - t_i \end{aligned}

In total we remove Xi+N(vti)+1|X_i| + |\mathcal{N}(v_{t_i})| + 1 vertices from AiA_i in every round. Putting everything together:

Ai+1Ai(Xi+N(vti)+1)Ai(Xi+degAi(vti))Ai(ti+β(Aiti))AiβAi=Ai(1β)\begin{aligned} |A_{i+1}| &\leq |A_i| - (|X_i| + |\mathcal{N}(v_{t_i})| + 1) \\ & \leq |A_i| - (|X_i| + \deg_{A'_i}(v_{t_i})) \\ &\leq |A_i| - (t_i + \beta (|A_i| - t_i) ) \\ &\leq |A_i| - \beta|A_i| = |A_i| (1 - \beta) \end{aligned}

where we used that β1\beta \leq 1 for the last inequality

We find that the set of available vertices AA shrinks at least by a factor of (1β)(1 - \beta) in every iteration. Together with the fact that the initial set AA is V(G)V(G) we obtain a contradiction to the initial condition (1) on the number of vertices in GG:

A(1β)qNeβqNR(5)\tag{5} |A| \leq (1 - \beta)^q N \leq e^{-\beta q} N \leq R

Here we used the well-known inequality (1+x)ex(1 + x) \leq e^x. After qq iterations, the initial set of available vertices has necessarily shrunk to a set of at most RR vertices.

Final bound

Let us now finally give the bound on the number of independent sets of size exactly q+kq + k. The bound (3) follows from the observation, that there are at most (Nq)\binom{N}{q} different ways to choose SS and therefore the first qq vertices of an independent set, and at most (Rk)\binom{R}{k} different ways to choose the kk remaining vertices from AA, which has size at most RR.

Another useful, but less sharp bounds, can be obtained from one of the various inequalities on the binomial coefficient:

I(G,q+k)Nqq!(Rk)(6)\tag{6} |\mathcal{I}(G, q + k)| \leq \frac{N^q}{q!}\binom{R}{k}

Wikipediahas an extensive collection of such bounds.

Overview of notation

  • Vertex set V(G)V(G)
  • Edge count eG(X)e_G(X): Number of edges in GG on vertex set XX
  • Neighborhood N(v)\mathcal{N}(v): set of vertices adjacent to vv
  • Induced subgraph G[A]G[A]: Obtained from GG by keeping all vertices in AA and their edges among them
  • Independence number α(G)\alpha(G): Size of largest independent set in GG
  • Independent sets I(G)\mathcal{I}(G): Collection of all independent sets in GG
  • Independent sets I(G,m)\mathcal{I}(G, m): Collection of all independent sets in GG of size exactly mm

Further reading

Some ressources for further details, including applications to various combinatorial problems and extensions of the container method to hypergraphs, are given below: