Characterization and Reconstruction of Hypergraphic Pattern Sequences

The notion of hypergraph has been introduced as a generalization of graphs so that each hyperedge is a subset of the set of vertices, without constraints on its cardinality. Our study focuses on 3-uniform hypergraphs, i.e., those hypergraphs whose (hyper)edges have three as common cardinality. A widely investigated problem related both to graphs and to hypergraphs concerns their characterization and reconstruction from their degree sequences. Concerning graphs, this problem has been efficiently solved in 1960 by Erdös and Gallai, while no efficient solutions are possible in the case of hypergraphs, even in the simple case of 3-uniform hypergraphs, as shown in 2018 by Deza et al. [4]. These problems are among the most studied in the field of Discrete Tomography (see [11, 12] for a complete survey) and, in a more general fashion, of Image Analysis. So, to reduce the NP-hard core of the hypergraph reconstruction problem, we consider a class of degree sequences defined in [4] that show interesting properties. Here, in particular, we characterize the subclass P by using the new notion of pattern and pattern sequence. First, we focus on t-pattern sequences, i.e., sequences with constant pattern t>=1, and we study the remarkable behaviour of their last elements, called tails. In particular, for any fixed t, we show that the tails tend to a fixed point when increasing the sequences’ lengths. The elements of these fixed points, on varying t, are the same and form the sequence A002620 in [13], generalizing the results in [6]. Finally, we provide a fast algorithm to reconstruct the hypergraphs that realize the sequences in P by iteratively discovering the elements of the characterizing pattern sequence.