Largest bipartite sub-matchings of a random ordered matching or a problem with socks

Andrzej Dudek, Jarosław Grytczuk, Andrzej Ruciński

Let $M$ be an ordered matching of size $n$, that is, a partition of the set $[2n]$ into 2-element subsets. The sock number of $M$ is the maximum size of a sub-matching of $M$ in wh…