The characterization of k-uniform hypergraphs by their degree sequences, say k-sequences, has been a longstanding open problem for. Very recently its decision version was proved to be NP-complete in [3]. In this paper, we consider Saind arrays of length, i.e. arrays, and we compute the related 3-uniform hypergraphs incidence matrices as in [3], where, for any, the array of column sums, turns out to be the degree sequence of the corresponding 3-uniform hypergraph. We show that, for a generic and share the same entries starting from an index on. Furthermore, increasing n, these common entries give rise to the integer sequence A002620 in [15]. We prove this statement introducing the notion of queue-triad of size n and pointer k. Sequence A002620 is known to enumerate several combinatorial structures, including symmetric Dyck paths with three peaks, some families of integers partitions in two parts, bracelets with beads in three colours satisfying certain constraints, and special kind of genotype frequency vectors. We define bijections between queue triads and the above mentioned combinatorial families, thus showing an innovative approach to the study of 3-hypergraphic sequences which should provide subclasses of 3-uniform hypergraphs polynomially reconstructable from their degree sequences.
Frosini, A., Palma, G., Rinaldi, S. (2020). Combinatorial Properties of Degree Sequences of 3-Uniform Hypergraphs Arising from Saind Arrays. In Beyond the Horizon of Computability. CiE 2020 (pp.228-238). Cham : Springer [10.1007/978-3-030-51466-2_20].
Combinatorial Properties of Degree Sequences of 3-Uniform Hypergraphs Arising from Saind Arrays
Palma G.;Rinaldi S.
2020-01-01
Abstract
The characterization of k-uniform hypergraphs by their degree sequences, say k-sequences, has been a longstanding open problem for. Very recently its decision version was proved to be NP-complete in [3]. In this paper, we consider Saind arrays of length, i.e. arrays, and we compute the related 3-uniform hypergraphs incidence matrices as in [3], where, for any, the array of column sums, turns out to be the degree sequence of the corresponding 3-uniform hypergraph. We show that, for a generic and share the same entries starting from an index on. Furthermore, increasing n, these common entries give rise to the integer sequence A002620 in [15]. We prove this statement introducing the notion of queue-triad of size n and pointer k. Sequence A002620 is known to enumerate several combinatorial structures, including symmetric Dyck paths with three peaks, some families of integers partitions in two parts, bracelets with beads in three colours satisfying certain constraints, and special kind of genotype frequency vectors. We define bijections between queue triads and the above mentioned combinatorial families, thus showing an innovative approach to the study of 3-hypergraphic sequences which should provide subclasses of 3-uniform hypergraphs polynomially reconstructable from their degree sequences.File | Dimensione | Formato | |
---|---|---|---|
978-3-030-51466-2_20.pdf
non disponibili
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
359.03 kB
Formato
Adobe PDF
|
359.03 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/1253608