zbMATH — the first resource for mathematics

Subgraphs in non-uniform random hypergraphs. (English) Zbl 1398.05180
Bonato, Anthony (ed.) et al., Algorithms and models for the web graph. 13th international workshop, WAW 2016, Montreal, QC, Canada, December 14–15, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-49786-0/pbk; 978-3-319-49787-7/ebook). Lecture Notes in Computer Science 10088, 140-151 (2016).
Summary: Myriad problems can be described in hypergraph terms. However, the theory and tools are not sufficiently developed to allow most problems to be tackled directly within this context. The main purpose of this paper is to increase the awareness of this important gap and to encourage the development of this formal theory, in conjunction with the consideration of concrete applications. As a starting point, we concentrate on the problem of finding (small) subhypergraphs in a (large) hypergraph. Many existing algorithms reduce this problem to the known territory of graph theory by considering the 2-section graph. We argue that this is not the right approach, neither from a theoretical point of view (by considering a generalization of the classic model of binomial random graphs to hypergraphs) nor from a practical one (by performing experiments on two datasets).
For the entire collection see [Zbl 1350.68010].
05C80 Random graphs (graph-theoretic aspects)
05C65 Hypergraphs
Full Text: DOI