论文标题
最小化$ k_ {s，t} $的边缘数 - 饱和的两部分图
Minimizing the number of edges in $K_{s,t}$-saturated bipartite graphs
论文作者
论文摘要
本文考虑了饱和的两分数图中的边缘最小化问题。如果$ n $ by $ n $ by $ n $ a $ g $是$ h $饱和，如果$ g $不包含子图同构为$ h $，则将任何缺失的边缘添加到$ g $会创建$ h $的副本。半个多世纪以前，Wessel和Bollobás独立地解决了将$ k _ {（s，t）} $的边缘数量最小化的问题，其中$ k _ {（s，t）} $是$ s $ s $ vertices图形的$ s $ vertices图表，该图是$ s $ vertices the First Collet class和$ t $ t $ t $ s $ t $ s $ s $ s $ thert class和$ t $ t $ s $ s $ therticle class和$ t $ t $。但是，Moshkovitz和Shapira仅考虑了一个非常自然的“无序”类似物。当$ s = t $时，可以轻松地检查无序的变体与有序的情况完全相同。后来，Gan，Korándi和Sudakov在$ k_ {s，t} $的最小边缘数量上对$ n $ bipartite图的最小边缘进行了差异，这仅比Moshkovitz和Moshkovitz和Shapira的构想要小。在本文中，我们确认了他们对$ s = t-1 $的猜想，并与极端图的分类确认。我们还提高了Gan，Korándi和Sudakov对一般$ S $和$ t $的估计，以及所有足够大的$ n $。
This paper considers an edge minimization problem in saturated bipartite graphs. An $n$ by $n$ bipartite graph $G$ is $H$-saturated if $G$ does not contain a subgraph isomorphic to $H$ but adding any missing edge to $G$ creates a copy of $H$. More than half a century ago, Wessel and Bollobás independently solved the problem of minimizing the number of edges in $K_{(s,t)}$-saturated graphs, where $K_{(s,t)}$ is the `ordered' complete bipartite graph with $s$ vertices from the first color class and $t$ from the second. However, the very natural `unordered' analogue of this problem was considered only half a decade ago by Moshkovitz and Shapira. When $s=t$, it can be easily checked that the unordered variant is exactly the same as the ordered case. Later, Gan, Korándi, and Sudakov gave an asymptotically tight bound on the minimum number of edges in $K_{s,t}$-saturated $n$ by $n$ bipartite graphs, which is only smaller than the conjecture of Moshkovitz and Shapira by an additive constant. In this paper, we confirm their conjecture for $s=t-1$ with the classification of the extremal graphs. We also improve the estimates of Gan, Korándi, and Sudakov for general $s$ and $t$, and for all sufficiently large $n$.
