Regarding the case of uniform distribution on cladograms, one can construct a common substructure via the recursive decomposition at the centroid of the limiting CRT. Heuristically, the size of this structure will grow as \( Z n^\gamma\), where the distribution of \(Z\) and the constant \( \gamma\) satisfy $$ Z =_d \sum_{i=1}^3 (X_iY_i)^\gamma Z_i .$$ Here \(X_1 > X_2 > X_3 \) are the ordered rearrangement of \( (X_1, X_2, X_3) \) with the Dirichlet \( (-1/2, -1/2, -1/2) \) distribution on the restricted simplex \( \{ x_1 + x_2 + x_3 = 1, \ \max_i x_i < 1/2\} \), that is with density \( (12 \pi)^{-1}(x_1x_2x_3)^{-3/2} \); and \(Y_1 > Y_2 > Y_3 \) is an independent copy of \(X_1 > X_2 > X_3 \); and \(Z_1, Z_2, Z_3\) are independent with the distribution of \(Z\). In particular this implies that \(\gamma \) must be the solution of $$ \mathbb{E} \large[\sum_{i=1}^3 (X_iY_i)^\gamma \large] = 1 .$$ Simulations give \( \gamma \approx 0.45 \). But intuitively this is not the optimal rate, because we are always matching the largest branches, whereas (because \(Z\) is first-order random) there is no reason to think this is always optimal.
Update (9/2018): Misra and Sullivant give a \(n^{1/2}\) result in the tree setting, for trees with the same shape.
Update (March 2019) the original document mentions longest common subsequence of random permutations, which in the uniform random model reduces to the longest increasing subsequence of a single random permutation. A non-uniform model is studied in Ke Jim The length of the longest common subsequence of two independent Mallows permutations.
Update (2022): For the uniform distribution on cladograms model, this paper proves a lower bound of \(n^\beta\) for \(\beta = 0.366\).
Back to Open Problem list