1
$\begingroup$

A complete symmetric graph with $n=4$ vertices, i.e. a $K_4$ is the disjoint union of three perfect matchings $M_{\text{min}},M_{\text{mid}},M_{\text{max}}$ of which $M_{\text{min}}$ denotes the lightest and $M_{\text{max}}$ the heaviest.

If we denote by $e_{\text{min}}$ and $e_{\text{max}}$ the lightest, resp. heaviest edge, then we have, assuming uniqueness of matching-weights and edge-weights the following peculiar duality:
$$ e_{\text{min}} \in M_{\text{max}}\implies e_{\text{max}} \in M_{\text{max}} \\ e_{\text{max}} \in M_{\text{min}}\implies e_{\text{min}} \in M_{\text{min}}$$

Questions:

  • has this "duality" been noticed before?
  • do analogous dualities appear elsewhere im mathematics?
  • does existence of these dualities have non-trivial implications?
Improve this question
$\endgroup$
14
  • 2
    $\begingroup$ What weights do you put on edges and matchings? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Aug 31, 2021 at 6:57
  • 3
    $\begingroup$ Doesn't this duality apply to any set of numbers, partitioned into pairs, when you look at the minimum and maximum elements and the minimum and maximum sums of pairs? $\endgroup$
    – Will Sawin
    Commented Aug 31, 2021 at 12:07
  • 6
    $\begingroup$ I would say it's a trivial fact and it needs (brief) checking to see it: If the smallest number $a$ forms part of the maximum sum of two numbers $a+b$ then for any pair of numbers $c,d$ we have $a+b \geq c+d$ and $a \leq c$ so $b\geq d$. Because this works for any $d$, $b$ is the maximum number. $\endgroup$
    – Will Sawin
    Commented Aug 31, 2021 at 13:04
  • 2
    $\begingroup$ It was pretty obvious to me but not literally immediate. I don't know how obvious it would be to someone else. $\endgroup$
    – Will Sawin
    Commented Aug 31, 2021 at 13:15
  • 11
    $\begingroup$ It felt obvious to me once I rephrased in terms of money. If each of $n$ people has two coins and the person with the least valuable coin is nevertheless the richest, then that person must also have the most valuable coin. $\endgroup$
    – Timothy Chow
    Commented Sep 1, 2021 at 20:50

1 Answer 1

Reset to default
1
$\begingroup$

This should rather be a comment, posting it as an answer is to give a visual clue that there is something in the vein of a proof.

Elaborating on Timothy Chow's insightful comment it suffices to consider a single pair of people, $A.$ and $B.$ of which $A.$ has the two coins $a_0$ and $a_1,\ a_0\le a_1$ of smaller value; likewise $B.$'s coins are $b_0$ and $b_1,\ b_0\le b_1;\quad a_0+a_1\lt b_0+b_1$.

Under the assumption that $a_1\gt b_1$ we have:
\begin{align*} & a_0+a_1=b_0+b_1-\Delta,\quad 0\lt\Delta\lt b_0+b_1 \\ & a_0\ =\ b_0+b_1-\Delta-a_1\ <\ b_0+b_1-\Delta-b_1\ =\ b_0-\Delta\quad\implies\quad a_0+\Delta\lt b_0 \end{align*} which proves that the assumption implies that the smaller coin of the smaller amount must be less than the smaller coin of the larger value.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Another way to say it is that if $A$ has the least valuable coin $a_0$ and $B$ has the most valuable coin $b_1$, then $B$ must be richer than $A$ since $a_0\le b_0$ (by minimality of $a_0$) and $a_1\le b_1$ (by maximality of $b_1$). So if $A$ is the richest then $A=B$. I'm being a little sloppy with $<$ versus $\le$ but you get the idea. This may be a case where the contrapositive is more intuitive than the direct statement: If $A$ doesn't have the most valuable coin then someone else (namely, the person with the most valuable coin) must be richer. $\endgroup$
    – Timothy Chow
    Commented Sep 4, 2021 at 14:02
  • $\begingroup$ @TimothyChow these observations seem so basic that I can imagine they may become useful in proofs; it is almost as obvious as the pigeon hole principle and knowing about it may shorten some proofs. $\endgroup$
    – Manfred Weis
    Commented Sep 4, 2021 at 14:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .