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

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the number of copies of one hypergraph in another
scientific article

    Statements

    On the number of copies of one hypergraph in another (English)
    0 references
    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
    0 references
    hypergraph
    0 references
    edge cover
    0 references
    fractional cover
    0 references
    0 references