The existence of k-radius sequences

DOI10.1016/J.JCTA.2011.08.004zbMATH Open1238.05182arXiv1101.1172OpenAlexW1665464119MaRDI QIDQ645973FDOQ645973

Authors: Simon R. Blackburn 

Publication date: 11 November 2011

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

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.

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

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

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)

Cites Work

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

Cited In (16)

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

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)