{
  "id": "1411.3504",
  "version": "v1",
  "published": "2014-11-13T11:22:58.000Z",
  "updated": "2014-11-13T11:22:58.000Z",
  "title": "An extension of Mantel's theorem to random 4-uniform hypergraphs",
  "authors": [
    "Ran Gu",
    "Xueliang Li",
    "Zhongmei Qin",
    "Yongtang Shi",
    "Kang Yang"
  ],
  "comment": "18 pages. arXiv admin note: substantial text overlap with arXiv:1310.1501 by other authors",
  "categories": [
    "math.CO"
  ],
  "abstract": "A sparse version of Mantel's Theorem is that, for sufficiently large $p$, with high probability (w.h.p.), every maximum triangle-free subgraph of $G(n,p)$ is bipartite. DeMarco and Kahn proved this for $p>K \\sqrt{\\log n/n}$ for some constant $K$, and apart from the value of the constant, this bound is the best possible. Denote by $T_3$ the 3-uniform hypergraph with vertex set $\\{a,b,c,d,e\\}$ and edge set $\\{abc,ade,bde\\}$. Frankl and F\\\"uredi showed that the maximum 3-uniform hypergraph on $n$ vertices containing no copy of $T_3$ is tripartite for $n> 3000$. For some integer $k$, let $G^k(n,p)$ be the random $k$-uniform hypergraph. Balogh et al. proved that for $p>K \\log n/n$ for some constant $K$, every maximum $T_3$-free subhypergraph of $G^3(n,p)$ w.h.p. is tripartite and it does not hold when $p=0.1 \\sqrt{\\log n}/n$. Denote by $T_4$ the 4-uniform hypergraph with vertex set $\\{1,2,3,4,5,6,7\\}$ and edge set $\\{1234,1235,4567\\}$. Pikhurko proved that there is an $n_0$ such that for all $n\\ge n_0$, the maximum 4-uniform hypergraph on $n$ vertices containing no copy of $T_4$ is 4-partite. In this paper, we extend this type of extremal problem in random 4-uniform hypergraphs. We show that for some constant $K$ and $p>K \\log n/n$, w.h.p. every maximum $T_4$-free subhypergraph of $G^4(n,p)$ is 4-partite.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-11-13T11:22:58.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C65",
      "05C35",
      "05C80",
      "05C75"
    ],
    "keywords": [
      "mantels theorem",
      "free subhypergraph",
      "edge set",
      "vertex set",
      "maximum triangle-free subgraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1411.3504G"
    }
  }
}