On substructure densities of hypergraphs (Q844225)

From MaRDI portal
Revision as of 03:29, 20 March 2024 by Openalex240319060354 (talk | contribs) (Set OpenAlex properties.)
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
    0 references
    0 references
    0 references
    0 references
    extremal problems in hypergraphs
    0 references
    Turán density
    0 references
    Erdős jumping constant conjecture
    0 references
    0 references
    0 references