Istrate's scaling conjecture for heapable subsequences
Statement
Let
be a uniformly random permutation of $[n]$, and let $MHS_k$ denote the minimum number of max $k$-heapable subsequences into whichcan be partitioned. For each integer , the normalized expected number of heaps is considered as tends to infinity.
Istrate's scaling conjecture. For every k\boldsymbol{ there exists such that, as n\to\boldsymbol{\frac{E[MHS_k]}{(n)} converges to . Moreover, is the golden ratio.
The conjecture concerns the logarithmic scaling of the minimum number of heapable subsequences in a random permutation. The existence of was subsequently proved, so the claim is solved; the golden-ratio value for is included in the resolved statement.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.