The existence of k-radius sequences

DOI10.1016/J.JCTA.2011.08.004MaRDI QIDQ645973zbMATHOpenAlexFDO

Authors Simon R. Blackburn

Publication date 11 November 2011

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-radius sequencematchings in quasi-random hypergraphssequence design

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $n$ and $k$ be positive integers, and let $F$ be an alphabet of size $n$. A sequence over $F$ of length $m$ is a emph{$k$-radius sequence} if any two distinct elements of $F$ occur within distance $k$ of each other somewhere in the sequence. These sequences were introduced by Jaromczyk and Lonc in 2004, in order to produce an efficient caching strategy when computing certain functions on large data sets such as medical images. Let $f_k(n)$ be the length of the shortest $n$-ary $k$-radius sequence. The paper shows, using a probabilistic argument, that whenever $k$ is fixed and $nightarrowinfty$ [ f_k(n)sim frac{1}{k}�inom{n}{2}. ] The paper observes that the same argument generalises to the situation when we require the following stronger property for some integer $t$ such that $2leqtleqk+1$: any $t$ distinct elements of $F$ must simultaneously occur within a distance $k$ of each other somewhere in the sequence.

Recommendations

• Constructing \(k\)-radius sequences
• Constructions of asymptotically shortest \(k\)-radius sequences
• Constructing optimal \(k\)-radius sequences
• Note on a construction of short \(k\)-radius sequences
• Packing analogue of k-radius sequences

Cites work

• scientific article; zbMATH DE number 3868663 (Why is no real title available?)
• Asymptotic behavior of the chromatic index for hypergraphs
• Consecutive storage of relevant records with redundancy
• Constructing \(k\)-radius sequences
• Constructions of asymptotically shortest \(k\)-radius sequences
• Matchings and covers in hypergraphs
• Near perfect coverings in graphs and hypergraphs
• Near-universal cycles for subsets exist
• On Universal Cycles for k-Subsets of an n-Set
• On a packing and covering problem
• Sequences of Radius k: How to Fetch Many Huge Objects into Small Memory for Pairwise Computations
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Universal cycles for combinatorial structures
• Universal cycles for minimum coverings of pairs by triples, with application to 2-radius sequences
• Universal cycles of \(k\)-subsets and \(k\)-permutations

Cited in

(16)

• Sequences of large radius
• Sequences of Radius k: How to Fetch Many Huge Objects into Small Memory for Pairwise Computations
• Harmonious and achromatic colorings of fragmentable hypergraphs
• Splitter Sets and $k$ -Radius Sequences
• Achromatic and harmonious colorings of circulant graphs
• Constructions of asymptotically shortest \(k\)-radius sequences
• Note on a construction of short \(k\)-radius sequences
• Constructing optimal \(k\)-radius sequences
• Harmonious and achromatic colorings of fragmentable hypergraphs
• Constructing \(k\)-radius sequences
• Sequences of radius \(k\) for complete bipartite graphs
• Universal cycle packings and coverings for \(k\)-subsets of an \(n\)-set
• Sequences of radius \(k\) for complete bipartite graphs
• Packing analogue of \(k\)-radius sequences
• Short k‐radius sequences, k‐difference sequences and universal cycles
• Euler tours in hypergraphs

This page was built for publication: The existence of \(k\)-radius sequences

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