Rainbow Fractional Matchings
Rainbow Fractional Matchings
复制标题
彩虹分数匹配
作者：
R. Aharoni;R. Holzman;Zilin Jiang
我们证明了任何一个E1，...，在r-一致超图中，每个具有大小为n的分数匹配的边的集合的E rn（不一定是不同的）具有大小为n的彩虹分数匹配（即，来自支持这种分数匹配的不同Ei的边的集合）。当超图是r-部的且n是整数时，所需的集合数从rn下降到rn-r +1。这里解决的问题是对应的彩虹匹配问题的一个分数版本，这个问题是由Drisko和Aharoni和Berger在二部图的情况下解决的，但是对于一般图以及r>2的r-部超图是开放的。我们的拓扑证明是基于Kalai和Meshulam关于单纯复形和拟阵在同一顶点集上的一个结果。
We prove that any family E1,..., E┌rn┐ of (not necessarily distinct) sets of edges in an r-uniform hypergraph, each having a fractional matching of size n, has a rainbow fractional matching of size n (that is, a set of edges from distinct Ei’s which supports such a fractional matching). When the hypergraph is r-partite and n is an integer, the number of sets needed goes down from rn to rn−r+1. The problem solved here is a fractional version of the corresponding problem about rainbow matchings, which was solved by Drisko and by Aharoni and Berger in the case of bipartite graphs, but is open for general graphs as well as for r-partite hypergraphs with r>2. Our topological proof is based on a result of Kalai and Meshulam about a simplicial complex and a matroid on the same vertex set.