On the reconstruction of 3-uniform hypergraphs from step-two degree sequences (Q2061815)

A necessary and sufficient condition for a nonnegative integer sequence $\pi$ to be the degree sequence of a $k$-hypergraph, for $k\geq 3$, is available in the literature. It depends on a recursive decomposition of $\pi$ suggested by \textit{A. K. Dewdney} [Proc. Am. Math. Soc. 53, 535--540 (1975; Zbl 0323.05137)]. However, the task of determining a practical characterization eluded us for quite some time. \textit{S. Brlek} and \textit{A. Frosini} [Lect. Notes Comput. Sci. 9647, 95--104 (2016; Zbl 1430.94010)] proposed a $P$-time reconstruction algorithm for the homogenous $k$-sequences and then it was extended to step-one $k$-sequences by \textit{A. Frosini} et al. [ibid. 7749, 300--310 (2013; Zbl 1382.68260)]. In this paper, the authors extend the result by focusing on the class of step-two 3-sequences and prove that such a condition is not sufficient anymore. They also remark that changing from step one to step two 3-sequences is critical for the reconstruction of the related 3-hypergraph. So they first define a series of step-two 3-sequences that are used as starting point in the final reconstruction algorithm. They demonstrate how to identify a 3-hypergraph solution related to the given 3-sequence using as edges the cyclic shifts of 3-dense Lyndon words. This work is really interesting and it would pave the way for more fruitful results in this direction. For the entire collection see [Zbl 1476.68014].