论文标题
渐近尖锐的独立横向数量
An Asymptotically Sharp Bound on the Maximum Number of Independent Transversals
论文作者
论文摘要
令$ g $为带有分区$ v_1，v_2，\ ldots，v_k $ of $ v（g）$的多部分图。令$ d_ {i，j} $表示对$（v_i，v_j）$的边缘密度。独立的横向是$ g $的独立集，每个$ v_i $中的一个顶点正好。在本文中，我们证明了$ d_ {i，j} $的最大独立横向数量上的渐近尖锐上限。
Let $G$ be a multipartite graph with partition $V_1, V_2,\ldots, V_k$ of $V(G)$. Let $d_{i,j}$ denote the edge density of the pair $(V_i, V_j)$. An independent transversal is an independent set of $G$ with exactly one vertex in each $V_i$. In this paper, we prove an asymptotically sharp upper bound on the maximum number of independent transversals given the $d_{i,j}$'s.
