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.

Characterization and Reconstruction of Hypergraphic Pattern Sequences / Michela Ascolese, Andrea Frosini. - STAMPA. - (2023), pp. 301-316. (Intervento presentato al convegno 21st International Workshop on Combinatorial Image Analysis, IWCIA 2022) [10.1007/978-3-031-23612-9_19].

### Characterization and Reconstruction of Hypergraphic Pattern Sequences

#### Abstract

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.
##### Scheda breve Scheda completa Scheda completa (DC)
2023
Lecture Notes in Computer Science
21st International Workshop on Combinatorial Image Analysis, IWCIA 2022
Michela Ascolese, Andrea Frosini
File in questo prodotto:
File
paper6.pdf

Accesso chiuso

Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: Tutti i diritti riservati
Dimensione 346.73 kB
Utilizza questo identificatore per citare o creare un link a questa risorsa: `https://hdl.handle.net/2158/1346952`