{
  "id": "1008.4707",
  "version": "v1",
  "published": "2010-08-27T12:48:48.000Z",
  "updated": "2010-08-27T12:48:48.000Z",
  "title": "On the Fon-der-Flaass Interpretation of Extremal Examples for Turan's (3,4)-problem",
  "authors": [
    "Alexander Razborov"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In 1941, Turan conjectured that the edge density of any 3-graph without independent sets on 4 vertices (Turan (3,4)-graph) is >= 4/9(1-o(1)), and he gave the first example witnessing this bound. Brown (1983) and Kostochka (1982) found many other examples of this density. Fon-der-Flaass (1988) presented a general construction that converts an arbitrary $\\vec C_4$-free orgraph $\\Gamma$ into a Turan (3,4)-graph. He observed that all Turan-Brown-Kostochka examples result from his construction, and proved the bound >= 3/7(1-o(1)) on the edge density of any Turan (3,4)-graph obtainable in this way. In this paper we establish the optimal bound 4/9(1-o(1)) on the edge density of any Turan (3,4)-graph resulting from the Fon-der-Flaass construction under any of the following assumptions on the undirected graph $G$ underlying the orgraph $\\Gamma$: 1. $G$ is complete multipartite; 2. The edge density of $G$ is >= (2/3-epsilon) for some absolute constant epsilon>0. We are also able to improve Fon-der-Flaass's bound to 7/16(1-o(1)) without any extra assumptions on $\\Gamma$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-08-27T12:48:48.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "edge density",
      "fon-der-flaass interpretation",
      "extremal examples",
      "turan-brown-kostochka examples result",
      "fon-der-flaass construction"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1008.4707R"
    }
  }
}