{
  "id": "2004.00938",
  "version": "v1",
  "published": "2020-04-02T11:17:01.000Z",
  "updated": "2020-04-02T11:17:01.000Z",
  "title": "Maximizing the expected number of components in an online search of a graph",
  "authors": [
    "Fabrício Siqueira Benevides",
    "Małgorzata Sulkowska"
  ],
  "comment": "16 pages, 4 figures",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "The following optimal stopping problem is considered. The vertices of a graph $G$ are revealed one by one, in a random order, to a selector. He aims to stop this process at a time $t$ that maximizes the expected number of connected components in the graph $\\tilde{G}_t$, induced by the currently revealed vertices. The selector knows $G$ in advance, but different versions of the game are considered depending on the information that he gets about $\\tilde{G}_t$. We show that when $G$ has $N$ vertices and maximum degree of order $o(\\sqrt{N})$, then the number of components of $\\tilde{G}_t$ is concentrated around its mean, which implies that playing the optimal strategy the selector does not benefit much by receiving more information about $\\tilde{G}_t$. Results of similar nature were previously obtained by M. Laso\\'n for the case where $G$ is a $k$-tree (for constant $k$). We also consider the particular cases where $G$ is a square, triangular or hexagonal lattice, showing that an optimal selector gains $cN$ components and we compute $c$ with an error less than $0.005$ in each case.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-04-02T11:17:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60G40",
      "60K35"
    ],
    "keywords": [
      "expected number",
      "online search",
      "components",
      "optimal selector gains",
      "optimal stopping problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}