论文标题
双方对应覆盖中的独立横向
Independent transversals in bipartite correspondence-covers
论文作者
论文摘要
假设$ g $和$ h $是双方图形，$ l：v（g）\ to 2^{v（h）} $诱导$ v（h）$的分区，使得$ h $ of $ h $ of $ l（v）$和$ l（v'v'）$在$ v'\ in e（g）$中是匹配的。我们为每个$ \ varepsilon> 0 $显示，如果$ h $具有最高度$ d $和$ | l（v）| \ ge（1+ \ varepsilon）d/\ log D $用于v（g）$中的所有$ v \，然后$ h $就$ l $接受独立的横向，前提是$ d $足够大。零件尺寸的界限在渐近上是$ 2 $ $ 2 $。我们还显示了该结果的一些不对称变体。
Suppose $G$ and $H$ are bipartite graphs and $L: V(G)\to 2^{V(H)}$ induces a partition of $V(H)$ such that the subgraph of $H$ induced between $L(v)$ and $L(v')$ is a matching whenever $vv'\in E(G)$. We show for each $\varepsilon>0$ that, if $H$ has maximum degree $D$ and $|L(v)| \ge (1+\varepsilon)D/\log D$ for all $v\in V(G)$, then $H$ admits an independent transversal with respect to $L$, provided $D$ is sufficiently large. This bound on the part sizes is asymptotically sharp up to a factor $2$. We also show some asymmetric variants of this result.
