Combinatorial Properties of Degree Sequences of 3-Uniform Hypergraphs Arising from Saind Arrays

The characterization of k-uniform hypergraphs by their degree sequences, say k-sequences, has been a longstanding open problem for k >= 3. Very recently its decision version was proved to be NP-complete in [3]. In this paper, we consider Saind arrays S-n of length 3n -1, i.e. arrays (n, n -1, n-2,..., 2 - 2n), and we compute the related 3-uniform hypergraphs incidence matrices M-n as in [3], where, for any M-n the array of column sums, pi(n) turns out to be the degree sequence of the corresponding 3-uniform hypergraph. We show that, for a generic n >= 2, pi(n) and pi(n + 1) 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.