7
$\begingroup$

Consider the complete graph on $2n$ vertices, where the ${2n \choose 2}$ edges have distinct lengths in uniform random order. So each vertex $v$ has a nearest neighbor $N(v)$, across the shortest edge at $v$. Let $p(n)$ be the probability that every vertex is its nearest neighbor's nearest neighbor: $v = N(N(v))$ for all $v$. I can give a "probability" proof that

$ p(n) = (2n-1)!! \times (2n-3)!!/ (4n-3)!! $ where (2n-1)!! = (2n-1)(2n-3)(2n-5) .... 3 .

It seems likely this question has been studied before. Is there a reference? Is there a simple "combinatorics" proof?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Not sure about the reference, but the "probability proof" is already nearly trivial. Just notice that you can run your assignment step by step, at each step either placing some particular weighted edge between a uniformly chosen random pair of not yet joined vertices, or putting a uniformly chosen random remaining edge between a fixed pair of not yet joined vertices (which option to choose is entirely up to you at each step and you can even make your choice between the two depending on what has been constructed already). Now observe that after placing the shortest edge, you should place the second shortest one disjointly. Then you can fill the rest of the four vertex graph in whatever way, but after that the shortest remaining edge has to be placed disjointly with the first two. Then you fill the 6 vertex graph, after which the shortest remaining edge has to be placed disjointly with the first three, and so on. This immediately leads to the formula $$ p(n)=\prod_{k=1}^{n-1}\frac{{2n-2k\choose 2}}{{2n-2k\choose 2}+2k(2n-2k)}\,, $$ which after simple algebraic manipulations turns into your expression.

Probably, this is equivalent to what you know yourself, but I'm a bit perplexed about why you would want anything simpler or different.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. Yes, it's basically the same argument, although with your style of verbal arguments I worry that it's possible to make mistakes about the effects of conditioning, as I know from experience. Re "wanting something different", my thought was that (2n-1)!! also counts other structures such as leaf-labelled binary trees, so maybe there is some interesting bijection with a statement about trees. See e.g. Diaconis-Holmes "Matchings and phylogenetic trees" (1988). $\endgroup$
    – David Aldous
    Commented Nov 25, 2023 at 5:42
  • $\begingroup$ based off this answer, isn’t the problem equivalent to showing that the fraction of labelled graphs with $n$ edges and $2n$ vertices that are matchings is the appropriate ratio of double factorials? its not hard to see that $(2n)!!$ counts the number of perfect matchings on $K_{2n}$, so presumably one could do something with that. $\endgroup$
    – Zach Hunter
    Commented Nov 28, 2023 at 6:53

You must log in to answer this question.

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