Cyclic sequences of \(k\)-subsets with distinct consecutive unions (Q2468032)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cyclic sequences of \(k\)-subsets with distinct consecutive unions |
scientific article |
Statements
Cyclic sequences of \(k\)-subsets with distinct consecutive unions (English)
0 references
30 January 2008
0 references
The paper investigates cyclic sequences, whose elements are \(k\)-subsets of the underlying set \(\{0,1,2,\dots,n-1\}\). The sequence must not repeat any \(k\)-subset but the pairs of consecutive \(k\)-subsets must all yield distinct unions. The problem is whether such cyclic sequences exist, under the extra condition that unions must belong to some given family of sets \(Y\). Notice that the famous unsolved middle two levels problem -- whether a Hamiltonian cycle exists if we restrict the hypercube graph to its two middle levels -- can easily be formulated in this context. The main interest of the paper is about \(Y=\) subsets with size congruent top \(k\) mod 2. This problem is motivated from applications in nonadaptive combinatorial group testing. The authors obtain, as a corollary, some error detecting group testing procedures.
0 references
distinct unions
0 references
group testing
0 references
middle two levels problem
0 references