Hypergraph Turán problem

$\newcommand{\Cat}{{\rm Cat}}$

$\newcommand{\A}{\mathcal A}$

$\newcommand{\freestar}{ \framebox[7pt]{$\star$} }$

Hypergraph Turán problem

Edited by Dhruv Mubayi, Oleg Pikhurko, and Benny Sudakov

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

Sections

Bibliography

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