Turán densities are rational

A hypergraph \( H\) consists of a vertex set \( V\) together with a family \( E\) of subsets of \( V\), which are called the edges of \( H\). A \( r\)-uniform hypergraph, or \( r\)-graph, for short, is a hypergraph whose edge set consists of \( r\)-subsets of \( V\). A graph is just a special case of an \( r\)-graph with \( r=2\).

For a finite family \( \mathcal F\) of \( r\)-graphs, one can define the Turán number \( t_r(n,{\mathcal F})\) to be the largest integer \( t\) such that there is an \( r\)-graph on \( n\) vertices with \( t\) edges which does not contain any \( F \in {\mathcal F}\) as a subgraph.

Let \( \mathcal F\) be a collection of \( r\)-graphs. For an \( r\)-graph \( H\), we say \( H\) is \( \mathcal F\)-free if \( H\) contains no copy of any \( F \in {\mathcal F}\). It is not hard to show the existence of the limit

\(\displaystyle \pi({\mathcal F}) = \lim_{n \rightarrow \infty} \frac { t(n,{\mathcal F})} {\binom{n}{r}}. \)

However, it is quite difficult in general to determine the value of \( \pi({\mathcal F})\) for specific choices of \( \mathcal F\).

Suppose \( \mathcal F\) consists of a single \( r\)-partite \( r\)-graph \( H\) with vertex set \( \cup_{i=1}^r A_i\) and \( \vert A_i\vert=t_i\). Erdös [1], [3] proved that

\begin{equation} t_r(n, H) \leq c n^{k-(t_1+\ldots+t_r)/(t_1\ldots t_r)} \end{equation}

where \( c\) is a constant depending only on \( r\) and the \( t_i\)'s.

If \( \mathcal F\) contains an \( r\)-partite \( r\)-graph, then (1) implies that \( \pi({\mathcal F})= 0\). If no member of \( \mathcal F\) is \( r\)-partite, then we have

\(\displaystyle \pi({\mathcal F}) \geq \frac{r!}{r^r} \)

since the \( r\)-partite \( r\)-graph on \( n\) vertices with all parts having almost equal sizes does not contain any member of \( \mathcal F\).

Erdös conjectured that for every fixed \( r\), the set \( \{ \pi(G): G\)    is an \( r\)-graph\( \}\) forms a discrete set. However, the celebrated result of Frankl and Rödl [4] shows that this is not true (for \( r \geq 3\), of course).

For the case \( r=2\), a classic result of Erdös, Stone and Simonovits [2], [5] shows that

\(\displaystyle \pi({\mathcal F}) = 1 - \frac 1 k \)

where \( k = -1 + \min \{ \chi(F) : F \in {\mathcal F} \} \geq 1\).

Conjecture

\(\pi({\mathcal F})\) is rational for any finite family \(\mathcal F\).


Bibliography
1 P. Erdös. On extremal problems of graphs and generalized graphs. Israel J. Math. 2 (1964), 183-190.

2 P. Erdös and A. H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946), 1087-1091.

3 Z. Füredi, Turán type problems, Surveys in Combinatorics, 1991 (Guildford, 1991), London Math. Soc. Lecture Notes Series 166, 253-300, Cambridge Univ. Press, Cambridge, 1991.

4 P. Frankl and V. Rödl, Hypergraphs do not jump, Combinatorica 4 (1984), 149-159.

5 P. Erdös and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966), 51-57.