5
$\begingroup$

Let $G = (Q, \Delta, W)$ be a finite weighted graph with $\Delta: Q \times Q$ and $W: Q \times Q \to \mathbb{R}^{+}$. Is it the case that there always exist a function $W': Q \times Q \to \mathbb{Q}^{+}$ such that $\forall S, S' \subseteq Q, \forall s, s' \in S$:

$$ \sum_{s'' \in S'}{W(s, s'')} = \sum_{s'' \in S'}{W(s', s'')} \Leftrightarrow \sum_{s'' \in S'}{W'(s, s'')} = \sum_{s'' \in S'}{W'(s', s'')} $$

?

I believe, at least for the finite case, this should be possible and I'm trying to prove this "constructively" by finding $W'$.

So let $\epsilon \in \mathbb{Q}^{+}$ be a rational such that $\forall s_0,s_1,s_2,s_3 \in Q, \epsilon < |W(s_0, s_1) - W(s_2, s_3)|$ whenever that difference isn't $0$.

Obviously if we just round every non-rational weight in a grid with spacing $\epsilon$ we will not preserve equalities and I believe it'll be quite difficult to restore the exact relations.

So my idea is to round one weight at a time, and then fix the equalities that get broken by modifying only non-rational weights and repeating the process until there are only rational weights.

So start by taking two subsets $S, S' \subseteq Q$ and take $s \in S$ and $s'' \in S'$ such that $W(s, s'') \notin \mathbb{Q}$. Now we can round this number to the nearest rational of the form $k\cdot \epsilon$.

Let $e = W(s, s'') - W'(s, s'')$ is the error we introduced. Now if there was an $s' \in S$ and an $s'''$ such that $W(s', s''') = W(s, s'')$ then we modify that weight in the same manner, and thus the iff condition still holds for $s$ and $s'$.

Otherwise for $s' \in S$ we must have that some (more than one) weight $W(s', s''') \notin \mathbb{Q}$ and we can subtract $e$ from it and preserve the condition for $s$ and $s'$ with respect to $S$ and $S'$.

However we have now changed some other weight, and thus while we may have preserved the equality between $S$ and $S'$, we may have broken it for other subsets. So we have to consider every subset that is either a subset or superset of $S$ and $S'$, verify if we have broken that iff condition, and if so we must find an other weight and change it, and repeat the process until it we find an equilibrium. But does this actually happen?

My question is:

  1. Does there exist such $W'$ or am I trying to build a non-existent function?
  2. If $W'$ exists, is the above approach feasible in some way, or should I completely change strategy in order to find $W'$? Do you know any particular trick that can help in devising $W'$?
$\endgroup$
3
  • $\begingroup$ Use a Hamel basis. $\endgroup$ Commented Apr 10, 2016 at 10:04
  • $\begingroup$ What is $\Delta$? ​ ​ $\endgroup$
    – user12859
    Commented Apr 10, 2016 at 10:37
  • $\begingroup$ @RickyDemer The edge relationship. There is an edge between $s, s' \in Q$ iff $(s, s') \in \Delta$. $\endgroup$
    – Bakuriu
    Commented Apr 10, 2016 at 11:20

1 Answer 1

3
$\begingroup$

Identify $W$ with the set of all weights. Let $B$ be a basis of $W$ over the rationals. That is, you can write every weight in $w$ as a linear combination of elements of $B$ with rational coefficients. You can identify the weights with vectors $\vec{w}$ of length $|B|$. Each linear dependency that you want to avoid can be thus encoded as an inequality $$ \sum_i \alpha_i b_i \neq 0, $$ where the coefficients $\alpha_i$ are not all zero. We can moreover assume that the $\alpha_i$ are integers (by taking a common denominator).

Let $M$ be an integer larger than all $|\alpha_i|$ appearing in an inequality you are interested in. If we replace $b_i$ with $M^i$ then all the requisite inequalities will be satisfied, while all equalities will also be preserved.

$\endgroup$
3
  • $\begingroup$ Cute! Probably useful to note that finding $B$ isn't really constructive (imagine $W=\{1,\pi, e, \pi+e\}$) but those seem like pretty silly weights to put on a graph anyways. $\endgroup$
    – cody
    Commented Apr 12, 2016 at 20:01
  • $\begingroup$ So $W'$ would become something like $W'(s, s') = \sum_{i}{\alpha_i M^i}$? Also is there a more constructive solution? For example: assume you have an oracle that tells you whether a weight $w$ belongs to $\mathbb{Q}$ or not. Is that enough to obtain an algorithm that computes $B$ as in your answer or for finding a different solution? $\endgroup$
    – Bakuriu
    Commented Apr 15, 2016 at 6:47
  • $\begingroup$ @Bakuriu For a constructive solution you need a way to find all linear dependencies. What you wrote isn't enough. $\endgroup$ Commented Apr 15, 2016 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.