Packing density of 2143 and crossing number of complete graph I've observed a numerical coincidence, and I'd like to know if there's something deeper here, or if I'm just observing a numerical coincidence due to Richard Guy's Strong Law of Small Numbers. I've been guilty of that before.
I've been looking at permutations $\sigma \in S_n$ and computing the greatest number of occurrences of the pattern $\sigma$ over all permutations in $S_m$. (This is only interesting when $m > n$.)
I asked about one aspect of this on MSE a few days ago with my question Greatest number of occurrences of the pattern 4213 in a permutation. In an answer, Misha Lavrov pointed me at a 2002 paper called On Packing Densities of Permutations, which addresses this idea.
The Observation
Using code from Code Golf Stack Exchange Users Noodle9 and Arnauld, it appears that the greatest number of occurrences of the pattern 2143 over all permutations in $S_n$ is equal to $A000241(n+1)$, the crossing number of complete graph with $n+1$ nodes—that is, the fewest number of edge-intersections of the complete graph $K_{n+1}$ when drawn in the plane.
This is true for all known crossing numbers of $K_n$: $A000241(1)$ through $A000241(12)$. The largest crossing number, $A000241(12)$, was computed back in 2007, and if bigger values have been computed since, I don't know of it. This means that without computing more crossing numbers (which is hard, presumably), you can't prove that these are unequal by a numerical comparison.
Question
I suspect that these numbers are eventually different—although permutation patterns show up in surprising places.
Is there some correspondence which shows that these values are equal in general? Or can you use some asymptotic argument (or other argument) to show that they're different eventually?
 A: The packing density of the pattern $2143$ is much easier to find. It is $\frac38$, and achieved by a permutation of the form $$\left\lfloor \frac n2 \right\rfloor, \left\lfloor \frac n2 \right\rfloor
-1, \dots, 1, n, n-1, \dots, \left\lfloor \frac n2 \right\rfloor
+1.$$
The number of occurrences of $2143$ in this permutation is $\binom{\lfloor n/2\rfloor}{2} \binom{\lceil n/2\rceil}{2}$.
This also happens to be the conjectured crossing number of $K_{n+1}$. A construction for this number of crossing is described in Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs by Richter and Thomassen. So we think that actually, these sequences are equal for all $n$ - but we don't have a proof.
In other words, the maximum number of $2143$ patterns is known to be found in the sequence A028723. The crossing number is defined to be the sequence A000241, and it is conjectured that these sequences are equal.
As an aside: the pattern $2143$ is much easier to understand not by coincidence, but because it is layered. A layered permutation of $[n]$ is one obtained from the permutation $123\dots n$ by partitioning it into several consecutive blocks, then reversing each block. (For $2143$, we split $1234$ into $12\;34$, then reverse both to get $21\;43$.) A theorem of Stromquist says that the optimal way to pack a layered permutation pattern is to use a layered permutation.
With $2143$, if we have blocks of size $n_1 + n_2 + \dots + n_r = n$ in a layered permutation, the number of occurrences of the pattern is $\sum_{i<j} \binom{n_i}{2} \binom{n_j}{2}$, and we can prove that this is maximized by making $r=2$ and by making $n_1, n_2$ as equal as possible. This gives the permutation at the beginning of this answer.
