论文标题
最大程度有限的图表中的双方独立数
Bipartite independence number in graphs with bounded maximum degree
论文作者
论文摘要
我们认为在两部分图中，自然而又没有研究的极端问题。两部分图$ g $中的大小$ t $的双孔是$ g $的$ k_ {t，t，t} $的副本。令$ f（n，δ）$为最大的$ k $，每$ n \ times n $ a $两部分图具有最高度$δ$的零件，其中一个尺寸为$ k $。因此，确定$ f（n，δ）$是在具有给定数量的顶点和有界最大程度的图中找到最大的独立集的两部分类似物。我们的主要结果决定了$ f（n，δ）$的渐近行为。更确切地说，我们表明，对于大而固定的$δ$和$ n $，$ f（n，δ）=θ（\ frac {\logδ}δn）$。我们进一步解决了$δ$的更具体的制度，尤其是当$δ$是一个小的固定常数时。特别是，我们确切地确定$ f（n，2）$，并获得$ f（n，3）$的界限，尽管确定$ f（n，3）$的精确值仍开放。
We consider a natural, yet seemingly not much studied, extremal problem in bipartite graphs. A bi-hole of size $t$ in a bipartite graph $G$ is a copy of $K_{t, t}$ in the bipartite complement of $G$. Let $f(n, Δ)$ be the largest $k$ for which every $n \times n$ bipartite graph with maximum degree $Δ$ in one of the parts has a bi-hole of size $k$. Determining $f(n, Δ)$ is thus the bipartite analogue of finding the largest independent set in graphs with a given number of vertices and bounded maximum degree. Our main result determines the asymptotic behavior of $f(n, Δ)$. More precisely, we show that for large but fixed $Δ$ and $n$ sufficiently large, $f(n, Δ) = Θ(\frac{\log Δ}Δ n)$. We further address more specific regimes of $Δ$, especially when $Δ$ is a small fixed constant. In particular, we determine $f(n, 2)$ exactly and obtain bounds for $f(n, 3)$, though determining the precise value of $f(n, 3)$ is still open.
