# Turán's problem for hypergraphs

 Importance: Medium ✭✭
 Author(s): Turan, Paul
 Subject: Graph Theory » Hypergraphs
 Keywords:
 Posted by: fhavet on: March 12th, 2013
Conjecture   Every simple -uniform hypergraph on vertices which contains no complete -uniform hypergraph on four vertices has at most hyperedges.
Conjecture   Every simple -uniform hypergraph on vertices which contains no complete -uniform hypergraph on five vertices has at most hyperedges.

Let be an -set. A -uniform hypergraph is complete if , the set of all -subsets of .

Let be a partition of into three sets which are as nearly equal in size as possible, and let be the union of , , , and . This -uniform hypergraph has hyperedges and contains no complete -uniform hypergraph on four vertices. Hence the first conjecture asserts that this hypergraph is extremal with this prpoerty.

Let be a partition of into two sets which are as nearly equal in size as possible, and let be the set of all -subsets of which intersect both and . This -uniform hypergraph has hyperedges and contains no complete -uniform hypergraph on five vertices. Hence the second conjecture asserts that this hypergraph is extremal with this property.

## Bibliography

*[T] P. Turán, Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48 (1941), 436--452.

* indicates original appearance(s) of problem.