The conjecture that the reconstruction gap is unbounded

About 10 years old · traced to

Let G(n)G(n) denote the largest integer kk such that every partition of nn is uniquely determined by its multiset of kk-minors, with the precise definition of G(n)G(n) as in the paper. The quantity n−G(n)n-G(n) measures the gap between the size of the partition and the largest reconstructible minor size. Unbounded reconstruction-gap conjecture. The difference n−G(n)n-G(n) satisfies

lim⁡n→∞n−G(n)=+∞.\lim_{n \rightarrow \infty} n-G(n) = +\infty.

The paper proves that n−G(n)=O(n/log⁡n)n-G(n)=O(n/\log n), while computational results determine this difference for various values of nn. The conjecture asserts that the gap is nevertheless unbounded.

References

Primary source

Pakawut Jiradilok, “Reconstructing Partitions from their Multisets of k-Minors”, arXiv:1610.05354 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.