On the number of copies of one hypergraph in another (Q1264288): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 10:37, 31 January 2024
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