Structure of towers and a new proof of the tight cut lemma
Structure of towers and a new proof of the tight cut lemma
复制标题
塔的结构和紧割引理的新证明
DOI：
10.1007/978-3-319-71150-8_20
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Nanao Kita
中科院分区：
文献类型：
--
作者：
N Tsujino;Y. Nishihara;D. Yamazaki;Y. Seto;Nanao Kita;Nanao Kita;Nanao Kita;Nanao Kita;Nanao Kita
在我们的研究的第一部分中，我们通过引入高阶和塔序列的新概念来扩展BASICI正则分解的理论。正则分解是最近提出的匹配理论中的一个工具，即使对于具有完美匹配的一般图，它也可以非平凡地应用。在研究匹配时，经常需要考虑交替路径的结构。我们展示了一个图是如何由塔和塔序列组成的，并由此得到了交错路径的结构。这一结果为分析具有完美匹配的一般图提供了有力的工具。本文的第二部分是对第一部分得到的所谓右割引理的新的图论证明。为了得到完美匹配多面体的特征，Edmonds，Lovász和Pulley Blank引入了紧割引理，这是他们工作中最具挑战性的方面。紧割引理实际上声称砖是构成图的基本构件，可以被称为这一领域的一个关键结果。尽管紧割引理本身是一种纯粹的图论表述，但直到Szigeti利用Frank-Szigeti的最优耳分解理论给出了这样的证明，几十年来一直没有已知的图论证明。相比之下，我们使用扩展的BaSilicon正则分解理论作为唯一的初步结果提供了一个新的证明，并相应地提出了一种新的研究砖和紧割或匹配理论的策略。我们的证明展示了关于交替路径的讨论是如何通过大殿正则分解从第一原理构造紧割引理的，即使没有使用障碍，即匹配的对偶概念。我们证明的显著特征是它是纯粹的图论，纯粹的匹配(基数1-匹配)理论，以及关于匹配的纯粹的“原始”。
In the first part of our study, we extend the theory of basilica canonical decomposition by introducing new concepts known astowersandtower-sequences. The basilica canonical decomposition is a recently proposed tool in matching theory that can be applied non-trivially even for general graphs with perfect matchings. When studying matchings, the structure ofalternating pathsfrequently needs to be considered. We show how a graph is made up of towers and tower-sequences, and thus obtain the structure of alternating paths in terms of the basilica canonical decomposition. This result provides a strong tool for analyzing general graphs with perfect matchings.The second part of our study is a new graph theoretic proof of the so-calledTight Cut Lemmaderived from the first part of our study. To derive a characterization of the perfect matchings polytope, Edmonds, Lovász, and Pulleyblank introduced the Tight Cut Lemma as the most challenging aspect of their work. The Tight Cut Lemma in fact claimsbricksas the fundamental building blocks that constitute a graph and can be referred to as a key result in this field. Although the Tight Cut Lemma itself is a purely graph theoretic statement, there was no known graph theoretic proof for decades until Szigeti provided such a proof using Frank-Szigeti’s optimal ear decomposition theory.By contrast, we provide a new proof using the extended theory of basilica canonical decomposition as the only preliminary result, and accordingly proposes a new strategy for studying bricks and tight cuts or matching theory in general. Our proof shows how the discussions on alternating paths construct the Tight Cut Lemma from first principles via the basilica canonical decomposition, even without usingbarriers, that is, the dual notion of matchings. The distinguishing features of our proof are that it is purely graph theoretic, purely matching (cardinality 1-matching) theoretic, and purely “primal” with respect to matchings.