From: zpan@aol.com (ZPAN) Subject: A hard question, need your help Date: 20 Jun 1999 02:01:30 GMT Newsgroups: sci.math Keywords: maximal number of maximal cliques in a graph with N vertices There are N players. A N by N symmetric matrix with 1's and 0's indicates whether player i and player j can play together, where i, j are positive integers from 1 to N. For example, N=4 and the matrix is 1 1 0 0 1 1 1 1 0 1 1 1 0 1 1 1 From the above matrix, we know that player 1 and player 2 can play together (matrix[1,2]=matrix[2,1]=1 (yes)), player 1 and player 3 cannot play together(matrix[1,3]=matrix[3,1]=0 (no)). Similarly 1 and 4 cannot; 2 and 3 can, 2 and 4 can; 3 and 4 can. Find all of the possible groups of N players under the conditions (1) players who cannot play together should not be in the same group, and (2) if one group is a subset of another group, then it should not exist. It may seem unclear. Let me explain the conditions using the above matrix. (1) Find all possible groups as long as no players who cannot play together are not in the same group (condiiton 1). Groups are listed as follows, 1. Player 1 himself. 2. Player 2 himself. 3. Player 1 and 2. 4. Player 3 himself. 5. Player 2 and 3. 6. Player 4 himself. 7. Player 2 and 3 and 4. 8. Player 2 and 4. 7. Player 3 and 4. (2) eliminate groups which are subsets of other groups (condition 2). 1. Player 1 himself. Eliminated, a subset of group 3. 2. Player 2 himself. Eliminated, a subset of group 3. 3. Player 1 and 2. Kept. 4. Player 3 himself. Eliminated, a subset of group 5. 5. Player 2 and 3. Eliminated, a subset of group 7. 6. Player 4 himself. Eliminated, a subset of group 7. 7. Player 2 and 3 and 4. Kept. 8. Player 2 and 4. Eliminated, a subset of group 7. 7. Player 3 and 4. Eliminated, a subset of group 7. Two groups are left, they are Player 1 and 2 Player 2 and 3 and 4 Here we know there are two groups left. The question: For a given N, what is the maximum number of groups we can have (namely the matrix is not fixed, you can change the matrix whatever you want). More examples, 1. N=2, the maximum number of groups is 2. And the matrix should be 1 0 0 1 2 N=3, the maximum number of groups is 3. And the matrix is 1 0 0 0 1 0 0 0 1 3. N=4, the maximum number of groups is 4, and the matrices are 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 (we have four groups with player 1 in group 1, player 2 in group 2, player 3 in group 3, and player 4 in group 4). or 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 (we have four groups with player 1 & 2 in group 1, player 1 & 4 in group 2, player 2 & 3 in group 3, player 3 & 4 in group 4). I do not need to know those matrix, I just need to know what is the maximum number of groups we can have for a given N. I suspect that the maximum number of groups is also N, but I cannot show any evidence to support it. Any help is appreciated. Thanks, Ziqing ============================================================================== From: David G Radcliffe Subject: Re: A hard question, need your help Date: 20 Jun 1999 08:41:45 GMT Newsgroups: sci.math Ziqing Pan's question can be restated as follows: What is the greatest possible number of maximal cliques for a graph with N vertices? (A clique of a graph is a set of vertices such that every pair of vertices is joined by an edge) For N=3m, we can construct a graph with 3^m maximal cliques. Partitition the vertices into m groups with 3 vertices in each group, and join two vertices with an edge whenever the vertices are in different groups. Similarly, for N=3m-1 there is a graph with 2*3^(m-1) maximal cliques, and for N=3m-2, m>1 there is a graph with 4*3^(m-2) maximal cliques. Is this solution optimal? David Radcliffe radcliff @ uwm.edu ============================================================================== From: scott@math.csuohio.edu (Brian M. Scott) Subject: Re: A hard question, need your help Date: Mon, 21 Jun 1999 18:05:43 GMT Newsgroups: sci.math On 20 Jun 1999 07:41:37 GMT, David G Radcliffe wrote: >ZPAN wrote: >: There are N players. A N by N symmetric matrix with 1's and 0's indicates >: whether player i and player j can play together, where i, j are positive >: integers from 1 to N. >[...] >: The question: For a given N, what is the maximum number of groups >: we can have (namely the matrix is not fixed, you can change the matrix >: whatever you want). >[...] >: I do not need to know those matrix, I just need to know what is the maximum >: number of groups we can have for a given N. I suspect that the maximum >: number of groups is also N, but I cannot show any evidence to support it. >Let the players be divided into two groups of equal size, and suppose >that two players from different groups can play together, but two players >from the same group cannot. Then the number of groups is N/2 * N/2. >If N is odd then one group has one more member than the other, and the >number of groups is (N-1)/2 * (N+1)/2. >I don't know if this is optimal. The same idea gives a better result. Let S be a set of N individuals, and let {A(1), ..., A(k)} be a partition of S. Say that if x and y are distinct players, x is in A(i) and y is in A(j), x and y can play together iff i != j. Clearly the maximal compatible groups are transversals of the partition, so there are n(1)n(2)...n(k) of them, where n(i) = |A(i)|. If N is even, we can partition S into pairs and get 2^(N/2) groups. If N is odd, we can partition S into (N - 3)/2 pairs and a triplet and get 3 * 2^[(N-3)/2] groups. Come to think of it, that's clearly not optimal: lg(3) > 1.5, so 3^(N/3) > 2^(N/2). We want to maximize lg(k)/k, where k is the size of each piece of the partition. The maximum occurs at k = e, so 2 and 3 are the obvious possibilities, with 3 the better of the two. A little more calculation shows (barring computational error!) that among representations of N of the form N = 2m + 3n, the number of groups is maximized when m is minimized. Brian M. Scott