title | date | description | tags | |||
---|---|---|---|---|---|---|
Kleitman-Winston Algorithm |
2024-03-19 |
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.
Let's start with some basic bounds on the number of independent sets
because every subset of the largest independent set is itself an independent set (recall that
Similarly, we can give an upper bound of
as every independent set is a subset of size at most
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
In addition, we also require that G must be a
Note that this corresponds to the situation where the subgraph spanned by
{% msg "info", true, "Theorem" %}
Given such a
For the number of independent sets in
{% endmsg %}
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
The Kleitman-Winston algorithm works by iteratively removing high-degree vertices as outlined above:
{% msg "algorithm", true, "Kleitman-Winston algorithm" %}
<style>.msg--algorithm ul ol { list-style-type: decimal; }</style>-
Input
: Independent set$I \in \mathcal{I}(G)$ , integer$q \leq |I|$ -
Output
: selected vertices$S$ , available vertices$A$ -
Procedure
:- Set available vertices
$A = V(G)$ , selected vertices$S = \varnothing$ - Iterate for
$i=1, \dots, q$ :- Let
$A = (v_1, \dots, v_{|A|})$ be ordered by max-degree - Let
$t_i$ be the first index in the ordering of$A$ such that$v_{t_i} \in I$
(i.e. first remaining vertex of$I$ by max-degree ordering in induced subgraph$G[A]$ ). - Move
$v_{t_i}$ from$A$ to$S$ - Remove higher-degree vertices
$X_i = (v_1, \dots, v_{t_i - 1})$ from$A$ :
$A = A \setminus X_i$ - Remove
$v_{t_i}$ and its neighborhood $\mathcal{N}A(v{t_i})$ from$A$ :
$A = A \setminus ({ v_{t_i} } \cup \mathcal{N}A(v{t_i}))$
- Let
- Output
$S$ and$A$
- Set available vertices
{% endmsg %}
The container of
The algorithm maintains a few invariants, that help prove correctness:
It is clear that the algorithm always succeeds in constructing the set of selected vertices
To conclude tightness of the containers, we must show that the final
First, note that by the Handshaking lemma we obtain an expression for the average degree of vertices:
Suppose for sake of contradiction
Using the bound (2) on the edge-count:
As we choose
$$ \deg_{A'i}(v{t_i}) \geq \frac{2e_G(A'_i)}{|A'_i|} \geq \beta (|A'_i| - 1) $$
Recalling the definition of
In total we remove
$$ \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
We find that the set of available vertices
Here we used the well-known inequality
Let us now finally give the bound on the number of independent sets of size exactly
Another useful, but less sharp bounds, can be obtained from one of the various inequalities on the binomial coefficient:
Wikipedia has an extensive collection of such bounds.
- Vertex set
$V(G)$ - Edge count
$e_G(X)$ : Number of edges in$G$ on vertex set$X$ - Neighborhood
$\mathcal{N}(v)$ : set of vertices adjacent to$v$ - Induced subgraph
$G[A]$ : Obtained from$G$ by keeping all vertices in$A$ and their edges among them - Independence number
$\alpha(G)$ : Size of largest independent set in$G$ - Independent sets
$\mathcal{I}(G)$ : Collection of all independent sets in$G$ - Independent sets
$\mathcal{I}(G, m)$ : Collection of all independent sets in$G$ of size exactly$m$
Some ressources for further details, including applications to various combinatorial problems and extensions of the container method to hypergraphs, are given below:
- Wikipedia: https://en.wikipedia.org/wiki/Container_method
- Survey paper by Samotij: https://arxiv.org/pdf/1412.0940.pdf
- Lecture notes by Liu: https://homepages.warwick.ac.uk/staff/H.Liu.9/topic-comb-lecture15.pdf