{
  "id": "2304.03710",
  "version": "v1",
  "published": "2023-04-07T15:50:02.000Z",
  "updated": "2023-04-07T15:50:02.000Z",
  "title": "The completion numbers of Hamiltonicity and pancyclicity in random graphs",
  "authors": [
    "Yahav Alon",
    "Michael Anastos"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\mu(G)$ denote the minimum number of edges whose addition to $G$ results in a Hamiltonian graph, and let $\\hat{\\mu}(G)$ denote the minimum number of edges whose addition to $G$ results in a pancyclic graph. We study the distributions of $\\mu (G),\\hat{\\mu}(G)$ in the context of binomial random graphs. Letting $d=d(n)$:=$n\\cdot p$, we prove that there exists a function $f:\\mathbb{R}^+\\to [0,1]$ of order $f(d) = \\frac{1}{2}de^{-d}+e^{-d}+O(d^6e^{-3d})$ such that, if $G\\sim G(n,p)$ with $20 \\le d(n) \\le 0.4 \\log n$, then with high probability $\\mu (G)= (1+o(1))\\cdot f(d)\\cdot n$. Let $n_i(G)$ denote the number of degree $i$ vertices in $G$. A trivial lower bound on $\\mu(G)$ is given by the expression $n_0(G) + \\lceil \\frac{1}{2}n_1(G) \\rceil$. We show that in the random graph process $\\{ G_t\\}_{t=0}^{\\binom{n}{2}}$ with high probability there exist times $t_1,t_2$, both of order $(1+o(1))n\\cdot \\left( \\frac{1}{6}\\log n + \\log \\log n \\right)$, such that $\\mu(G_t)=n_0(G_t) + \\lceil \\frac{1}{2}n_1(G_t) \\rceil$ for every $t\\ge t_1$ and $\\mu(G_t)>n_0(G_t) + \\lceil \\frac{1}{2}n_1(G_t) \\rceil$ for every $t\\le t_2$. The time $t_i$ can be characterized as the smallest $t$ for which $G_t$ contains less than $i$ copies of a certain problematic subgraph. In particular, this implies that the hitting time for the existence of a Hamilton path is equal to the hitting time of $n_1(G) \\le 2$ with high probability. For the binomial random graph, this implies that if $np-\\frac{1}{3}\\log n - 2\\log \\log n \\to \\infty$ and $G\\sim G(n,p)$ then, with high probability, $\\mu (G) = n_0(G) + \\lceil \\frac{1}{2}n_1(G) \\rceil$. Finally, we show that if $G\\sim G(n,p)$ and $np\\ge 20$ then, with high probability, $\\hat{\\mu} (G)=\\mu (G)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-04-07T15:50:02.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "high probability",
      "completion numbers",
      "binomial random graph",
      "hamiltonicity",
      "minimum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}