Bipartite Independence Number in Graphs with Bounded Maximum Degree
Bipartite Independence Number in Graphs with Bounded Maximum Degree
复制标题
最大有界图中的二分独立数
DOI：
10.1137/20m1321760
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Lea Weber
中科院分区：
文献类型：
--
作者：
M. Axenovich;Jean;Richard Snyder;Lea Weber
我们考虑一个自然的，但似乎没有太多研究的，二部图中的极值问题。二部图$G$中大小为$t$的双孔是$G$的二部补中$K_{t, t}$的副本。设$f(n, \Delta)$为最大的$k$，其中一个部分中每个最大度为$\Delta$的$n \times n$二部图都有一个尺寸为$k$的双孔。因此，确定$f(n, \Delta)$是在具有给定顶点数量和有界最大度的图中寻找最大独立集的二部模拟。我们的主要结果确定了$f(n, \Delta)$的渐近性质。更准确地说，对于大但固定的$\Delta$和足够大的$n$, $f(n, \Delta) = \Theta(\frac{\log \Delta}{\Delta} n)$。我们进一步解决$\Delta$的更具体的制度，特别是当$\Delta$是一个小的固定常数。特别是，我们精确地确定$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, \Delta)$ be the largest $k$ for which every $n \times n$ bipartite graph with maximum degree $\Delta$ in one of the parts has a bi-hole of size $k$. Determining $f(n, \Delta)$ 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, \Delta)$. More precisely, we show that for large but fixed $\Delta$ and $n$ sufficiently large, $f(n, \Delta) = \Theta(\frac{\log \Delta}{\Delta} n)$. We further address more specific regimes of $\Delta$, especially when $\Delta$ 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.