Turánnical hypergraphs

Details Turánnical hypergraphs Turánnical hypergraphs

2010-11-05

arxiv.org/abs/1011.1483v2

Mathematics

Combinatorics

33 pages, minor improvements thanks to two referees

Scientific paper

This paper is motivated by the question of how global and dense restriction sets in results from extremal combinatorics can be replaced by less global and sparser ones. The result we consider here as an example is Turan's theorem, which deals with graphs G=([n],E) such that no member of the restriction set consisting of all r-tuples on [n] induces a copy of K_r. Firstly, we examine what happens when this restriction set is replaced just by all r-tuples touching a given m-element set. That is, we determine the maximal number of edges in an n-vertex such that no K_r hits a given vertex set. Secondly, we consider sparse random restriction sets. An r-uniform hypergraph R on vertex set [n] is called Turannical (respectively epsilon-Turannical), if for any graph G on [n] with more edges than the Turan number ex(n,K_r) (respectively (1+\eps)ex(n,K_r), no hyperedge of R induces a copy of K_r in G. We determine the thresholds for random r-uniform hypergraphs to be Turannical and to epsilon-Turannical. Thirdly, we transfer this result to sparse random graphs, using techniques recently developed by Schacht [Extremal results for random discrete structures] to prove the Kohayakawa-Luczak-Rodl Conjecture on Turan's theorem in random graphs.

Affiliated with

Also associated with

No associations

Rating

Turánnical hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Turánnical hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Turánnical hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-455955