Largest common suborder of two random two-dimensional orders

Definitions and mathematical statement

For each $n$, sample two independent collections of points \[ Z_i=(U_i,V_i),\qquad Z_i'=(U_i',V_i'),\qquad 1\le i\le n, \] all uniformly distributed in $[0,1]^2$. Each collection defines a partial order on the same label set $[n]$: for distinct labels, $i\prec j$ means $U_i<U_j$ and $V_i<V_j$, and $i\prec'j$ is defined by the primed coordinates. Coordinate ties occur with probability zero.

For a subset $A\subseteq[n]$, say the induced orders agree if, for every ordered pair of distinct labels $i,j\in A$, $i\prec j$ holds exactly when $i\prec'j$ holds. Define \[ C_n=\max\{|A|:A\subseteq[n],\ \prec|_A=\prec'|_A\}. \] Is there a constant $c\in(0,\infty)$ such that $\mathbb EC_n\sim c n^{1/3}$? Prove existence of this finite positive limit constant and determine its value or provide a mathematical characterization of it.

Here $a_n\sim b_n$ means $a_n/b_n\to1$. The expectation is over both independent point samples. Agreement is label-preserving and includes incomparability as well as comparability and its direction. Thus the task is not unrestricted isomorphism between two subsets carrying different labels.

The proposed asymptotic is stronger than upper and lower bounds of order $n^{1/3}$. It asks that the normalized expectations have one limit along the entire sequence of integers, and includes identifying what controls that constant.

Short English statement

Does the largest label-preserving common suborder of two random planar orders have mean asymptotic to a fixed constant times n to the one-third power?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 9700020 (AMR-096-0020), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Aldous - Open problems, substructures.html; linked 2003 document, Example 4. Original source indexed by AMR-096-0020. https://www.stat.berkeley.edu/~aldous/Research/OP/index.html.
• S3 D. Aldous, Largest common substructures in probabilistic combinatorics, original problem definitions. https://www.stat.berkeley.edu/~aldous/Research/OP/common_subs.pdf.