Loading Web-Font TeX/Main/Regular
| Register
\newcommand{\Cat}{{\rm Cat}} \newcommand{\A}{\mathcal A} \newcommand{\freestar}{ \framebox[7pt]{$\star$} }

2. Turán functions for books

Let the book B_{k,m} consist of m edges sharing k-1 common points plus one more edge that contains the remaining m points and is disjoint otherwise. Let us exclude the case m\le 1 when \pi(B_{k,m})=0. The hypergraph problems for books turned out (relatively) more tractable. We know \operatorname{ex}(n,B_{k,m}) exactly for all large n, when 2\le m\le k\le 4, see [<a href="#" class="cite">bollobas:74,frankl+furedi:83,furedi+pikhurko+simonovits:03:ejc,keevash+mubayi:04,furedi+pikhurko+simonovits:05,furedi+pikhurko+simonovits:06,furedi+mubayi+pikhurko:08,pikhurko:08:c</a>].

    1.     Frankl and Füredi [frankl+furedi:89] determined \pi(B_{k,2}) for k=5,6; in both cases the lower bounds comes by blowing up a small design. The following question is still open (see Frankl and Füredi \cite[Conjecture 1.5]{frankl+furedi:89}):

      Add remark

      Problem 2.1.

      Determine \operatorname{ex}(n,B_{5,2}) and \operatorname{ex}(n,B_{6,2}) exactly for all large n.
        1. Remark. One difficulty for this problem is that it is not clear how to prove the stability property, that is, that all almost extremal graphs have similar structure.


            • Add remark

              Conjecture 2.2.

              [[furedi+mubayi+pikhurko:08,bohman+frieze+mubayi+pikhurko:10]] \pi(B_{5,5})=\frac{40}{81},
              and \pi(B_{6,6})=\frac12.
                1. Remark. The lower bounds come from a “bipartite” construction. It was proved in [bohman+frieze+mubayi+pikhurko:10] that \pi(B_{5,5})\le 0.534... and that the bipartite construction is not optimal for \pi(B_{k,k}) when k\ge 7.
                    • Remark. The Turán density is unknown for B_{5,3} and B_{5,4} which is an interesting (and perhaps tractable) open problem.

                          Cite this as: AimPL: Hypergraph Turán problem, available at http://aimpl.org/hypergraphturan.