# algorithmic almost equitable partitioning

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$.

• Please don't go creating new tags that we don't need. I've retagged, and hopefully "almost-equitable-partit" and "equitable-partitions" (as opposed to the singular form) won't appear again – David White Feb 19 '13 at 19:18
• Ok, sorry, the plural was just a typo. But concerning the almost-equitable tag: I do think that a.e. partitions are something definitely different and more general than equitable ones: if the question is focused on them, why not having a tag for them. – Delio Mugnolo Feb 19 '13 at 19:31
• Two meta comments: I agree that too many tags are not good (in principle the plural is the default, but to have both versions is definitely not a good idea, one can ask on meta if one would like to have something pluralized). I have no specific knowledge regarding the math objects in question but IMO a good question to ask (in part. if there are only very few question to begin with is): is there any reasonable chance there is some mathematician that would look at a question tagged almost equ-part yet not one equ-part. If the answer is 'yes' create the tag, if 'no' then rather not. Or... – user9072 Feb 19 '13 at 19:40
• ...since the one seems to be more general one might consider renaming/generalizing the existing tag to the almost version. (Again ask on the relevant sticky thread on meta.) To put this differently, the main point of the tag is IMO not to have a precise indication of the question now (now we all see the title anyway containing almost equitable) yet for somebody to perhaps find the question in months via looking for specifically tagged questions for example. Sorry for the longish meta comment. If you prefer, let me know and I delete them. – user9072 Feb 19 '13 at 19:44
• Corresponding questions for equitable partitions were asked at mathoverflow.net/questions/96858/… and not answered successfully. About this question, I assume that the usual refinement procedure for finding the coarsest equitable partition finer than a given partition works also when adapted to almost-equitable. So problems like finding a non-trivial a-e partition with a singleton cell are polynomial. The general case is unclear though. – Brendan McKay Feb 20 '13 at 1:01

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.

• You are of course right, I edited the entry and added the correct definition. – Delio Mugnolo Feb 20 '13 at 7:04