Description
Abstract:
A 3-uniform hypergraph is a generalization of simple graphs where each hyperedge is a subset of vertices of size 3. The degree of a vertex in a hypergraph is the number of hyperedges incident to it. The degree sequence of a hypergraph is the sequence of the degrees of its vertices. The degree sequence problem for 3-uniform hypergraphs is to decide if a 3-uniform hypergraph exists with a prescribed degree sequence. Such a hypergraph is called a realization. Recently, Deza et al. proved that the degree sequence problem for 3-uniform hypergraphs is NP-complete. Some special cases are easy; however, polynomial algorithms were known so far only for some very restricted degree sequences. The main result of our research is the following. If all degrees are between $\frac{2n^2}{63}+O(n)$ and $\frac{5n^2}{63}-O(n)$ in a degree sequence D, further, the number of vertices is at least 45, and the sum of the degrees can be divided by 3, then D has a 3-uniform hypergraph realization. Our proof is constructive and in fact, it constructs a hypergraph realization in polynomial time for any degree sequence satisfying the above-mentioned properties. To our best knowledge, this is the first polynomial running time algorithm to construct a 3-uniform hypergraph realization of a highly irregular and dense degree sequence.
Joint work with former BSM student, Runze Li.