论文标题
混乱的比赛：证明和猜想
Deranged matchings: proofs and conjectures
论文作者
论文摘要
我们引入并部分解决了一种猜想，它带来了一个三世纪的毁灭现象及其在同一伞下的较年轻的两个年轻的类似物。通过图理论镜头，Distangement是完整的两部分图中的完美匹配$ K_ {N，N} $，并删除了不连接的完美匹配$ M $。同样，一个精神错乱的匹配是完整图中的完美匹配$ k_ {2n} $减去完美的匹配$ m'$。使用$ \ mathrm {pm}（\ cdot）$计数完美的匹配，老年现象采取了$ \ mathrm {pm {pm}（k_ {n，n} -m）/\ mathrm {pm {pm {pm}（k_ {n，n，n}）\至1/e $ n \ as $ n \ farty Applugo， $ \ mathrm {pm}（k_ {2n} -m'）/\ mathrm {pm}（k_ {2n}）\至1/\ sqrt {e} $。这些启动图都是$ 2N $ -VERTEX`平衡完整$ r $ -partite'图$ k_ {r \ times {2n}/{r}} $，$ r = 2 $和$ r = 2n $。我们猜测$ \ mathrm {pm}（k_ {r \ times {2n}/r} -m）/\ mathrm {pm {pm}（k_ {r \ times {2n}/r}/r}/r}）仅两个示例，$ r = 3 $产生限制$ e^{ - 3/4} $，而$ r = n $ resuct又在$ e^{ - 1/2} $中再次产生。我们的工具在结合包容性排斥和制革厂定理的混合泳中混合组合和分析。
We introduce, and partially resolve, a conjecture that brings a three-centuries-old derangements phenomenon and its much younger two-decades-old analogue under the same umbrella. Through a graph-theoretic lens, a derangement is a perfect matching in the complete bipartite graph $K_{n,n}$ with a disjoint perfect matching $M$ removed. Likewise, a deranged matching is a perfect matching in the complete graph $K_{2n}$ minus a perfect matching $M'$. With $\mathrm{pm}(\cdot)$ counting perfect matchings, the elder phenomenon takes the form $\mathrm{pm}(K_{n,n}-M)/\mathrm{pm}(K_{n,n})\to 1/e$ as $n\to\infty$ while its youthful analogue is $\mathrm{pm}(K_{2n}-M')/\mathrm{pm}(K_{2n})\to 1/\sqrt{e}$. These starting graphs are both $2n$-vertex `balanced complete $r$-partite' graphs $K_{r \times {2n}/{r}}$, respectively with $r=2$ and $r=2n$. We conjecture that $\mathrm{pm}(K_{r\times{2n}/r}-M)/\mathrm{pm}(K_{r\times{2n}/r})\sim e^{-r/(2r-2)}$ as $n\to\infty$ and establish several substantive special cases thereof. For just two examples, $r=3$ yields the limit $e^{-3/4}$ while $r=n$ results again in $e^{-1/2}$. Our tools blend combinatorics and analysis in a medley incorporating Inclusion-Exclusion and Tannery's Theorem.
