Irredundant sets in the m X n rook graph ======================================== 1. Representation as binary matrices A set of vertices in the rook graph can be represented as a binary m X n matrix with 1 meaning the vertex is included in the set. Rule 1: If a row of the matrix contains a 1 with both another 1 in the same row and another 1 in the same column then the vertex set is not irredundant. For example in: 0 1 0 1 1 0 0 0 0 the central 1 is redundant so the corrresponding set in the rook graph is not irredundant. Rule 2: If a row contains more than one 1 and there is no blank row then the vertex set is not irredundant. Similarly, if a column contains more than one 1 and there is no blank column then the set is not irredundant. For example in: 1 1 0 0 0 1 the first row includes a redundant 1. However in: 1 1 0 0 0 1 0 0 0 there are no redundant 1's since each 1 in the first row dominates a 0 in the final row. Rule 3: Conversely, any matrix that is not eliminated by either of the above two rules corresponds with an irredundant set. 2. Counting Irredundant sets In the following, x will be used as a polynomial variable to count the number of sets by the size of the set. Let a(m,n) be the number of irredundant sets in the m X n rook graph. Irredundant sets will be either dominating or not. Let b(m,n) be the number of irredundant sets that are dominating and p(m,n) the number of irredundant sets that are not dominating. a(m,n) = b(m,n) + p(m,n). Also let c(m,n) be the number of binary matrices with at least one all zero row and one all zero column and at most one 1 in any column. ___ \ c(m,n) = > binomial(n,i) * (n^i - n!*stirling2(i,n)) * x^i /___ i=0..m-1 Case dominating: Irredundant dominating sets are exactly the minimal dominating sets which are enumerated by A290632(m,n). b(m,n) = m^n * x^n + (n^m - n!*stirling2(m, n)) * x^m for m>=n. use b(m,n) = b(n,m) for m<n. In the case of m = n this reduces to b(n,n) = (2*n^2 - n!) * x^n. Case not dominating: In order to be non dominating there must be at least one all zero row and one all zero column. The intersection between the zero rows and zero columns is not dominated. By rule 2 and 3 this means other columns and rows may contain more than one 1 and we only need to pay attention to rule 1 above. Let k be the number of columns that contain more than one 1. Let r be the number of rows occupied by those k columns. (Each 1 must be in a separate row). The total number of ways of distributing the r 1's into the k columns so that each column has at least two 1's is given by k!*s(r, k) where s(r, k) are the associated stirling numbers of the second kind (A008299). The remaining m-k columns and n-r rows must by definition have at most one 1 in each column and must include at least one all zero column and one all zero row. This is counted by c(m-k, n-r). ___ ___ \ \ p(m,n) = > > binomial(m,k) * binomial(n,r) * k!*s(r,k) * x^r * c(m-k, n-r) /___ /___ k r =============================================================================== 3. Maximum size of irredundant set (upper irredundance number) Consideration of the formula to enumerate the irredundant sets yields the following formula for the maximum set size. IR(m,n) = max( max(m,n), m+n-4 ) for m>1 and n>1 IR(m,1) = IR(1,n) = 1 In the case of m = n this reduces to IR(n,n) = max(n, n-4). For m,n >= 5 the largest irredundant sets are those that are non dominating. For example 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 corresponds to an irredundant set of maximum size in the 5 X 5 rook graph. The number of irredundant sets of maximum size is m*(m-1)*n*(n-1) for IR(m,n) > max(m,n). 4. Irredundant sets of small size. Let size of irredundant set be k. Case k=0: The empty set is always an irredudant set => 1. Case k=1: Any single vertex is always an irredundant set => m * n. Case k=2: If both m and n are > 1, then any two vertices will be an irredundant set, otherwise there are no 2-irredundant sets. => binomial(m * n, 2) for m > 1, n > 1; otherwise 0. Case k=3: If both m and n are > 2, then any three vertices will be an irredundant set unless one of the vertices is on the same row as one of the others and the same column as the third. => binomial(m * n, 3) - m*n*(m-1)*(n-1) for m > 2, n > 2.