| 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.