A Family of Counter Examples to an Approach to Graph Isomorphism 8 0 0 Jin-Yi Cai∗ Pinyan Lu† Mingji Xia‡ 2 n January 10,2008 a J 2 1 Abstract ] C We give a family of counter examples showing that the two se- C quences of polytopes Φ and Ψ are different. These polytopes . n,n n,n s were defined recently by S. Friedland in an attempt at a polynomial c time algorithm for graph isomorphism. [ 2 v 1 Introduction 6 6 7 In a recent posting at arXiv (arXiv:0801.0398v1 [cs.CC] 2 Jan 2008 and 1 arXiv:0801.0398v2 [cs.CC] 4 Jan 2008), S. Friedland defined two sequences . 1 of polytopes Φ and Ψ . n,n n,n 0 Let Ω ⊂ Rn×n denote the n × n doubly stochastic matrices. Then 8 n + 0 Ψn,n ⊂ Ωn2 istheconvexhullofthetensorproductsA⊗B,whereA,B ∈ Ωn. v: Meanwhile Φn,n is defined to be the subset of Ωn2 defined by the following i set of linear constraints. X r n,n n,n a c = c = 1,i = 1,...,n,k = 1,...,n, X (i,k),(j,l) X (j,l),(i,k) j,l=1 j,l=1 n n n n c = c , c = c , X (i,k),(j,l) X (1,k),(j,l) X (j,k),(i,l) X (1,k),(j,l) j=1 j=1 j=1 j=1 where i = 2,...,n, and k,l = 1,...,n, ∗Universityof Wisconsin-Madison, [email protected] †Tsinghua University [email protected] ‡Instituteof Software, Chinese Academy of Sciences, [email protected] 1 n n n n c = c , c = c , X (i,k),(j,l) X (i,1),(j,l) X (i,l),(j,k) X (i,1),(j,l) l=1 l=1 l=1 l=1 where i = 2,...,n, and k,l = 1,...,n. ItwasshownthatΨ ⊆ Φ . (Intheearlierversionitwasclaimedthat n,n n,n Ψ = Φ . Ifthiswerethecase, thengraphisomorphismwouldbeinP,as n,n n,n one can reduce the problem to linear programming. In the Jan 4th version Friedlandstatedthattheequality Ψ = Φ “isprobablywrong”.) Inthis n,n n,n note we give an explicit family of counter examples showing Ψ 6= Φ . n,n n,n For every n ≥ 4, our examples consist of an exponential numberof matricies which are vertices of Φ , but do not belong to Ψ . n,n n,n 2 Counter Examples Let ρ ∈ S be the cyclic permutation (1 2 3 ... n). Let σ ∈ S be any n n permutation. Lemma 2.1. There are exactly n!−nφ(n) many permutations σ ∈S , such n that σρσ−1 does not belong to the subgroup generated by ρ. Proof. A conjugate σρσ−1 of ρ is also an n-cycle. To be in the subgroup generated by ρ, iff it is a power ρi for some i relatively prime to n. To be of this form, iff σ is of the form σ(i+1)−σ(i) (in a cyclic sense) is a constant relatively prime to n, which means there are exactly nφ(n) many. Let A be the matrix whose first row is (x ,x ,...x ), and its i-th row is 1 2 n obtained by applying (i−1) times the cyclic permutation ρ. Let B be the matrix whose first row is (x ,x ,...x ) permuted by σ, and its i-th row is 1 2 n obtained by further applying (i−1) times the cyclic permutation ρ. Lemma 2.2. Whenever σ ∈ S satisfies Lemma 1, there does not exist a n pair of permutation matrices P and Q, such that A= PBQ. Proof. The first two rows of B are σ(x ,x ,...x ) and ρσ(x ,x ,...x ). 1 2 n 1 2 n Assume for contradiction that there does exist a pair of permutation ma- trices P and Q, such that A = PBQ. The first two rows of BQ are qσ(x ,x ,...x ) and qρσ(x ,x ,...x ), where q is the permutation cor- 1 2 n 1 2 n responding to Q. They must be two rows of A, so there exist i and j (i 6= j) such that qσ(x ,x ,...x ) = ρi(x ,x ,...x ) and qρσ(x ,x ,...x ) = 1 2 n 1 2 n 1 2 n ρj(x ,x ,...x ). We get σ−1ρσ = ρj−i, contradicting with lemma 1. 1 2 n 2 Suppose A = (a ) is an n×n matrix. we use A to denotes the column ij vector (a ,...,a ,a ,...,a ,a ,...,a )T of blength n2. 11 1n 21 2,n 3,1 nn Given A and B, define T to be the n2 ×n2 matrix composed of 0 and 1/n such that A = TB. An examplebof thibs is shown as follows, for n = 4 and σ = (3 4): x x x x x x x x 1 2 3 4 1 2 4 3     x x x x x x x x A= 2 3 4 1 ,B = 2 4 3 1 ,  x x x x   x x x x  3 4 1 2 4 3 1 2      x x x x   x x x x  4 1 2 3 3 1 2 4 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0   0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0  0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0     0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1     0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0     0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0     0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1     1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0  T = 1/4   0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0      0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1      1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0     0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0     0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1     1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0     0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0     0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0  Theorem 2.1. For any σ ∈ S satisfying Lemma 1.1, the matrix T is an n extreme point of Φ . However, T 6∈ Ψ . n,n n,n Proof. By the definition of A, B and T = (t ), for each fixed pair (i,k),(j,l) i,j, (t ) (respectively, for each fixed k,l, (t )) is a permutation (i,k),(j,l) (i,k),(j,l) matrix multiplied by 1/n. Obviously, T ∈ Φ . For each double row index n,n (i,k), either fix i, or fix k, and varying the other index, and for each double column index (j,l), either fix j, or fix l, and varying the other index, we always get an n by n permutation matrix. Suppose T = w T , where T ∈ Φ , w > 0, and w = 1. So s s s s n,n s s s P P withineachblock(fixedi,j,varyingkandl,)thenon-zeroentriesofT area s subset of non-zero entries of T within that block, which form a permutation matrix. then by the equations for T within the block, it must be either s 3 totally zero or a positive multiple of the same permutation matrix made up of non-zero entries of T within that block. For each block, the permutation matrix is the same for every T . The multipliers form a doubly stochastic s n,n matrix M ∈ Ω , by the global sum = 1. Therefore T is as follows: s n Pj,l=1 s its (i,j) block is obtained by multiplying each entry of a doubly stochastic matrix M ∈ Ω with the permutation matrix of T for each block. s n n n Now if we consider the sum c = c , by the Pj=1 (i,k),(j,l) Pj=1 (1,k),(j,l) property of T each row of M is a constant. (Similarly each column of M s s is a constant.) Thus M is just the all 1/n matrix 1/nJ. s This implies that there is exactly one term in the sum T = w T , s s s P and T is an extreme point. Assumefor acontradiction that T ∈ Ψ and T = w P ⊗Q , where n,n s s s s P P ,Q are permutation matrices, w > 0, and w = 1. We get T ≥ s s s s s P w P ⊗Q (Here the relation of ≥ is entry-wise). For any x ,x ,...,x ≥ 0, 1 1 1 1 2 n TB ≥ w P ⊗ Q B, that is, A ≥ w P BQ . By lemma 1.2, P BQ is 1 1 1 1 1 1 1 1 diffberent from A, sobtheremust bean entry (i,j) such that they are different at thatentry. Notice that each entry ofAor P BQ is asinglevariable from 1 1 {x ,...,x }. W.l.o.g, we can assume the (i,j)-th entry of A and P BQ 1 n 1 1 are x and x . We can set x = 0 and x = 1 such that A <(w P BQ ) , 1 2 1 2 ij 1 1 1 ij which is a contradiction. So T 6∈ Ψ . n,n Before we posted this note, we note that Babai (http://people.cs.uchicago.edu∼laci/polytope.pdf)andOnn(arXiv:0801.1410) have both pointed out that the linear optimization problem over the poly- tope Ψ can solve NP-complete problems, and therefore it is unlikely that n,n Ψ canbedefinedbyapolynomialnumberof(in)equalities asΦ can. In n,n n,n (http://people.cs.uchicago.edu∼laci/polytope-correspondence.pdf),Babaialso mention that Joel Rosenberg already gave a counter example showing the two polytopes are different, for n = 4. References [1] L. Babai, The double permutation polytope is NP-hard. http://people.cs.uchicago.edu∼laci/polytope.pdf [2] L. Babai, Timeline of a correspondence. http://people.cs.uchicago.edu∼laci/polytope-correspondence.pdf [3] S. Friedland, Graph isomorphism is Polynomial. http://arxiv.org/PS cache/arxiv/pdf/0801/0801.0398v1.pdf 4 [4] S. Friedland, On the graph isomorphism problem. http://arxiv.org/PS cache/arxiv/pdf/0801/0801.0398v2.pdf [5] S. Onn, Two graph isomorphism polytopes. http://arxiv.org/abs/0801.1410 5