On the reconstruction of 3-uniform hypergraphs from step-two degree sequences
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].
- New sufficient conditions on the degree sequences of uniform hypergraphs
- On the Degree Sequence of 3-Uniform Hypergraph: A New Sufficient Condition
- Properties of unique degree sequences of 3-uniform hypergraphs
- On the degree sequences of uniform hypergraphs
- scientific article; zbMATH DE number 4200248
- A fast algorithm to generate necklaces with fixed content
- A tomographical interpretation of a sufficient condition on h-graphical sequences
- An Efficient Algorithm for Generating Necklaces with Fixed Density
- Degree Sequences in Complexes and Hypergraphs
- scientific article; zbMATH DE number 3169205 (Why is no real title available?)
- scientific article; zbMATH DE number 43754 (Why is no real title available?)
- On the degree sequences of uniform hypergraphs
- Optimization over degree sequences
- Some NP-complete problems for hypergraph degree sequences
- A family of non-reconstructible hypergraphs
- Nonconvexity of the set of hypergraph degree sequences
- Properties of unique degree sequences of 3-uniform hypergraphs
- Combinatorial properties of degree sequences of 3-uniform hypergraphs arising from Saind arrays
- Weighted 2-sections and hypergraph reconstruction
- Hypergraph recovery algorithms from a given vector of vertex degrees
- Reconstructing 2-complexes by a nonnegative integer-valued vector
- On the reconstruction of 3-uniform hypergraphs from degree sequences of span-two
- A simple formulation of the Boesch-Harary theorem on 2-graphic lists
- New results on degree sequences of uniform hypergraphs
- On the degree sequences of uniform hypergraphs
- On the Degree Sequence of 3-Uniform Hypergraph: A New Sufficient Condition
- A tomographical interpretation of a sufficient condition on h-graphical sequences
- Characterization and reconstruction of hypergraphic pattern sequences
- New sufficient conditions on the degree sequences of uniform hypergraphs
This page was built for publication: On the reconstruction of 3-uniform hypergraphs from step-two degree sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2061815)
