A proof of the upper matching conjecture for large graphs
A proof of the upper matching conjecture for large graphs
复制标题
大图上匹配猜想的证明
DOI：
10.1016/j.jctb.2021.07.005
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Perkins, Will
中科院分区：
文献类型：
--
作者：
Davies, Ewan;Jenssen, Matthew;Perkins, Will
我们证明了Friedland、Krop和Markström的“上匹配猜想”和Kahn关于正则图中独立集的类似猜想对于所有足够大的图都是度的函数。也就是说，对于每个d和每个足够大的能被2d整除的n，完全d-正则二部图的n/（2d）个副本的并集使得在n个顶点上的所有d-正则图上的每个k的独立集和大小为k的匹配的数量最大化。为了证明这一点，我们利用集群扩展的统计物理自旋模型的正则系综，我们给出了一些进一步的应用，这种方法的最大化和最小化的独立集的数量和匹配的一个给定的大小在一个给定的最小围长的正则图。
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/(2 d) 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.
登录
查看更多内容
DOI：
--
发表时间：
2013
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Jonathan Cutler;A. J. Radcliffe
通讯作者：
A. J. Radcliffe
DOI：
--
发表时间：
2015
期刊：
影响因子：
--
作者：
Will Perkins
通讯作者：
Will Perkins
DOI：
--
发表时间：
2006
期刊：
影响因子：
--
作者：
S. Friedland;E. Krop;P. Lundow;K. Markstrom
通讯作者：
K. Markstrom
影响因子：
0.9
作者：
Luke Sernau
通讯作者：
Luke Sernau
DOI：
--
发表时间：
2012
期刊：
Journal of Combinatorial Theory
影响因子：
--
作者：
L. Ilinca;J. Kahn
通讯作者：
J. Kahn