论文标题
大图的上层匹配猜想的证明
A proof of the Upper Matching Conjecture for large graphs
论文作者
论文摘要
我们证明，弗里德兰，克罗普和马克斯特姆的“上匹配猜想”以及KAHN的类似猜想，用于常规图中的独立集合，适用于所有足够大图作为该度的函数。也就是说，每$ d $和每一个足够大的$ n $可除以$ 2D $，$ n/（2d）$副本的完整$ d $ d $ - d $ - 规范的两分图的副本最大化了所有$ k $的独立集和匹配的数量，每$ k $的尺寸$ k $在$ n $ n $ vertices上的所有$ d $ groume y。为了证明这一点，我们利用了统计物理旋转模型的典型集合的群集扩展，我们为此提供了一些进一步的应用，以最大程度地提高和最小化给定最小值的常规图中给定大小的独立集和匹配的数量和匹配。
We prove that the `Upper Matching Conjecture' of Friedland, Krop, and Markström and the analogous conjecture of Kahn for independent sets in regular graphs hold for all large enough graphs as a function of the degree. That is, for every $d$ and every large enough $n$ divisible by $2d$, a union of $n/(2d)$ copies of the complete $d$-regular bipartite graph maximizes the number of independent sets and matchings of size $k$ for each $k$ over all $d$-regular graphs on $n$ vertices. To prove this we utilize the cluster expansion for the canonical ensemble of a statistical physics spin model, and we give some further applications of this method to maximizing and minimizing the number of independent sets and matchings of a given size in regular graphs of a given minimum girth.
