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 [Formula: see text]. Very recently its decision version was proved to be NP-complete in [3]. In this paper, we consider Saind arrays [Formula: see text] of length [Formula: see text], i.e. arrays [Formula: see text], and we compute the related 3-uniform hypergraphs incidence matrices [Formula: see text] as in [3], where, for any [Formula: see text], the array of column sums, [Formula: see text] turns out to be the degree sequence of the corresponding 3-uniform hypergraph. We show that, for a generic [Formula: see text], [Formula: see text] and [Formula: see text] 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.