Independent Sets on Path-Schemes

Sergey Kitaev Reykjavík University Ofanleiti 2 IS-103 Reykjavík Iceland

                         sergey@ru.is

Abstract We give the generating function for the number of independent sets on the class of well-based path-schemes (a kind of regularly structured graph), which generalizes the known result in this direction.

1 Introduction

Let G = (V, E) be a simple undirected graph with vertex set V = {1, 2, …, n} and set of edges E. An independent set (also called a stable set in the literature) of G is a subset S of V such that no two vertices in S are adjacent. The set of all independent sets of a graph G is denoted by I(G). An independent set is maximal if it is not a subset of any larger independent set, and maximum if there are no larger independent sets in the graph. The independence number α(G) (also called the stability number) is the cardinality of a maximum independent set in G.

The two problems of determining maximal and maximum independent sets have received considerable attention, particularly since the computation of the independence number is known to be an NP-complete problem [8]. These problems were extensively studied for various classes of graphs, including trees, forests, (connected) graphs with at most one cycle, bipartite graphs, k-connected graphs, and others (see [7] for a survey). The most efforts are made for the number of maximal independent sets rather than for finding α(G). However, counting cardinality of I(G), being a very challenging and interesting enumerative combinatorics problem, received even less attention, and very few papers deal with it (see, e.g., [1, 2, 3, 5, 9] and references therein). A motivation for finding |I(G)| is, for instance, the fact that for some classes of graphs, the set of independent sets I(G) has an interpretation in terms of other combinatorial objects (see [1, 3]). For example, Ehrenborg and Kitaev [3] showed that there is a bijection between the set of independent sets of a symmetric Ferrers graph on 2n vertices and the parts of all compositions (ordered non-empty partitions) of n + 1.

The main objective in this paper is to obtain the generating function for the number of independent sets on the class of well-based path-schemes (see Section 2 for definitions), which generalizes the known result in this direction [9]. Although it is possible to provide an entirely self-contained proof of our main result, we proceed by reformulating the problem in terms of combinatorics on words, and then by applying a known result. Providing such a proof we give an approach to solve some graph theory problems using combinatorics on words (there are other examples in the literature when a combinatorics on words approach solves a graph theory problem, e.g., Evdokimov [4] constructed chains of maximal length in the n-dimensional unit cube reducing the problem under consideration to a combinatorics on words problem).

2 Preliminary

Let V = {1, 2, …, n} and M be a subset of V. A path-scheme P (n, M) is a graph G = (V, E), where the edge set E is {(x, y) | |x−y| ∈ M}. See Figure 1 for an example of a path-scheme.

1 2 3 4 5 6

Figure 1: The path-scheme P (6, {2, 4}).

Note that from the definition, P (n, M) is a simple graph, and thus its adjacency matrix A is symmetric. Moreover, if the columns and rows of A are ordered naturally, that is, node i corresponds to the i-th column and to the i-th row, then for 1 ≤ i < j < n, A(i, j) = A(i + 1, j + 1), since |i − j| is in M if and only if |(i + 1) − (j + 1)| is in M. Thus, we can construct the upper triangular part of A by shifting the first row to the right, that is, we place the first row, and row i + 1 is obtained by shifting row i one element to the right. Then we use the symmetry to fill in the remain entries of A.

Suppose k ≥ 2 and A = \{A_{1}, A_{2}, …, A_{k}\} is a set of words of the form A_{i} = 1 \underbrace{0 … 0}_{a_{i}−1} 1,

where a_{i} ≥ 1, and a_{i} < a_{j} if i < j. Moreover, we assume that for any i > 1 and A_{i} ∈ A, if we replace any number of 0’s in A_{i} by 1’s, then we obtain a word A′_{i} that contains the word A_{j} ∈ A as a subword for some j < i. In this case, we call A well-based set, and we call the sequence of a_{i}s associated with A well-based sequence.

Any well-based set must contain the word 11. Indeed, if we replace all 0’s by 1’s in, say, A_{2} then A_{1} must be a subword of the obtained word. So, we may extend our definition to the case k = 1. We define A = {11} to be a well-based set. We see that any well-based sequence starts from 1, and, clearly, if we take any number of consecutive initial elements of a well-based sequence, we get a well-based sequence. A few examples of well-based sets and associated with them sequences are given in Table 1 (i copies of 0 is denoted by 0^{i}).

Well-based set  Corresponding well-based sequence
{11, 101, 1001, …, 10^{k−1}1}  1, 2, 3, …, k
{11, 1001, 100001, …, 10^{2m}1}  1, 3, 5, …, 2m + 1
{11, 101, 1001, 1000001, 10000001} 1,2,3,6,7

Table 1: Examples of well-based sets and well-based sequences

We call a scheme P (n, M) a well-based scheme, if the elements of M listed in increasing order form a well-based sequence.

It is known [9], that |I(P (n, {1}))| = F (n + 2) and, more generally,

|I(P (n, {1, 2, …, k − 1}))| = F_{k}(n + k),  (1)

where F (n) is the n-th Fibonacci number and F_{k}(n) is the n-th k-generalized Fibonacci number defined, in our context, as F_{k}(1) = ⋯ = F_{k}(k) = 1 and F_{k}(n) = F_{k}(n−1)+F_{k}(n−k). Note that in our notation, F (n) = F_{2}(n).

In Section 3, we find the generating function for the number of independent sets of an arbitrary well-based path-scheme. The known result mentioned above can be extracted from our generating functions, since it corresponds to a well-based sequence 1, 2, …, k − 1.

Before going further, we need some notions and results in a certain area of combinatorics on words which perhaps can be best described as “binary strings and substring avoidance.” In our presentation we follow [11], although the original ideas appear in [6].

A binary string is a string that consists only of the digits 0 and 1. If X_{1} = a_{0}a_{1} … a_{k−1} and X_{2} = b_{0}b_{1} … b_{ℓ−1} are two binary strings of length k and ℓ respectively, then the correlation c_{12} = c_{0}c_{1} … c_{k−1} is the binary string defined with respect to whether k ≤ ℓ or ℓ ≤ k as follows:

k ≤ ℓ: For all 0 ≤ j ≤ k − 1, c_{j} = 1 if a_{i} = b_{ℓ−k+i+j} for all i = 0, 1, …, k − j − 1, and c_{j} = 0 otherwise;

k > ℓ: For all 0 ≤ j ≤ k − ℓ, c_{j} = 1 if b_{i} = a_{k−ℓ+i−j} for all i = 0, 1, …, ℓ − 1, and c_{j} = 0 otherwise; for all k−ℓ+1 ≤ j ≤ k−1, c_{j} = 1 of a_{i} = b_{ℓ−k+i+j} for all i = 0, 1, …, k−j−1 and c_{j} = 0 otherwise.

For example, if X_{1} = 110 and X_{2} = 1011, then c_{12} = 011 and c_{21} = 0010, as depicted below:

1 1 0 1 0 1 1 0 1 0 1 1  1 1 0 1 1  1  1 0 1 1 1 1 0 0 1 1 0  0 1 1 0  1 1 1 0  0

So, in general c_{ij} ≠ c_{ji} (they can even be of different lengths). The autocorrelation of a word X_{1} is just c_{11}, the correlation of X_{1} with itself. For instance, if X_{1} = 1011 then c_{11} = 1001. This is convenient to interpret a correlation c_{ij} = c_{0}c_{1} … c_{k−1} as a polynomial c_{ij}(x) = c_{0} + c_{1}x + ⋯ + c_{k−1}x^{k−1}.

The following theorem is the main tool in our considerations.

Theorem 1. ([11, Th. 24]) The generating function for the number of binary strings that avoid the substrings b_{1}, b_{2}, …, b_{n}, of length ℓ_{1}, ℓ_{2}, …, ℓ_{n} respectively, none included in any other, is given by the formula

S(x) = \frac{\begin{matrix}−c_{11}(x) & ⋯ & −c_{1n}(x) \\ ⋮ & ... & ⋮ \\ −c_{n1}(x) & ⋯ & −c_{nn}(x) \end{matrix}}{\begin{matrix}(1 − 2x) & 1 & ⋯ & 1 \\ x^{ℓ_{1}} & −c_{11}(x) & ⋯ & −c_{1n}(x) \\ ⋮ & ⋮ & ... & ⋮ \\ x^{ℓ_{n}} & −c_{n1}(x) & ⋯ & −c_{nn}(x) \end{matrix}} .  (2)

3 Main Result

Our main result in this paper is the following theorem.

Theorem 2. Let M = {a_{1}, a_{2}, …, a_{k}} be a subset of V = {1, 2, …, n} such that the sequence a_{1}, a_{2}, …, a_{k} is well-based (in particular, a_{1} = 1). Let c(x) = 1 + ∑_{i=1}^{k} x^{a_{i}}. Then the generating function for the number of independent sets on the well-based path-scheme P = P (n, M) (with vertex set V) is given by

G(x) = \frac{c(x)}{(1 − x)c(x) − x}.

Proof. If x is a vertex in P, we denote by N(x) the set of its neighbors in P. We identify independent sets with the corresponding (0,1)-incidence vectors, indexed by V. These vectors are called stable vectors in some literature. Let S(P) denote the set of all stable vectors of P. Then

S_{n}(P) = {T ∈ {0, 1}^{n} | ∀x ∈ V T (x) = 1 ⇒ T (y) = 0 ∀y ∈ N(x)}.

Thus, our goal is equivalent to finding the generating function for |S_{n}(P)|.

Let A be the adjacency matrix of P with rows and columns ordered naturally. One can see that the first row of A has 0’s everywhere except for the entries A(1, a_{i} + 1), where i = 1, 2, …, k. Indeed, if A(1, x + 1) = 1, and x ≠ a_{i} for some i, then we must have x ∈ M, contradiction.

Recall that the upper triangular part of A is constructed by shifting the first row to the right, which gives that a vector T belongs to S_{n}(P) if and only if T avoids each substring b_{i} = 1 \underbrace{0 … 0}_{a_{i}−1} 1 for i = 1, 2, …, k. Let us prove the last statement.

We first prove necessity. Assume that for a vector T ∈ S_{n}(P), T (j) = T (j + a_{i}) = 1 and T (t) = 0 for j < t < j +a_{i} and 1 ≤ j ≤ n−a_{i}. From the way we construct A, (j +a_{i}) ∈ N(j). We get a contradiction with the definition of S_{n}(P).

Let us now prove sufficiency. We need to show that if a vector T does not belong to S_{n}(P) then it must contain b_{s} for some s, 1 ≤ s ≤ k. A vector T does not belong to S_{n}(P) if there exist two adjacent nodes, say j and h, j < h, such that T (j) = T (h) = 1. From the construction of A, we must have h = j + a_{i} for some i, 1 ≤ i ≤ k. If T (t) = 0 for all t such that j < t < h = j + a_{i} then we are done. If some of T (t), for j < t < h, are not 0’s, T must contain b_{s} for some s, 1 ≤ s < i due to the fact, that the sequence of a_{i}s is well-based, and therefore the set {b_{1}, b_{2}, …, b_{k}} is well-based (this set is associated with the sequence)^{1}.

So, |S_{n}(P)| is given by the number of different binary strings avoiding the substrings b_{1}, b_{2}, …, b_{k}, and we may use Theorem 1 since none of b_{i}s is included in any other.

One can easily check that the autocorrelation c_{ii}(x) = 1 + x^{a_{i}}, and for i < j, the correlations c_{ij}(x) = x^{a_{i}} and c_{ji}(x) = x^{a_{j}}. The corresponding lengths are ℓ_{i} = a_{i} + 1, for 1 ≤ i ≤ k. Thus (2) in our case is

G(x) = \frac{\begin{matrix}−(1 + x^{a_{1}}) & −x^{a_{1}} & ⋯ & −x^{a_{1}} \\ −x^{a_{2}} & −(1 + x^{a_{2}}) & ⋯ & −x^{a_{2}} \\ ⋮ & ⋮ & ... & ⋮ \\ −x^{a_{k}} & −x^{a_{k}} & ⋯ & −(1 + x^{a_{k}}) \end{matrix}}{\begin{matrix}(1 − 2x) & 1 & 1 & ⋯ & 1 \\ x^{a_{1}+1} & −(1 + x^{a_{1}}) & −x^{a_{1}} & ⋯ & −x^{a_{1}} \\ x^{a_{2}+1} & −x^{a_{2}} & −(1 + x^{a_{2}}) & ⋯ & −x^{a_{2}} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ x^{a_{k}+1} & −x^{a_{k}} & −x^{a_{k}} & ⋯ & −(1 + x^{a_{k}}) \end{matrix}} .

To take the determinant in the numerator, we replace the first row by the sum of all the rows, then factor out some terms from the determinant, and then add to each column the first one multiplied by (-1) to get

(−1)^{k} · (1 + ∑_{i=1}^{k} x^{a_{i}}) · \begin{matrix}1 & 0 & 0 & ⋯ & 0 \\ x^{a_{2}} & 1 & 0 & ⋯ & 0 \\ x^{a_{3}} & 0 & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ x^{a_{k}} & 0 & 0 & ⋯ & 1 \end{matrix} = (−1)^{k} · c(x).

To take the determinant in the denominator, we may replace the first column by the sum of the first column and the last column times x; we replace any column i, 1 < i < k + 1 by the sum of column i and the last column times (-1). Finally, we replace the last row by the sum:

\frac{x}{1 − x} · (row 1) + (row 2) + ⋯ + (row (k+1)),

1Note that this is the only place we use the fact that the sequence a_{1}, a_{2}, …, a_{k} is well-based.

to get an upper triangular matrix having the determinant

(−1)^{k} · (1 − x) (1 − \frac{x}{1 − x} + ∑_{i=1}^{k} x^{a_{i}}) = (−1)^{k} · ((1 − x)c(x) − x).

Thus the statement is proved.

Let us discuss some corollaries to Theorem 2.

If M = {1, 2, …, k − 1} then we can apply our theorem, since the sequence 1, 2, …, k − 1 is well-based. In this case, we get

G(x) = ∑_{n≥0} g_{n}x^{n} = \frac{1 + x + ⋯ + x^{k−1}}{1 − x − x^{k}} ,

and thus, using the form of the generating function, the sequence g_{n} = |I(P (n, M))| satisfies the recurrence g_{n} = g_{n−1} + g_{n−k} with g_{1−k} = g_{2−k} = ⋯ = g_{0} = 1, which agrees with (1).

If M = {1, 3, 5} then M is well-based. Theorem 2 gives us that

G(x) = ∑_{n≥0} w_{n}x^{n} = \frac{1 + x + x^{3} + x^{5}}{1 − x − x^{2} + x^{3} − x^{4} + x^{5} − x^{6}} .

Thus, in this case the sequence w_{n} satisfies the recurrence formula

w_{n} = w_{n−1} + w_{n−2} − w_{n−3} + w_{n−4} − w_{n−5} + w_{n−6},

with the initial conditions: w_{−5} = w_{−4} = w_{−3} = w_{−2} = w_{−1} = w_{0} = 1. The initial values for w_{n} = |I(P (n, M))| and n ≥ 1 are

2, 3, 5, 7, 11, 15, 23, 32, 49, 69, 105, 149, ….

Finally, we state the following corollary to Theorem 2 that can be proved in a standard way by the partial fraction expansion of the generating function G(x) from Theorem 2.

Corollary 3. Let M, V, c(x), and P (n, M) satisfy the conditions of Theorem 2. Also, ρ is the largest zero (|ρ| is maximal among all the zeros) of the function

Q(x) = (1 − x)c(x) − x = 1 − x − x^{2} + (1 − x) ∑_{i=2}^{k} x^{a_{i}}.

Then asymptotically, the growth rate of |I(P (n, M))| is

|I(P (n, M))| ≲ c|ρ|^{n}

for some constant c.

If k = 1 in Corollary 3 then ρ = \frac{1+\sqrt{5}}{2}, and if k = 2 there then it can be shown^{2} that 0.6 ≤ ρ ≤ \frac{1+\sqrt{5}}{2}.

2This observation was made by the referee.

4 Problems on the Well-Based Sets

Although the paper is devoted to counting independent sets, it is interesting to consider what can be said on the number of well-based sets. Can we provide a formula and/or asymptotic for it to specify the portion of the well-based path-schemes among all path-schemes?

The initial values of the sequence corresponding to the number of well-based sets was kindly provided to the author by Michael Slone:

1, 2, 4, 6, 11, 15, 26, 36, 57, 79, 130, 170, 276, 379, 579, 784, 1249, 1654, 2615, 3515.

This sequence appears as \underline{A103580} in [10] and has the following interpretation: it is the number of non-empty subsets S of 1, 2, …, n that have the property that no element x of S is a nonnegative integer linear combination of elements of S − x.

References

[1] A. Burstein, S. Kitaev and T. Mansour, Independent sets in certain classes of (almost) regular graphs, preprint.

[2] N. Calkin and H. Wilf, The number of independent sets in a grid graph. SIAM J. Discrete Math. 11 (1998), 54–60.

[3] R. Ehrenborg and S. Kitaev, Ferrers graphs, their independent sets and independence complexes, in preparation.

[4] A. Evdokimov, On the maximal chain length of an unit n-dimensional cube, Math. Notes 6, no. 3 (1969), 309–319. (in Russian)

[5] F. Forbes and B. Ycart, Counting stable sets on Cartesian products of graphs, Discrete Math. 186 (1998), 105–116.

[6] L. J. Guibas and A. M. Odlyzko, String overlaps, pattern matching, and nontransitive games, J. Comb. Theory Ser. A 30 (1981), 19–42.

[7] M. J. Jou and G. J. Chang, Survey on counting maximal independent sets, Proceedings of the Second Asian Mathematical Conference, S. Tangmance and E. Schulz eds., World Scientific, Singapore, 1995, 265–275.

[8] R. M. Karp, Reducibility among combinatorial problems, in R. E. Miller, J. W. Thatcher, eds., Complexity of Computer Computations, Plenum Press, New York (1972), 85–103.

[9] T. Sillke, Counting independent sets, http://www.mathematik.uni-bielefeld.de/ sillke/PROBLEMS/stable sets

[10] N. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically at http://www.research.att.com/njas/sequences [11] B. Winterfjord, Binary strings and substring avoidance, Master’s thesis, CTH and

Göteborg University (2002).

2000 Mathematics Subject Classification: Primary 05C69, 05A15; Secondary 68R15, 05A16. Keywords: Independent sets, path-schemes, generating functions, string avoidance.

(Concerned with sequence \underline{A103580}.)

Received August 1 2005; revised version received February 11 2006. Published in Journal of Integer Sequences, April 19 2006.

Return to Journal of Integer Sequences home page.