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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references