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 -free orgraph 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 underlying the orgraph : 1. is complete multipartite; 2. The edge density of 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 .
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.