Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.03906 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910290083315712 |
|---|---|
| author | Zhang, Xiande Zhong, Wenjie |
| author_facet | Zhang, Xiande Zhong, Wenjie |
| contents | For a given $n$, what is the smallest number $k$ such that every sequence of length $n$ is determined by the multiset of all its $k$-subsequences? This is called the $k$-deck problem for sequence reconstruction, and has been generalized to the two-dimensional case -- reconstruction of $n\times n$-matrices from submatrices. Previous works show that the smallest $k$ is at most $O(n^\frac{1}{2})$ for sequences and at most $O(n^\frac{2}{3})$ for matrices. We study this $k$-deck problem for general dimension $d$ and prove that, the smallest $k$ is at most $O(n^\frac{d}{d+1})$ for reconstructing a $d$ dimensional hypermatrix of order $n$ from the multiset of all its subhypermatrices of order $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_03906 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reconstruction of hypermatrices from subhypermatrices Zhang, Xiande Zhong, Wenjie Combinatorics For a given $n$, what is the smallest number $k$ such that every sequence of length $n$ is determined by the multiset of all its $k$-subsequences? This is called the $k$-deck problem for sequence reconstruction, and has been generalized to the two-dimensional case -- reconstruction of $n\times n$-matrices from submatrices. Previous works show that the smallest $k$ is at most $O(n^\frac{1}{2})$ for sequences and at most $O(n^\frac{2}{3})$ for matrices. We study this $k$-deck problem for general dimension $d$ and prove that, the smallest $k$ is at most $O(n^\frac{d}{d+1})$ for reconstructing a $d$ dimensional hypermatrix of order $n$ from the multiset of all its subhypermatrices of order $k$. |
| title | Reconstruction of hypermatrices from subhypermatrices |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.03906 |