Article ID Journal Published Year Pages File Type
4649327 Discrete Mathematics 2009 13 Pages PDF
Abstract

Estimating Turán densities of hypergraphs is believed to be one of the most challenging problems in extremal set theory. The concept of ‘jump’ concerns the distribution of Turán densities. A number α∈[0,1)α∈[0,1) is a jump for rr-uniform graphs if there exists a constant c>0c>0 such that for any family FF of rr-uniform graphs, if the Turán density of FF is greater than αα, then the Turán density of FF is at least α+cα+c. A fundamental result in extremal graph theory due to Erdős and Stone implies that every number in [0,1)[0,1) is a jump for graphs. Erdős also showed that every number in [0,r!/rr)[0,r!/rr) is a jump for rr-uniform hypergraphs. Furthermore, Frankl and Rödl showed the existence of non-jumps for hypergraphs. Recently, more non-jumps were found in [r!/rr,1)[r!/rr,1) for rr-uniform hypergraphs. But there are still a lot of unknowns regarding jumps for hypergraphs. In this paper, we propose a new but related concept–strong-jump and describe several sequences of non-strong-jumps. It might help us to understand the distribution of Turán densities for hypergraphs better by finding more non-strong-jumps.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,