On the number of copies of one hypergraph in another (Q1264288)

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 1195651
Language Label Description Also known as
default for all languages
No label defined
    English
    On the number of copies of one hypergraph in another
    scientific article; zbMATH DE number 1195651

      Statements

      On the number of copies of one hypergraph in another (English)
      0 references
      0 references
      0 references
      14 January 1999
      0 references
      For two given hypergraphs \(H\) and \(G\), let \(N(C,H)\) denote the number of subhypergraphs of \(G\) isomorphic to \(H\), and let \(N(\ell, H)\) denote the maximum of \(N(G,H)\), taken over all \(G\) with exactly \(\ell\) edges. Let \(E\) be the set of edges of \(H\) and let \(V\) be a set of vertices of \(H\). A fractional cover of \(H\) is a mapping \(\phi: E \rightarrow [0,1]\) such that \(\sum_{e \owns v} \phi(e) \geq 1 \) for each \( v \in V\). The fractional cover number of \(H\) , \(\rho^*(H) \), is the minimum over the fractional covers \(\phi\) of \(\sum_{e \in E}\phi(e) \). The authors show that for given \(H\), the growth of \(N(\ell,H)\) is basically a function of \(\rho^*(H)\), that is, \(N(\ell,H) = \theta(\rho^*(H))\). For graphs this was shown by \textit{N. Alon} [Isr. J. Math. 38, 116-130 (1981; Zbl 0472.05034)].
      0 references
      hypergraph
      0 references
      edge cover
      0 references
      fractional cover
      0 references
      0 references

      Identifiers