Complexity of equitable partitions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T04:40:15Z http://mathoverflow.net/feeds/question/96858 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/96858/complexity-of-equitable-partitions Complexity of equitable partitions Brendan McKay 2012-05-13T23:34:27Z 2012-05-30T10:22:00Z <p>We are talking about undirected simple graphs and <em>partitions</em> of their vertex sets into disjoint non-empty <em>cells</em>. Such a partition is <em>equitable</em> if for any two vertices $v,w$ in the same cell, and any cell $C$, it holds that $v,w$ have the same number of neighbours in $C$. The <em>trivial</em> partition (with only one vertex per cell) is always equitable.</p> <p>Given any partition $\pi$, there is a unique coarsest equitable partition $\bar\pi$ finer than $\pi$. (The concepts <em>finer</em> and <em>coarser</em> include equality). This is a very old result, as also are polynomial-time algorithms for computing $\bar\pi$ from $\pi$.</p> <p>Another fact is that it is NP-complete to determine if a graph has an equitable partition with every cell of size 2. (This follows from Lubiw, SIAM J Comput 10, 1981, 11–21 on noting that such a partition corresponds to a fixed-point-free automorphism of order 2.)</p> <p>My question is: <strong>what else?</strong> Are any other complexity results known? In particular:</p> <ol> <li>What is the complexity of: Given a regular graph, does it have any non-trivial equitable partition other than the partition with just one cell?</li> <li>What is the complexity of: Given a regular graph, does it have an equitable partition with exactly two cells?</li> <li>What is the complexity of: Given a graph and two vertices $v,w$, is there a non-trivial equitable partition which has $v,w$ in different cells?</li> <li>Is there any problem on equitable partitions with complexity equal to graph isomorphism?</li> </ol> http://mathoverflow.net/questions/96858/complexity-of-equitable-partitions/96862#96862 Answer by Joseph O'Rourke for Complexity of equitable partitions Joseph O'Rourke 2012-05-14T01:04:17Z 2012-05-14T01:48:17Z <p><br />&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/Equipartition.jpg" alt="2-partitions"><br /> Concerning <em>Question 1</em>, it seems that partitioning a hypercube into two diagonally crossing sets is an equipartition: in the two examples shown, each blue vertex has two neighbors in the purple set, and vice versa. This continues to hold for $d$-dimensional hypercubes, providing an example of a $d$-regular graph with a 2-equipartition.</p> http://mathoverflow.net/questions/96858/complexity-of-equitable-partitions/97103#97103 Answer by Aaron Meyerowitz for Complexity of equitable partitions Aaron Meyerowitz 2012-05-16T09:24:26Z 2012-05-16T09:24:26Z <p>More a comment than an answer. I have (as suggested) asked a <a href="http://mathoverflow.net/questions/97098/" rel="nofollow">related question</a> which is essentially about the complexity of determining if a certain eigenspace has a member with two distinct entries.</p> <p>Related to this question, here is an astonishingly vague sketch of a possible type of approach for an attempted construction of a potentially difficult example for question 2: Start with a connected bipartite graph $H$ which has $2m$ vertices $v_1 \cdots v_{2m}$ all of degree $d$ (so the two halves each have $m$ vertices) but is otherwise fairly irregular. Also generate $2m$ graphs $G_1 \cdots G_{2m}$ each with $n$ vertices, regular of degree $d^*$ and all having $0$ as an eigenvalue of reasonably high multiplicity but without any very simple eigenvectors. Now make them into a big graph $\mathcal{G}$ with $2mn$ vertices by putting in all $n^2$ edges connecting $G_i$ and $G_j$ whenever $v_iv_j$ is an edge of $H.$ There will be an enormous number of fairly complicated eigenvectors of $\mathcal{G}$ obtained by picking an arbitrary eigenvector of $0$ for each of the $G_i.$ There will also be an eigenvector which is $1$ on half the vertices and $-1$ on the other half (respecting the bipartition of $H$.) Now if the graph is just presented as a huge adjacency matrix with vertices in a very scrambled order then it will be clear that $0$ is an eignevalue of high multiplicity and our favorite program will present us a basis for the corresponding eigenspace, but it may not be obvious how to find that special eigenvector.</p> <p>Left unspecified is how to pick good values for $m,n,d,d^*$ Perhaps there is a simple flaw in this description, maybe too many easy to find $0,1,-1$ eigenvectors. In that case I say that that was only a sketch. In some other way build in an equitable (two cell) partition overlaid with lots of noise.</p>