{
  "id": "2206.13490",
  "version": "v1",
  "published": "2022-06-27T17:52:33.000Z",
  "updated": "2022-06-27T17:52:33.000Z",
  "title": "A Critical Probability for Biclique Partition of $G_{n,p}$",
  "authors": [
    "Tom Bohman",
    "Jakob Hofstad"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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 - \\alpha(G)$, where $\\alpha(G)$ is the maximum size of an independent set of $G$. Erd\\H{o}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 - \\alpha(G)$ with high probability. Alon showed that this is false. We show that the conjecture of Erd\\H{o}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 \\leq p <1/2$, then $bp(G_{n,p}) = n - (1 + \\Theta(1)) \\alpha(G_{n,p})$ with high probability.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-06-27T17:52:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C69",
      "05C70"
    ],
    "keywords": [
      "critical probability",
      "edge disjoint complete bipartite subgraphs",
      "pairwise edge disjoint complete bipartite",
      "high probability",
      "biclique partition number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}