Counting independent sets Torsten Sillke, 1.11.96 ------------------------- Let I(G) count the independent sets of a Graph G. This number can be determined for some special graphs. I am interessted in UPPER bounds. But let's look at some special graphs first. Multipartite complete Graphs: I( K_a1,a2,...,am ) = 2^a1 + 2^a2 + ... + 2^am - m + 1 Path-Schemes: I( P_n ) = I( P(n, {1}) ) = Fibonacci(n+2) I( P(n, {1,2,...,k-1}) ) = F_k(n+k) Cyclic-Schemes: I( C_n ) = I( C(n, {1}) ) = Fibonacci(n+1) + Fibonacci(n-1) = Lucas(n) I( C(2n, {1,n}) ) = (1+sqrt(2))^n + (1-sqrt(2))^n - (-1)^n (Achim Flammenkamp, 1996) I( C(n, {1,2,...,k-1}) ) = F_k(n+1) + (k-1)*F_k(n-k+1) Trees: (H. Wilf) Zoltan Furedi, the number of maximal independent sets in connected graphs, J. Graph Theory 11 (1987), 463-470. Grids: Neil Calkin, Herbert S. Wilf; The number of independent sets in a grid graph, (1996) http://www.cis.upenn.edu/~wilf/gridgrap.ps.gz Abstract: If f(m,n) is the (vertex) independence number of the m*n grid graph, then we show that the double limit eta = lim_{m,n->oo} f(m,n)^(1/(m*n)) exists, thereby refining earlier results of Weber and Engel. We establish upper and lower bounds for eta, and prove that 1.503047782 <= eta <= 1.5035148. Numerical computations suggest that the true value of eta (the "hard square constant") is around 1.5030480824753323. Karl Weber; On the number of stable sets in an m*n lattice, Rostock. Math. Kolloq. 34 (1988) 28-36. (MR 89i:05172) The notation used in the cases above: Path-Scheme: P(n, M) with M a subset of the positive integers Vertex_set = { 0, 1, ..., n-1 } Edge-Set = { (x,y) | x-y in M } Cyclic-Scheme: C(n, M) with M a subset of the positive integers Vertex_set = { 0, 1, ..., n-1 } Edge-Set = { (x,y) | x-y mod n in M } Generalized Fibonacci-numbers F_k(1) = ... = F_k(k) = 1 F_k(n) = F_k(n-1) + F_k(n-k) Miles; Generalized Fibonacci Numbers and associated Matrices, AMM 67 (1960) 745-752 Miller; On genralized Fibonacci Numbers, AMM 78 (1971), 1108-1109 G. N. Raney; Generalization of Fibonacci squences to n dimensions, Cnad. J. Math. 18 (1966) 332-349 Bounds depending on n (number of vertices) and d (minimal degree): ------------------------------------------------------------------ Conjectures (Torsten Sillke): ----------------------------- Upper Bound (general graphs): The number of independent sets for graphs with minimal degree d is at most: (a) UB(n,d) = 2^(n-d) + 2^d - 1 // for sparse graphs d <= n/2 (b) UB(n,d) = n * (2^(n-d) - 1)/(n-d) + 1 // for dense graphs d >= n/2 The bound (a) is reached for Graphs K_n-d,d. The bound (b) is reached for Graphs K_m,m,...,m with n = k * m, d = n - m. Upper Bound (regular graphs): The number of independent sets for d-regular graphs is at most: (a) UB_reg(n,d) <= (2*2^d - 1) ^ (n/(2*d)) // for sparse graphs d <= n/2 (b) UB_reg(n,d) <= n * (2^(n-d) - 1)/(n-d) + 1 // for dense graphs d >= n/2 The bound (a) is reached for Graphs k * K_d,d with n = 2d * k. The bound (b) is reached for Graphs K_m,m,...,m with n = k * m, d = n - m. Lower Bound: LB(n,d) = LB_reg(n,d) = (d + 2)^(n/(d+1)) The bound is reached for graphs k * K_d+1 with n = k * (d+1). How must the conjectures above be generalzed to make them provable? To support the upper bounds for regular graphs the small cases have been computed. The maximal number of independent sets: (d-regular connected graphs) --------------------------------------- Let I(n,d) (I_c(n,d)) be the maximal number of independent sets for d-regular simple (connected) graphs with n vertices. Achim Flammenkamp calculated the following table of the maximal number of independent sets for connected graphs I_c(n,d) : d=2 d=3 d=4 d=5 d=6 d=7 d=8 d=9 d10 d11 d12 d13 d14 d15 d16 n=2 - - - - - - - - - - - - - - - n=3 4 - - - - - - - - - - - - - - n=4 7 5 - - - - - - - - - - - - - n=5 11 - 6 - - - - - - - - - - - - n=6 18 15 10 7 - - - - - - - - - - - n=7 29 - 16 - 8 - - - - - - - - - - n=8 47 35 31 18 13 9 - - - - - - - - - n=9 76 - 40 - 22 - 10 - - - - - - - - n10 123 84 68 63 33 23 16 11 - - - - - - - n11 199 - 93 - 58 - 25 - 12 - - - - - - n12 322 207 154 133 127 60 46 29 19 13 - - - - - n13 521 - 215 - 145 - 66 - 30 - 14 - - - - n14 843 498 354 285 262 255* 112 71 48 32 22 15 - - - n15 1364 - 531 - 281* - >=149 - 94 - 36 - 16 - - n16 2207 1202 863* 623* 547* 519* 511* 61 37 25 17 - n17 3571 - 1249* - 665* - - 39 - 18 n18 5778 2970 63 43 28 n19 9349 - - 44 n20 15127 7128* appended * indicates only graphs without any C3 checked Gunnar Brinkmann provieded Achim with regular graph generator programs. The I(n,2) case is easily checked: I(n,2) = 3 if n=3 7^m if n=4m 11*7^m if n=4m+5 18*7^m if n=4m+6 29*7^m if n=4m+7 The value is attained for C_3 m times C_4 m times C_4 and one C_5 m times C_4 and one C_6 m times C_4 and one C_7. This is easy to prove as I(C_n) = Lucas(n) = phi^n + (-phi)^(-n) with phi = (sqrt(5) + 1)/2. The I(n,3) case is easily conjectured: I(n,3) = (defined for n even) 5 if n=4 15^m if n=6m 35*15^m if n=6m+8 84*15^m if n=6m+10 The value is attained for K_4 m times K_3,3 m times K_3,3 and one (K_4,4 - matching) = cube-graph m times K_3,3 and one (K_5,5 - (C_4 and C_6)) An unrelated problem: --------------------- The maximal number of maximal independent set for connected graphs with n vertices is: 3 ^ (n/3). (Only maximal independent set are counted.) - Zoltan Furedi, the number of maximal independent sets in connected graphs, J. Graph Theory 11 (1987), 463-470. -- mailto:sillke@mathematik.uni-bielefeld.de http://www.mathematik.uni-bielefeld.de/~sillke/PROBLEMS/stable_sets