Largest common substructures in probabilistic combinatorics

The general setting and two particular questions are described in this section of the original 2003 document. Regarding the two-dimensional partial order problem described there, a brief correspondence with Graham Brightwell had resulted (May 2001) in me writing some May 2001 draft notes, but neither of us pursued it thereafter, according to memory and files.

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.

Back to Open Problem list