$\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 Fü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. 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$. • Conjecture 1.1. [Turá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 ... Problem 1.3. This problem is just a placeholder. Replace it bu a real problem, or we can jsut delete it later. • Conjecture 1.2. [Turá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. 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.