{
  "id": "2303.12046",
  "version": "v1",
  "published": "2023-03-21T17:32:32.000Z",
  "updated": "2023-03-21T17:32:32.000Z",
  "title": "Saturation in Random Graphs Revisited",
  "authors": [
    "Sahar Diskin",
    "Ilay Hoshen",
    "Maksim Zhukovskii"
  ],
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "For graphs $G$ and $F$, the saturation number $\\textit{sat}(G,F)$ is the minimum number of edges in an inclusion-maximal $F$-free subgraph of $G$. In 2017, Kor\\'andi and Sudakov initiated the study of saturation in random graphs. They showed that for constant $p\\in (0,1)$, whp $\\textit{sat}\\left(G(n,p),K_s\\right)=\\left(1+o(1)\\right)n\\log_{\\frac{1}{1-p}}n$. We show that for every graph $F$ and every constant $p\\in (0,1)$, whp $\\textit{sat}\\left(G(n,p), F\\right)=O(n\\ln n)$. Furthermore, if every edge of $F$ belongs to a triangle, then the above is asymptotically sharp, that is, whp $\\textit{sat}\\left(G(n,p),F\\right)=\\Theta(n\\ln n)$. We further show that for a large family of graphs $\\mathcal{F}$ with an edge that does not belong to a triangle, which includes all the bipartite graphs, for every $F\\in \\mathcal{F}$ and constant $p\\in(0,1)$, whp $\\textit{sat}\\left(G(n,p),F\\right)=O(n)$. We conjecture that this sharp transition from $O(n)$ to $\\Theta(n\\ln n)$ depends only on this property, that is, that for any graph $F$ with at least one edge that does not belong to a triangle, $\\textit{sat}\\left(G(n,p),F\\right)=O(n)$. We further generalise the result of Kor\\'andi and Sudakov, and show that for a more general family of graphs $\\mathcal{F}'$, including all complete graphs $K_s$ and all complete multipartite graphs of the form $K_{1,1,s_3,\\ldots, s_{\\ell}}$, for every $F\\in \\mathcal{F}'$ and every constant $p\\in(0,1)$, whp $\\textit{sat}\\left(G(n,p),F\\right)=\\left(1+o(1)\\right)n\\log_{\\frac{1}{1-p}}n$. Finally, we show that for every complete multipartite graph $K_{s_1, s_2, \\ldots, s_{\\ell}}$ and every $p\\in \\left[\\frac{1}{2},1\\right)$, $\\textit{sat}\\left(G(n,p),K_{s_1,s_2,\\ldots,s_{\\ell}}\\right)=\\left(1+o(1)\\right)n\\log_{\\frac{1}{1-p}}n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-03-21T17:32:32.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random graphs",
      "complete multipartite graph",
      "bipartite graphs",
      "free subgraph",
      "sharp transition"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}