Turán densities are rational
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
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
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
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
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.
|