Perfect sequence covering arrays

DOI10.1007/S10623-019-00698-7MaRDI QIDQ2302158zbMATH OpenOpenAlexFDO

Authors Raphael Yuster

Publication date 25 February 2020

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.08914

zbMATH Keywords

completely scrambling set of permutationscovering arraydirected \(t\)-designsequence covering array

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Orthogonal arrays, Latin squares, Room squares (05B15) Other designs, configurations (05B30) Combinatorial aspects of packing and covering (05B40)

Abstract: An $(n,k)$ sequence covering array is a set of permutations of $[n]$ such that each sequence of $k$ distinct elements of $[n]$ is a subsequence of at least one of the permutations. An $(n,k)$ sequence covering array is perfect if there is a positive integer $lambda$ such that each sequence of $k$ distinct elements of $[n]$ is a subsequence of precisely $lambda$ of the permutations. While relatively close upper and lower bounds for the minimum size of a sequence covering array are known, this is not the case for perfect sequence covering arrays. Here we present new nontrivial bounds for the latter. In particular, for $k=3$ we obtain a linear lower bound and an almost linear upper bound.

Recommendations

• Growth of the perfect sequence covering array number
• A group-based structure for perfect sequence covering arrays
• Sequence covering arrays
• Sequence Covering Arrays and Linear Extensions
• scientific article; zbMATH DE number 861356

Cites work

• A Certain Class of Incidence Matrices
• A diagonal form for the incidence matrices of t-subsets vs. k- subsets
• A note on scrambling permutations
• An extremal problem of \(d\) permutations containing every permutation of every \(t\) elements
• Containment problems in high-dimensional spaces
• Directed t-packings and directed t-Steiner systems
• scientific article; zbMATH DE number 525969 (Why is no real title available?)
• Minimal scrambling sets of simple orders
• On the minimum number of completely 3-scrambling permutations
• Scrambling permutations and entropy of hypergraphs
• Sequence covering arrays
• The difference between consecutive primes. II

Cited in

(12)

• A group-based structure for perfect sequence covering arrays
• Growth of the perfect sequence covering array number
• Sequence Covering Arrays and Linear Extensions
• Suitable permutations, binary covering arrays, and Paley matrices
• scientific article; zbMATH DE number 861356 (Why is no real title available?)
• Sequence covering arrays
• On perfect sequence covering arrays
• A polynomial construction of perfect sequence covering arrays
• Perfect and nearly perfect separation dimension of complete and random graphs
• Excess coverage arrays and Levenshtein's conjecture
• Explicit and near-optimal construction of t-rankwise independent permutations
• Algebraic and SAT models for SCA generation

This page was built for publication: Perfect sequence covering arrays

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2302158)