% LaTeX class specification.  Any changes will not appear in the final version
\documentclass[12pt,letterpaper, reqno]{aimpl}

% The problem list should be arranged like a research paper, with
% introductory material followed be one or more main sections.
% Do not divide the sections into subsections.
% Each section could have its own introductory material.
% The main part of each section is a "problem block" which has the format
% [[see elsewhere for more documentation]]

% New macros.
% If at all possible, please do not define any new macros.  Each
% macro you introduce has the potential to cause problems with the
% long-term maintenance of the problem list.

% removed \n from join and moved it to MACROS in app.js
\newcommand{\Cat}{{\rm Cat}}
\newcommand{\A}{\mathcal A}
\newcommand{\freestar}{ \framebox[7pt]{$\star$} }

\begin{document}
\title{Hypergraph Turán problem}
\author{Edited by Dhruv Mubayi, Oleg Pikhurko, and Benny Sudakov}

\urlstub{hypergraphturan}

\maketitle

Here we present a selection of some open questions related to the
hypergraph Tur\'an problem.

Let $[n]$ denote the interval $\{1,\dots,n\}$. For a set $X$ and an
integer $k$, let ${X\choose k}=\{Y\subseteq X\mid |Y|=k\}$ be the
family of all $k$-subsets of $X$. By a \emph{$k$-graph} $F$ we
understand a $k$-uniform set system, that is, $F$ is a pair $(V,E)$
where $V$ is the set of vertices and $E\subseteq {V\choose k}$. For
convenience, we will identify $k$-graphs with their edge set. Thus
e.g.\ $|F|=|E(F)|$ denotes the \emph{size} of $F$.

Let $\mathcal F$ be a family of $k$-graphs. A $k$-graph $G$ is \emph{$\mathcal F$-free}
if $G$ does not contain any member of $\mathcal F$ as a (not necessarily induced)
subgraph. The \emph{Tur\'an function} is
$$
\textstyle
\operatorname{ex}(n,\mathcal F)=\max\{|G|\mid G\subseteq {[n]\choose k},\
G\mbox{ is $\mathcal F$-free}\}.
$$
It goes back to the fundamental paper of Tur\'an~\cite{turan:41}. The
\emph{Tur\'an density} is
 $$
\pi(\mathcal F)=\lim_{n\to\infty} \frac{\operatorname{ex}(n,\mathcal F)}{{n\choose k}};
$$
it not hard to show that the limit exists. If $\mathcal F=\{F\}$, then we abbreviate
$\operatorname{ex}(n,\{F\})$ to $\operatorname{ex}(n,F)$, etc.


We refer the reader to the surveys by F\"uredi~\cite{furedi:91},
Sidorenko~\cite{sidorenko:95}, and Keevash~\cite{keevash:survey}.


\section{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.




\begin{problemblock}
\name{$K_4^3$ minus an edge}
Let $K_4^-$ be obtained from $K_4^3$ by removing one edge.


\begin{conjecture}[1.4] $\pi(K_4^-)=\frac27$ \end{conjecture}




\end{problemblock}



\begin{problemblock}

\begin{conjecture}[1.1] $\pi(K_4^3)=\frac59$.\label{K34} \end{conjecture}




\begin{remark}Fon-der-Flaass~\cite{fonderflaass:88} presented a construction of
$K_4^3$-free graphs from digraphs. A weakening of Conjecture~\ref{cj:K34}
is that Fon-der-Flaass' construction cannot beat $\frac59$; some
progress in this direction was made by Razborov~\cite{razborov:flaass}.
\end{remark}

\begin{remark}Kalai~\cite{kalai:85:gc} (see also~\cite[Section~11]{keevash:survey})
presented an interesting approach to $\pi(K_4^3)$.
\end{remark}

\end{problemblock}



\begin{problemblock}Intro to this problem ...

\begin{problem}[1.3] This problem is just a placeholder.  Replace it bu a real problem,
or we can jsut delete it later. \end{problem}




\end{problemblock}



\begin{problemblock}

\begin{conjecture}[1.2] $\pi(K_m^3)=1-\left(\frac{2}{m-1}\right)^2$.
\label{Km3} \end{conjecture}




\begin{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).\end{remark}

\end{problemblock}



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


\begin{problem}[1.3]  Does $k(1-\pi(K_{k+1}^k))$ tend to $\infty$
as $k\to\infty$? \end{problem}




\end{problemblock}



\section{Turán functions for books}

Let \emph{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>].




\begin{problemblock}Frankl and F\"uredi~\cite{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\"uredi~\cite[Conjecture~1.5]{frankl+furedi:89}):


\begin{problem}[2.1] Determine $\operatorname{ex}(n,B_{5,2})$ and $\operatorname{ex}(n,B_{6,2})$ exactly for all
large $n$. \end{problem}




\begin{remark}One difficulty for this problem is that it is not
clear how to prove \emph{the stability property}, that is, that all
almost extremal graphs have similar structure.
\end{remark}

\end{problemblock}



\begin{problemblock}

\begin{conjecture}[2.2] \[
 \pi(B_{5,5})=\frac{40}{81},
\]
and
\[
 \pi(B_{6,6})=\frac12.
\]

 \end{conjecture}




\begin{remark}The lower bounds come from a ``bipartite'' construction. It was
proved in \cite{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$.
\end{remark}

\begin{remark}
The Tur\'an density is unknown for $B_{5,3}$ and $B_{5,4}$ which is an
interesting (and perhaps tractable) open problem.
\end{remark}

\end{problemblock}



\section{Tight $5$-Cycle}

Note to the editors:  The items in this section are in the wrong order.
The next version of the code will provide an easy way to reorder the
problems in a section.



\begin{problemblock}Mubayi and R\"odl~\cite{mubayi+rodl:02} have given bounds on
$\pi(C_5^3)$, where $C_5^3$ is the tight $3$-graph $5$-cycle:
 $$
 C_5^3=\{123,234,345,451,512\}.
 $$
 In particular, the lower bound $\pi(C_5^3)\ge 2\sqrt3-3$ comes from the
following construction: partition the vertex set into two parts $A$ and $B$, take all triples that intersect $A$ precisely in $2$ vertices, and
recursively repeat this construction within $B$. Finding the optimal ratio
between $|A|$ and $|B|$ gives the required.
Razborov's~\cite{razborov:10} flag algebra computations showed that
$\pi(C_5^3)< 0.4683$ (note that $2\sqrt3-3=0.4641...$). This makes the following
conjecture plausible.


\begin{conjecture}[3.1] $\pi(C_5^3)=2\sqrt3-3$  \end{conjecture}




\end{problemblock}



\begin{problemblock}
\name{Tight $5$-Cycle Minus an Edge}
Let the $3$-graph $C_5^-$ be obtained from $C_5^3$ by removing one
edge. An example of a $C_5^-$-free $3$-graph can be obtained by taking
a complete $3$-partite $3$-graph and repeating this construction
recursively within each of the three parts. This gives density $1/4$
in the limit.


\begin{conjecture}[3.2] $\pi(C_5^-)=1/4$. \end{conjecture}




\end{problemblock}



\section{Ruzsa-Szemer\'edi Theorem and Relatives}

Let the $3$-graph $C_5^-$ be obtained from $C_5^3$ by removing one
edge. An example of a $C_5^-$-free $3$-graph can be obtained by taking
a complete $3$-partite $3$-graph and repeating this construction
recursively within each of the three parts. This gives density $1/4$
in the limit.




\begin{problemblock}

\begin{conjecture}[4.1]  For any $r\ge 3$ and $s\ge 4$ we have
 $$
 f^r(n,s(r-2)+3,s)=o(n^2).
 $$
 \end{conjecture}




\begin{remark}In~\cite{sarkozy+selkow:05} it is proved that
$f^r(n,s(r-2)+[{\log_2s}],s)=o(n^2)$. The first remaining open case is to
prove the conjecture for $f^3(n,7,4)$ (probably very hard).
\end{remark}

\begin{remark}One possible direction here is to look at multiple hypergraphs (when
the same $r$-tuple can appear a multiple number of times) and ask for
$F^r(n,p,s)$ maximum size of an $r$-multi-hypergraph such that every
$s$-set spans at most $p$ edges. See F\"uredi and
K\"undgen~\cite{furedi+kundgen:02} for results in the graph case
($r=2$).
\end{remark}

\end{problemblock}



\begin{problemblock}A related question is as follows.  Let $A$, $B$, and $C$ be disjoint
sets each of size $n$.  Let $M_1,\dots ,M_l$, be matchings, where each
edge of $M_i$ has one point in each of $A$, $B$, and $C$. The
forbidden configuration is: three edges $abc$, $a'b'c'$, $a''b''c''$
all in some $M_i$ and one edge of the form $ab'c''$ in some other
$M_j$ (that is, the edge from $M_j$ crosses the three edges of $M_i$).
Additionally, we require that the union of all matchings $M_i$ makes a
simple (linear) $3$-graph, call it $M$.


\begin{conjecture}[4.2]  $$
 |M| = o(n^2).
 $$
 \end{conjecture}




\end{problemblock}



\begin{problemblock}The following conjecture seems to be related.


\begin{conjecture}[4.3] Let $F$ be a graph and
$\alpha>1$ be such that $\operatorname{ex}(n,F)=\Omega(n^{\alpha}$).  Then for any
$\epsilon > 0$ there is $n_0$ so that if $n > n_0$ and a
graph $H$ is the edge-disjoint union of $m=\lceil \epsilon
n^{\alpha}\rceil$ copies of $F$, then $H$ contains another copy of $F$
(i.e.\ has at least $m+1$ copies of $F$). \end{conjecture}




\end{problemblock}





\begin{thebibliography}{99}

\end{thebibliography}


\end{document}
