On the Tura´n Number of Triple Systems

For a family of r-graphs F the Tura´n number ex (n, F) is the maximum number of edges in an n vertex r-graph that does not contain any member of F. The Tura´n density <f>π(F)=limlower limit n→∞ ex(n,<sc>F</sc>)/(<ar><r><c CSPAN="1" RSPAN="1" CA="L" RA="T">(n</c></r><r><c CSPAN="1" RSPAN="1" CA="L" RA="T">r</c></r></ar>).</fr></f> When <sc>F</sc> is an <it>r</it>-graph, <it>π</it>(<sc>F</sc>)≠0, and <it>r</it>>2, determining <it>π</it>(<sc>F</sc>) is a notoriously hard problem, even for very simple <it>r</it>-graphs <sc>F</sc>. For example, when <it>r</it>=3, the value of <it>π</it>(<sc>F</sc>) is known for very few (<10) irreducible <it>r</it>-graphs. Building upon a method developed recently by de Caen and Fu¨redi (<it>J. Combin. Theory Ser. B</it>78 (2000), 274–276), we determine the Tura´n densities of several 3-graphs that were not previously known. Using this method, we also give a new proof of a result of Frankl and Fu¨redi (Combinatorica 3 (1983), 341–349) that <it>π</it>(<sc>H</sc>)=<f><fr SHAPE="BUILT" ALIGN="C" STYLE="S">2/9</fr></f>, where <sc>H</sc> has edges 123,124,345. Let <sc>F</sc>(3,2) be the 3-graph 123,145,245,345, let <sc>K</sc>−4 be the 3-graph 123,124,234, and let <sc>C</sc>5 be the 3-graph 123,234,345,451,512. We prove <l type="unord"><li>

&les;(<sc>F</sc>(3,2))&les;<fr shape="case" ALIGN="C" STYLE="S">1/2</fr>,

</li><li>

({:<sc>K</sc>,<sc>C</sc>})&les;=0.322581,

</li><li>

0.464<(<sc>C</sc>)&les;2−√2<0.586.

</li></l> The middle result is related to a conjecture of Frankl and Fu¨redi (<it>Discrete Math.</it>50 (1984) 323–328) that <it>π</it>(<sc>K</sc>−4)=<f><fr SHAPE="BUILT" ALIGN="C" STYLE="S">2/7</fr></f>. The best known bounds are <f><fr SHAPE="BUILT" ALIGN="C" STYLE="S">2/7</fr></f>&les;<it>π</it>(<sc>K</sc>−4)&les;<fr shape="case" ALIGN="C" STYLE="S">1/3</f> When F is an r-graph, π(F)≠0, and r>2, determining π(F) is a notoriously hard problem, even for very simple r-graphs F. For example, when r=3, the value of π(F) is known for very few (<10) irreducible r-graphs. Building upon a method developed recently by de Caen and Fu¨redi (J. Combin. Theory Ser. B78 (2000), 274–276), we determine the Tura´n densities of several 3-graphs that were not previously known. Using this method, we also give a new proof of a result of Frankl and Fu¨redi (Combinatorica 3 (1983), 341–349) that π(H)=<f>2/9</fr></f>, where <sc>H</sc> has edges 123,124,345. Let <sc>F</sc>(3,2) be the 3-graph 123,145,245,345, let <sc>K</sc>−4 be the 3-graph 123,124,234, and let <sc>C</sc>5 be the 3-graph 123,234,345,451,512. We prove <l type="unord"><li>

&les;(<sc>F</sc>(3,2))&les;<fr shape="case" ALIGN="C" STYLE="S">1/2</fr>,

</li><li>

({:<sc>K</sc>,<sc>C</sc>})&les;=0.322581,

</li><li>

0.464<(<sc>C</sc>)&les;2−√2<0.586.

</li></l> The middle result is related to a conjecture of Frankl and Fu¨redi (<it>Discrete Math.</it>50 (1984) 323–328) that <it>π</it>(<sc>K</sc>−4)=<f><fr SHAPE="BUILT" ALIGN="C" STYLE="S">2/7</fr></f>. The best known bounds are <f><fr SHAPE="BUILT" ALIGN="C" STYLE="S">2/7</fr></f>&les;<it>π</it>(<sc>K</sc>−4)&les;<fr shape="case" ALIGN="C" STYLE="S">1/3</f>, where H has edges 123,124,345. Let F(3,2) be the 3-graph 123,145,245,345, let K−4 be the 3-graph 123,124,234, and let C5 be the 3-graph 123,234,345,451,512. We prove <l type="unord"><li>&les;(F(3,2))&les;1/2</fr>,

</li><li>

({:<sc>K</sc>,<sc>C</sc>})&les;=0.322581,

</li><li>

0.464<(<sc>C</sc>)&les;2−√2<0.586.

</li></l> The middle result is related to a conjecture of Frankl and Fu¨redi (<it>Discrete Math.</it>50 (1984) 323–328) that <it>π</it>(<sc>K</sc>−4)=<f><fr SHAPE="BUILT" ALIGN="C" STYLE="S">2/7</fr></f>. The best known bounds are <f><fr SHAPE="BUILT" ALIGN="C" STYLE="S">2/7</fr></f>&les;<it>π</it>(<sc>K</sc>−4)&les;<fr shape="case" ALIGN="C" STYLE="S">1/3,</li><li>({:K,C})&les;=0.322581,</li><li>0.464<(C)&les;2−√2<0.586.</li></l> The middle result is related to a conjecture of Frankl and Fu¨redi (Discrete Math.50 (1984) 323–328) that π(K−4)=<f>2/7</fr></f>. The best known bounds are <f><fr SHAPE="BUILT" ALIGN="C" STYLE="S">2/7</fr></f>&les;<it>π</it>(<sc>K</sc>−4)&les;<fr shape="case" ALIGN="C" STYLE="S">1/3</f>. The best known bounds are <f>2/7</fr></f>&les;<it>π</it>(<sc>K</sc>−4)&les;<fr shape="case" ALIGN="C" STYLE="S">1/3</f>&les;π(K−4)&les;1/3. [Copyright &y& Elsevier]