Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2411.12718 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912126814126080 |
|---|---|
| author | Ma, Yiming Zhong, Wenjie Zhang, Xiande |
| author_facet | Ma, Yiming Zhong, Wenjie Zhang, Xiande |
| contents | We study the reconstruction problem of permutation sequences from their $k$-minors, which are subsequences of length $k$ with entries renumbered by $1,2,\ldots,k$ preserving order. We prove that the minimum number $k$ such that any permutation of length $n$ can be reconstructed from the multiset of its $k$-minors is between $\exp{(Ω(\sqrt{\ln n}))}$ and $O(\sqrt{n\ln n})$. These results imply better bounds of a well-studied parameter $N_d$, which is the smallest number such that any permutation of length $n\ge N_d$ can be reconstructed by its $(n-d)$-minors. The new bounds are $ d+\exp(Ω(\sqrt{\ln d}))<N_d<d+O(\sqrt{d\ln d})$ asymptotically, and the previous bounds were $d+\log_2 d<N_d<d^2/4+2d+4$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_12718 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improvements on Permutation Reconstruction from Minors Ma, Yiming Zhong, Wenjie Zhang, Xiande Combinatorics Optimization and Control We study the reconstruction problem of permutation sequences from their $k$-minors, which are subsequences of length $k$ with entries renumbered by $1,2,\ldots,k$ preserving order. We prove that the minimum number $k$ such that any permutation of length $n$ can be reconstructed from the multiset of its $k$-minors is between $\exp{(Ω(\sqrt{\ln n}))}$ and $O(\sqrt{n\ln n})$. These results imply better bounds of a well-studied parameter $N_d$, which is the smallest number such that any permutation of length $n\ge N_d$ can be reconstructed by its $(n-d)$-minors. The new bounds are $ d+\exp(Ω(\sqrt{\ln d}))<N_d<d+O(\sqrt{d\ln d})$ asymptotically, and the previous bounds were $d+\log_2 d<N_d<d^2/4+2d+4$. |
| title | Improvements on Permutation Reconstruction from Minors |
| topic | Combinatorics Optimization and Control |
| url | https://arxiv.org/abs/2411.12718 |