No label defined (Q3679225)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3900799
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3900799

      Statements

      1984
      0 references
      supersaturated graphs
      0 references
      Turán-type problems
      0 references
      0 references
      0 references
      [For the entire collection see Zbl 0546.00007.] For a graph \(H\) and an integer \(n\geq 1\), let \(\text{ex}(n,H)\) denote the maximum number of edges of a graph \(G\) on \(n\) vertices that contains no copy of \(H\). This paper considers the following conjecture: for every graph \(H\) with \(v\) vertices and \(e\) edges and for every \(c>0\), there is a constant \(d>0\) such that every graph \(G\) on \(n\) vertices with \(E\geq (1+c)\text{ex}(n,H)\) edges contains at least \(d\cdot E^e/n^{2e-v}\) copies of \(H\). This conjecture holds for every nonbipartite H by the results of the authors [Combinatorica 3, 181-192 (1983; Zbl 0529.05027)]. (See also [\textit{P. Frankl} and \textit{V. Rödl}, Hypergraphs do not jump, ibid. 4, 149-159 (1984)].) If true, the conjecture is best possible. This interesting paper proves the conjecture and some related results for various special cases.
      0 references

      Identifiers