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

1. Complete hypergraphs

Let K_m^k={[m]\choose k} be the complete k-graph on m vertices. Erd\H os offered a money prize for determining \pi(K_m^k) for at least one pair k,m with m>k\ge 3; the highest money value of the prize we found in the literature is $3000 (Frankl and Füredi \cite[Page 323]{frankl+furedi:84}). It is still unclaimed. We also refer the reader to the survey by Sidorenko~\cite{sidorenko:95} that discusses \pi(K_m^k) for some other k,m in addition to those discussed below.

    1. K_4^3 minus an edge

          Let K_4^- be obtained from K_4^3 by removing one edge.

      Add remark

      Conjecture 1.4.

      \pi(K_4^-)=\frac27
          The lower bound comes by partitioning [n] into six parts, taking certain 10 complete 3-partite 3-graphs, and then recursively repeating the same construction inside each part, see \cite[Page 323]{frankl+furedi:84}.

      The best known upper bounds come from flag algebra computations: Baber and Talbot [baber+talbot] (by using the method of Razborov [razborov:10] and generating a larger SDP program than that in [razborov:10]) showed that \pi(K_4^-)\le 0.2871.


        • Add remark

          Conjecture 1.1.

          [Turán [turan:41]] \pi(K_4^3)=\frac59.
              There are many different constructions that achieve the lower bound (see Brown [brown:83], Kostochka [kostochka:82], and Fon-der-Flaass [fonderflaass:88]), which is one of the reasons why this problem is so difficult. Successively better upper bounds were proved by de Caen [decaen:88], Giraud (see [chung+lu:01]), and Chung and Lu [chung+lu:01]. Razborov’s [razborov:10] flag algebra approach suggests that \pi(K_4^3)\le 0.561... (and, if needed, this can be converted into a rigorous proof).
            1. Remark. Fon-der-Flaass [fonderflaass:88] presented a construction of K_4^3-free graphs from digraphs. A weakening of Conjecture cj:K34 is that Fon-der-Flaass’ construction cannot beat \frac59; some progress in this direction was made by Razborov [razborov:flaass].
                • Remark. Kalai [kalai:85:gc] (see also \cite[Section 11]{keevash:survey}) presented an interesting approach to \pi(K_4^3).

                    •     Intro to this problem ...

                      Add remark

                      Problem 1.3.

                      This problem is just a placeholder. Replace it bu a real problem, or we can jsut delete it later.


                        • Add remark

                          Conjecture 1.2.

                          [Turán] \pi(K_m^3)=1-\left(\frac{2}{m-1}\right)^2.
                            1. Remark. A construction that achieves the lower bound can be found in \cite[Section 7]{sidorenko:95}. Mubayi and Keevash (see \cite[Section 9]{keevash:survey}) found a different construction (via digraphs).

                                •     Let us mention here another very interesting question for whose solution de Caen \cite[Page 190]{decaen:94} offered 500 Canadian dollars.

                                  Add remark

                                  Problem 1.3.

                                  Does k(1-\pi(K_{k+1}^k)) tend to \infty as k\to\infty?

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