One Turán Type Problem on Uniform Hypergraphs

Abstract

Let n,m,p,r∈N with p≥n≥r. For a hypergraph, if each edge has r vertices, then the hypergraph is called an r-graph. Define er(n,m;p) to be the maximum number of edges of an r-graph with p vertices in which every subgraph of n vertices has at most m edges. Researching this function constitutes a Turán type problem. In this paper, on the one hand, for fixed p, we present some results about the exact values of er(n,m;p) for small m compared to n; on the other hand, for sufficient large p, we use the combinatorial technique of double counting to give an upper bound of e(n,m;p) and obtain a lower bound of er(n,m;p) by applying the lower bound of the independent set of a hypergraph.

Keywords

• Turán type problem
• extremal graph
• uniform hypergraph
• bounds