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
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