Hypergraphs and a functional equation of Bouwkamp and de Bruijn

Abstract: We show that a 1969 result of Bouwkamp and de Bruijn on a formal power series expansion can be interpreted as the hypergraph analogue of the fact that every connected graph with n vertices has at least n-1 edges. We explain some of Bouwkamp and de Bruijn's formulas in terms of hypertrees and we use Lagrange inversion to count hypertrees by the number of vertices and the number of edges of a specified size.

Review text

\textit{C. J. Bouwkamp} and \textit{N. G. de Bruijn} [Nederl. Akad. Wet., Proc., Ser. A 72, 301--308 (1969; Zbl 0179.34601)] found that for any given power series \(\Phi(u,v)=\sum_{m=0}^\infty \sum_{n=0}^\infty c_{mn} u^mv^n\), there exists a power series \(\Psi(u,v)\) satisfying the equation \(t\Psi(tz,z)=\log (\sum_{k=0}^\infty {t^k\over k!} \exp(k\Phi(kz,z)))\). The paper under review relates this result to the theory of exponential generating functions and enumeration of hypertrees.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Hypergraphs and a functional equation of Bouwkamp and de Bruijn

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q556860)