Upper bounds on the numbers of 1-factors and 1-factorizations of hypergraphs

Anna Taranenko

Published 2015-03-28Version 1

Hypergraph $G=(X,W)$ is called $d$-uniform if each hyperedge $w \in W$ is a set of $d$ vertices. A 1-factor of a hypergraph $G$ is a set of hyperedges such that every vertex of the hypergraph is incident to exactly one hyperedge from the set. A 1-factorization of $G$ is a partition of all hyperedges of the hypergraph into disjoint 1-factors. The adjacency matrix of a $d$-uniform hypergraph $G$ is the $d$-dimensional (0,1)-matrix of order $|X|$ describing which subsets of vertices of $G$ make a hyperedge. We estimate the number of 1-factors of uniform hypergraphs and the number of 1-factorizations of the complete uniform hypergraphs by the means of permanents of their adjacency matrices.