On substructure densities of hypergraphs (Q844225)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On substructure densities of hypergraphs
scientific article

    Statements

    On substructure densities of hypergraphs (English)
    0 references
    18 January 2010
    0 references
    A real number \(\alpha \in [0, 1)\) is a jump for an integer \(r \geq 2\) if there exists \(c > 0\) such that for any \(\varepsilon > 0\) and any integer \(m \geq r\), there exists an integer \(n _{0}\) such that any \(r\)-uniform graph with \(n > n _{0}\) vertices and density at least \(\alpha + \varepsilon\) contains a subgraph with \(m\) vertices and density at least \(\alpha + c\). It follows from a fundamental theorem of Erdős and Stone that every \(\alpha \in [0, 1)\) is a jump for \(r = 2\). Erdős also showed that every number in \([0, r!/r^{r})\) is a jump for \(r \geq 3\) and asked whether every number in \([0, 1)\) is a jump for \(r \geq 3\) as well. Frankl and Rödl gave a negative answer by showing a sequence of non-jumps for every \(r \geq 3\). Recently, more non-jumps were found for some \(r \geq 3\). But there are still a lot of unknowns on determining which numbers are jumps for \(r \geq 3\). The set of all previous known non-jumps for \(r = 3\) has only an accumulation point at 1. In this paper, we give a sequence of non-jumps having an accumulation point other than 1 for every \(r \geq 3\). It generalizes the main result in the paper `A note on the jumping constant conjecture of Erdős' by \textit{P. Frankl, Y. Peng, V. Rödl} and \textit{J. Talbot} published in [J. Comb. Theory, Ser. B 97, No. 2, 204--216 (2007; Zbl 1110.05052)].
    0 references
    extremal problems in hypergraphs
    0 references
    Turán density
    0 references
    Erdős jumping constant conjecture
    0 references
    0 references

    Identifiers