Result: A hypergraph extension of Turán's theorem

Title:
A hypergraph extension of Turán's theorem
Authors:
Source:
Journal of Combinatorial Theory, Series B. 96:122-134
Publisher Information:
Elsevier BV, 2006.
Publication Year:
2006
Document Type:
Academic journal Article
File Description:
application/xml
Language:
English
ISSN:
0095-8956
DOI:
10.1016/j.jctb.2005.06.013
Rights:
Elsevier Non-Commercial
Accession Number:
edsair.doi.dedup.....d3e750bfe6e8e88ffd3ccadb4fb2ead5
Database:
OpenAIRE

Further Information

This paper contains several theorems on Turán-type extremal questions for \(r\)-uniform hypergraphs. The main result is that the author determines the Turán density of the \(r\)-uniform hypergraph that results from the complete graph \(K_l\) by adding to each edge \(r-2\) new vertices, with these new vertices all distinct, so the \(r\)-uniform hypergraph has \((r-2){l\choose2} + l\) vertices and \({l\choose 2}\) hyperedges. It is shown that the maximum number of edges in an \(r\)-uniform hypergraph without this subhypergraph is \({(l-1)_r\over(l-1)^r}{n\choose r} + o(n^r)\). The author shows also a stability version of this result similar to Simonovits stability theorem: A hypergraph which does not contain this subgraph, and is within \(\varepsilon n^r\) edges of that maximum edge number, can be converted to the extremal graph by changing \(\delta(\varepsilon)n^r\) edges.