| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

Hypergraph Turán problem

Edited by org.aimpl.user:bsudakov@math.ucla.edu, org.aimpl.user:mubayi@math.uic.edu, and org.aimpl.user:pikhurko@cmu.edu

Here we present a selection of some open questions related to the hypergraph Turán 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 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 Turán 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án [turan:41]. The Turán 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üredi [furedi:91], Sidorenko [sidorenko:95], and Keevash [keevash:survey].


    1. Bibliography

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