论文标题
$ g_ {n，p} $的Biclique分区的关键概率
A Critical Probability for Biclique Partition of $G_{n,p}$
论文作者
论文摘要
图$ g =（v，e）$的双式分区编号，表示为$ bp（g）$，是$ g $ $ g $的成对边缘分离的最小数量，以便$ g $的每个边缘属于其中一个。很容易看到$ bp（g）\ leq n -α（g）$，其中$α（g）$是$ g $的独立集的最大尺寸。在80年代，Erdős的猜想是，几乎每个图形$ g $ equality均具有；即，如果$ g = g_ {n，1/2} $，则具有高概率的$ bp（g）= n -α（g）$。阿隆表明这是错误的。我们表明，如果我们采用$ g = g_ {n，p} $，$ p $是恒定且小于一定阈值$ p_0 \ of约0.312 $，则表明ERDőS的猜想是正确的。这验证了Chung and Peng的猜想，这些值为$ P $。我们还表明，如果$ p_0 <p <1/2 $，则$ bp（g_ {n，p}）= n-（1 +θ（1））α（g_ {n，p}）$具有很高的可能性。
The biclique partition number of a graph $G= (V,E)$, denoted $bp(G)$, is the minimum number of pairwise edge disjoint complete bipartite subgraphs of $G$ so that each edge of $G$ belongs to exactly one of them. It is easy to see that $ bp(G) \leq n - α(G)$, where $α(G)$ is the maximum size of an independent set of $G$. Erdős conjectured in the 80's that for almost every graph $G$ equality holds; i.e., if $ G=G_{n,1/2}$ then $bp(G) = n - α(G)$ with high probability. Alon showed that this is false. We show that the conjecture of Erdős is true if we instead take $ G=G_{n,p}$, where $p$ is constant and less than a certain threshold value $p_0 \approx 0.312$. This verifies a conjecture of Chung and Peng for these values of $p$. We also show that if $p_0 < p <1/2$ then $bp(G_{n,p}) = n - (1 + Θ(1)) α(G_{n,p})$ with high probability.
