{
  "id": "1812.09841",
  "version": "v1",
  "published": "2018-12-24T06:17:14.000Z",
  "updated": "2018-12-24T06:17:14.000Z",
  "title": "A Note on Replica Symmetry in Upper Tails of Mean-Field Hypergraphs",
  "authors": [
    "Somabha Mukherjee",
    "Bhaswar B. Bhattacharya"
  ],
  "comment": "14 pages",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Given a sequence of $s$-uniform hypergraphs $\\{H_n\\}_{n \\geq 1}$, denote by $T_p(H_n)$ the number of edges in the random induced hypergraph obtained by including every vertex in $H_n$ independently with probability $p \\in (0, 1)$. Recent advances in the large deviations of low complexity non-linear functions of independent Bernoulli variables can be used to show that tail probabilities of $T_p(H_n)$ are precisely approximated by the so-called `mean-field' variational problem, under certain assumptions on the sequence $\\{H_n\\}_{n \\geq 1}$. In this note, we study properties of this variational problem for the upper tail of $T_p(H_n)$, assuming that the mean-field approximation holds. In particular, we show that the variational problem has a universal {\\it replica symmetric} phase (where it is uniquely minimized by a constant function), for any sequence of {\\it regular} $s$-uniform hypergraphs, which depends only on $s$. We also analyze the associated variational problem for the related problem of estimating subgraph frequencies in a converging sequence of dense graphs. Here, the variational problems themselves have a limit which can be expressed in terms of the limiting graphon.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-12-24T06:17:14.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "variational problem",
      "upper tail",
      "mean-field hypergraphs",
      "replica symmetry",
      "low complexity non-linear functions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}