Assume integers $d > r > 0$ and a connected graph $G$ with $d$ vertices. Every point on the $r$-fold Cartesian product of $G$ with itself, $G^{\square r}$, is equivalent to a dimension-$d$ non-negative integer vector whose entries total to $r$. Assume some linear constraints on these dimension-$d$ vectors; we will say that vertex of $G^{\square r}$ is allowed if its corresponding non-negative integer vector satisfies those linear constraints. Given allowed vertices $x$ and $y$, I would like to know if a path exists between them in $G^{\square r}$ such that every vertex on that path is allowed.

Said another way, each cardinality-$r$ multiset of vertices on $G$ is equivalent to a dimension-$d$ non-negative integer vector whose entries total to $r$. Given two such cardinality-$d$ multisets whose corresponding indicator vectors satisfy some linear constraints, find a sequence of such cardinality-$d$ multisets such that

  • neighboring multisets in the sequence differ by a move of one element of the multiset along an edge of $G$
  • the corresponding non-negative integer vectors satisfy the linear constraints.

If it helps, the linear constraints are of the following form. Assume $c > 0$, a $c \times d$ binary matrix $C$, and a dimension-$c$ positive integer vector $m$. Our linear constraints on a non-negative vector $s$ with total $r$ are that $Cs < m$ and that $s$ is binary.

Somehow it seems that we would be slicing off subsets of the Cartesian product with our linear constraints, but I can't see how we would get the graph structure to talk to the linear constraints. In the long run, we would like to have an algorithm to find the minimal path between points, but deciding existence would be a huge help.

Thank you for your help.

  • $\begingroup$ Here are some partial restatements to check I'm understanding correctly. Since $s$ is binary, the multiset of vertices occupied is actually a set, and the $i$th row of $C$ ensures that at most $m_i$ of the vertices in the set $C_i$ are occcupied. Am I right in thinking that there is no unique way of passing between a given configuration of this sort on $G$ and a vertex of $G^{\square r}$? $\endgroup$ – Ben Barber Jun 20 '14 at 15:56
  • $\begingroup$ You are right on both counts. For the first statement, I thought it would be easier to find previous work if I went with a more general statement. For the second, you make a great point-- the vertices of $G^{\square r}$ are ordered, whereas our point configurations do not have to be. However, in both counts an answer to the problem as stated will give an answer to the more specific problem we care about.Do you think that it would be better to edit to make it more specific? Thanks, @BenBarber. $\endgroup$ – ematsen Jun 20 '14 at 17:12
  • $\begingroup$ To expand on my previous note, we would actually like to be able to say things about the symmetric power of $G$ (the question concerning cospectrality in that paper is answered in this paper. It wouldn't be a big problem for us if we had to try every ordering of the points, but actually solving the symmetric product case would be ideal. $\endgroup$ – ematsen Jun 20 '14 at 18:05

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.