论文标题
Erdős$ - $ McKay猜想的两分版本
A bipartite version of the Erdős $-$ McKay conjecture
论文作者
论文摘要
一个旧的猜想和麦凯（McKay）指出，如果所有均匀的集合中的所有均值集均为$ o（\ log n）$的顺序，则该图包含每个大小的诱导子图，从$ \ \ {0,1，\ ldots，ω（n^2）$。我们证明了猜想的两分类模拟：如果在$ n \ times n $ bipartite图中以$ o（\ log n）$为单位的所有平衡均质集，则该图包含$ \ \ {0,1，\ ldots，ω（n^2）$的每个大小的诱导子图。
An old conjecture of Erdős and McKay states that if all homogeneous sets in an $n$-vertex graph are of order $O(\log n)$ then the graph contains induced subgraphs of each size from $\{0,1,\ldots, Ω(n^2)\}$. We prove a bipartite analogue of the conjecture: if all balanced homogeneous sets in an $n \times n$ bipartite graph are of order $O(\log n)$ then the graph contains induced subgraphs of each size from $\{0,1,\ldots, Ω(n^2)\}$.
