algorithmic almost equitable partitioning

Question

Let $G$ be a graph -- possibly infinite, but I will be glad to learn a positive result even in the finite case. Then the trivial partition (i.e., one cell coinciding with the whole $G$) is clearly almost equitable (a definition can be found here, for example), but this is of course very coarse. Another trivial almost equitable partition is instead much too fine: it is the partition consisting of singletons only - this is indeed even equitable.

My question: Is there any way of algorithmically constructing further (non trivial) almost equitable partitions -- that is, almost equitable partitions with a larger number of smaller cells, but not too small? Or almost equitable partitions with a smaller number of larger cells, but not too large?

EDIT: As Aaron Meyerowitz suggests in the comments, the mathoverflow entry linked above does in fact call almost equitable what is usually called equitable. So, let me for reference write down here what is the correct definition, even in the general case of a weighted graph: Let $G$ be a (possibly infinite) graph with node set $V$, where each edge $e=(v,w)$ has a weight $\mu_{vw}\in (0,\infty)$ and each node $v$ has a weight $\nu_v\in (0,\infty)$. Given a subset $W\subset V$ and a $v\in V$, one denotes by $d_W(v)$ the weighted degree of $v$ in $W$, i.e., $$ d_W(v):=\frac{1}{\nu_v} \sum_{w\in V \hbox{ s.t. }w\sim v} \mu_{vw}. $$ Then, a (possibly infinite) partition $(V_i)_{i\in I}$ of $V$ is called almost equitable if for all $i,j\in I$, $i\neq j$, there is a number $c_{ij}$ such that $d_{V_j}(v)=c_{ij}$ for all $v\in V_i$.

Answer 1

The definition to which you link says

$\forall i,j\in\{1,\ldots,k\}$ $\forall v, u\in V_i$ $|N(v)\cap V_j|=|N(u)\cap V_j|$, i. e. that the number of neighbors of a node $v$ in $V_i$ in the component $V_j$ does not depend on the choice of $v$.

Am I correct that that is the definition of equitable whereas almost-equitable restricts to $i \ne j$?

You might check out Partitions in matrices and graphs MR1104819

by Hughes, D. R. and Singhi, N. M. European J. Combin v 12 (1991) number 3 pages 223-235

I know it aims to be very general and as I recall, it had algorithmic aspects. But I read it a long time ago. Here is an idea which I think I might recall from that paper (but I could be totally wrong):

If you have a potential cell $C$ of a partition then you can take the corresponding characteristic vector $\mathbf{v}$ and multiply it by the Laplacian matrix once (or several times) obtaining $\mathbf{w}$. Define $i \sim j$ if $\mathbf{w}_i=\mathbf{w}_j.$ Then I think that the following is true: Any almost equitable partition having $C$ as a cell is a refinement of this partition (so the vertices of $C$ had better be equivalent under $\sim$.)

This also works if $C$ is a union of several cells (then $C$ need not be part of an equivalence class under $\sim$ so you could take each of the parts into which it was split and use them as $\mathbf{v}$). So if you are looking for fully equitable partitions ($i=j$ also required) and happen to have several degrees in the graph and then you could start with the characteristic vector of each degree class, try the procedure above to get several partitions and then restrict your attention to common refinements. I'm not sure how to adapt that to the almost equitable setting.

I'm not sure how an infinite graph would be presented and how one would check a potential partition. Perhaps the mode of presentation would give some clues.