<p>Fix any algorithm that works for integer edge weights, and treats the weights as black boxes that can be copied, added, subtracted, and compared, but cannot be accessed in any other way. Furthermore, assume that the algorithm terminates in time bounded by a function <span class="math-container">$t(n)$</span> of the number of vertices of the graph, independent of the weights. We may assume the input graph is the complete graph, with missing edges represented by <span class="math-container">$0$</span> weights.</p>
<p>I claim that such an algorithm also works for weights valued in arbitrary (totally) ordered abelian groups. This follows from the following two observations.</p>
<blockquote>
<p><strong>Lemma 1:</strong> For any <span class="math-container">$n$</span>, the soundness of the algorithm on graphs of order <span class="math-container">$n$</span> can be expressed by a universal first-order sentence in the language of ordered groups.</p>
</blockquote>
<p><strong>Proof:</strong> For fixed <span class="math-container">$n$</span>, the computation of the algorithm can be described by a tree that branches whenever two black boxes are compared; at each node of the tree, the content of each black box is given by a linear function of the input weights <span class="math-container">$\{x_{i,j}:i,j\in[n]\}$</span> with integer coefficients. If <span class="math-container">$\{\ell_t:t\in[m]\}$</span> is an enumeration of leaves of the tree, let <span class="math-container">$\theta_t(\vec x)$</span> denote the conjunction of the linear inequalities or their negations that determine the path leading to <span class="math-container">$\ell_t$</span>, and let <span class="math-container">$M_t$</span> denote (the set of edges of) the matching that’s output at <span class="math-container">$\ell_t$</span>. Then <span class="math-container">$\bigvee_{t\in[m]}\theta_t(\vec x)$</span> is a tautology, and the soundness of the algorithm is expressed by the universal sentence
<span class="math-container">$$\forall\vec x\:\bigwedge_{t\in[m]}\bigwedge_M\Bigl(\theta_t(\vec x)\to\sum_{\{i,j\}\in M_t}x_{i,j}\ge\sum_{\{i,j\}\in M}x_{i,j}\Bigr),$$</span>
where <span class="math-container">$M$</span> runs over all (finitely many) matchings on <span class="math-container">$[n]$</span>.</p>
<blockquote>
<p><strong>Lemma 2:</strong> Every universal sentence true in <span class="math-container">$(\mathbb Z,+,\le)$</span> holds in all ordered abelian groups.</p>
</blockquote>
<p><strong>Proof:</strong>
An ordered abelian group <span class="math-container">$(G,+,\le)$</span> embeds in its divisible hull <span class="math-container">$G\otimes_\mathbb Z\mathbb Q$</span> (which carries a unique order <span class="math-container">$\le'$</span> extending <span class="math-container">$\le$</span> that makes it an ordered group, namely <span class="math-container">$x\le'y\iff nx\le ny$</span> for some/all <span class="math-container">$n\in\mathbb N_{&gt;0}$</span> such that <span class="math-container">$nx,ny\in G$</span>). This in turn embeds in <span class="math-container">$(G\otimes_\mathbb Z\mathbb Q)\oplus\mathbb Z$</span>, ordered lexicographically so that <span class="math-container">$\mathbb Z$</span> is a convex subgroup. Being an extension of a divisible ordered abelian group by <span class="math-container">$\mathbb Z$</span>, this is a <span class="math-container">$\mathbb Z$</span>-group, thus it is elementarily equivalent to <span class="math-container">$\mathbb Z$</span>. It follows that any universal sentence true in <span class="math-container">$\mathbb Z$</span> is true in <span class="math-container">$(G\otimes_\mathbb Z\mathbb Q)\oplus\mathbb Z$</span>, and therefore in <span class="math-container">$G$</span>.</p>
<p>Alternatively, every nontrivial finitely generated subgroup of <span class="math-container">$\mathbb Q$</span> is isomorphic to <span class="math-container">$\mathbb Z$</span>, thus a universal sentence true in <span class="math-container">$(\mathbb Z,+,\le)$</span> is also true in <span class="math-container">$(\mathbb Q,+,\le)$</span>. It follows that it is true in all divisible ordered abelian groups such as <span class="math-container">$G\otimes_\mathbb Z\mathbb Q$</span>, and consequently in <span class="math-container">$G$</span>.</p>
<p>(The first argument relies on completeness of the theory of <span class="math-container">$\mathbb Z$</span>-groups, aka Presburger arithmetic; the second argument on completeness of the theory of nontrivial divisible ordered abelian groups.)</p>
<p>A final note: the statements above apply to ordered abelian groups that are <em>sets</em>, whereas the question asks for surreal numbers, which form a proper class. But this is of no consequence: we can just look at the subgroup of the surreals generated by the (finitely many) weights of the given graph, which is a countable set.</p>

CC BY-SA 4.0
2023-01-18T10:40:14.180Z
2023-01-18T10:40:14.180Z
Emil Jeřábek
<blockquote>
<p>Is there an efficient algorithm for finding a maximum weight matching in a graph where the weight of each edge is a <a href="https://en.wikipedia.org/wiki/Surreal_number" rel="nofollow noreferrer">surreal number</a>?</p>
</blockquote>
<p>I strongly remember thinking about this problem about 20 years ago, but I don't remember any conclusion.<br />
On one hand, I think that algorithms (like Edmonds's) should work for surreal numbers as well--this might follow from standard methods in nonstandard analysis.<br />
On the other, this would solve finding maximum weight maximum cardinality matchings, which is claimed to be open in <a href="https://doi.org/10.1007/s11786-007-0028-0" rel="nofollow noreferrer">this paper</a>. Added: Seems like this should not be open, see the comment by Neal.</p>

CC BY-SA 4.0
2023-01-17T02:02:27.260Z
(1) Are you asking whether there is an *efficient algorithm* for the problem, or just whether such a max-weight matching always exists?  If the former, how is the input encoded?  (2) I'm confused by the assertion that it is not known how to find (presumably in poly time) a matching of maximum weight among matchings of maximum cardinality.  Surely this can be done by asking for a max-weight matching in the graph with an appropriate encoding of the edge weights (e.g. give edge $e$ weight $1+\epsilon w_e$ for positive $\epsilon \ll 1/\sum_e w_e$)?  What am I missing?
Neal Young
CC BY-SA 4.0
2023-01-17T05:34:13.047Z
(1) Yes, and I hope I won't have to define the encoding. I assume addition/subtraction, comparison are allowed, like on a real RAM machine. (2) I was also confused by the very same thing, my essentially same construction was adding $\sum w_i$ to the weight of each edge. Then I assume this problem is not so open, though there are several references to it online: https://www.google.com/search?q=%22Maximum+weight+maximum+cardinality+matching%22&oq=%22maximum+weight+maximum+cardinality+matching%22
domotorp
CC BY-SA 4.0
2023-01-17T07:59:56.467Z
@Emil Yes, I also think so, thank you for confirming it. Do you maybe have a reference for this?
domotorp
CC BY-SA 4.0
2023-01-17T15:57:04.697Z
@Emil: Would you put together these comments into an answer that I can accept and cite?
domotorp
<matching>
Maximum weight matching with surreal weights
domotorp
# Maximum weight matching with surreal weights

(Asked by: username_0 on 2023-01-16)

> Is there an efficient algorithm for finding a maximum weight matching in a graph where the weight of each edge is a [surreal number](https://en.wikipedia.org/wiki/Surreal_number)?

I strongly remember thinking about this problem about 20 years ago, but I don't remember any conclusion.  
On one hand, I think that algorithms (like Edmonds's) should work for surreal numbers as well--this might follow from standard methods in nonstandard analysis.  
On the other, this would solve finding maximum weight maximum cardinality matchings, which is claimed to be open in [this paper](https://doi.org/10.1007/s11786-007-0028-0). Added: Seems like this should not be open, see the comment by Neal.

**Tags:** matching
> **Comments:**
> **username_1**: (1) Are you asking whether there is an *efficient algorithm* for the problem, or just whether such a max-weight matching always exists?  If the former, how is the input encoded?  (2) I'm confused by the assertion that it is not known how to find (presumably in poly time) a matching of maximum weight among matchings of maximum cardinality.  Surely this can be done by asking for a max-weight matching in the graph with an appropriate encoding of the edge weights (e.g. give edge $e$ weight $1+\epsilon w_e$ for positive $\epsilon \ll 1/\sum_e w_e$)?  What am I missing?  
> **username_0**: (1) Yes, and I hope I won't have to define the encoding. I assume addition/subtraction, comparison are allowed, like on a real RAM machine. (2) I was also confused by the very same thing, my essentially same construction was adding $\sum w_i$ to the weight of each edge. Then I assume this problem is not so open, though there are several references to it online: https://www.google.com/search?q=%22Maximum+weight+maximum+cardinality+matching%22&oq=%22maximum+weight+maximum+cardinality+matching%22  
> **username_0**: @Emil Yes, I also think so, thank you for confirming it. Do you maybe have a reference for this?  
> **username_0**: @Emil: Would you put together these comments into an answer that I can accept and cite?  

---

## 1 answers

### Answer by username_2 on 2023-01-18. Score: 2 | Accepted answer

Fix any algorithm that works for integer edge weights, and treats the weights as black boxes that can be copied, added, subtracted, and compared, but cannot be accessed in any other way. Furthermore, assume that the algorithm terminates in time bounded by a function $t(n)$ of the number of vertices of the graph, independent of the weights. We may assume the input graph is the complete graph, with missing edges represented by $0$ weights.

I claim that such an algorithm also works for weights valued in arbitrary (totally) ordered abelian groups. This follows from the following two observations.

> **Lemma 1:** For any $n$, the soundness of the algorithm on graphs of order $n$ can be expressed by a universal first-order sentence in the language of ordered groups.

**Proof:** For fixed $n$, the computation of the algorithm can be described by a tree that branches whenever two black boxes are compared; at each node of the tree, the content of each black box is given by a linear function of the input weights $\{x\_{i,j}:i,j\in[n]\}$ with integer coefficients. If $\{\ell\_t:t\in[m]\}$ is an enumeration of leaves of the tree, let $\theta\_t(\vec x)$ denote the conjunction of the linear inequalities or their negations that determine the path leading to $\ell\_t$, and let $M\_t$ denote (the set of edges of) the matching that’s output at $\ell\_t$. Then $\bigvee\_{t\in[m]}\theta\_t(\vec x)$ is a tautology, and the soundness of the algorithm is expressed by the universal sentence
$$\forall\vec x\:\bigwedge\_{t\in[m]}\bigwedge\_M\Bigl(\theta\_t(\vec x)\to\sum\_{\{i,j\}\in M\_t}x\_{i,j}\ge\sum\_{\{i,j\}\in M}x\_{i,j}\Bigr),$$
where $M$ runs over all (finitely many) matchings on $[n]$.

> **Lemma 2:** Every universal sentence true in $(\mathbb Z,+,\le)$ holds in all ordered abelian groups.

**Proof:**
An ordered abelian group $(G,+,\le)$ embeds in its divisible hull $G\otimes\_\mathbb Z\mathbb Q$ (which carries a unique order $\le'$ extending $\le$ that makes it an ordered group, namely $x\le'y\iff nx\le ny$ for some/all $n\in\mathbb N\_{>0}$ such that $nx,ny\in G$). This in turn embeds in $(G\otimes\_\mathbb Z\mathbb Q)\oplus\mathbb Z$, ordered lexicographically so that $\mathbb Z$ is a convex subgroup. Being an extension of a divisible ordered abelian group by $\mathbb Z$, this is a $\mathbb Z$-group, thus it is elementarily equivalent to $\mathbb Z$. It follows that any universal sentence true in $\mathbb Z$ is true in $(G\otimes\_\mathbb Z\mathbb Q)\oplus\mathbb Z$, and therefore in $G$.

Alternatively, every nontrivial finitely generated subgroup of $\mathbb Q$ is isomorphic to $\mathbb Z$, thus a universal sentence true in $(\mathbb Z,+,\le)$ is also true in $(\mathbb Q,+,\le)$. It follows that it is true in all divisible ordered abelian groups such as $G\otimes\_\mathbb Z\mathbb Q$, and consequently in $G$.

(The first argument relies on completeness of the theory of $\mathbb Z$-groups, aka Presburger arithmetic; the second argument on completeness of the theory of nontrivial divisible ordered abelian groups.)

A final note: the statements above apply to ordered abelian groups that are *sets*, whereas the question asks for surreal numbers, which form a proper class. But this is of no consequence: we can just look at the subgroup of the surreals generated by the (finitely many) weights of the given graph, which is a countable set.


---

