# Maximal number of intersections within a bipartite graph

Consider $$n$$ line segments in the Cartesian plane. For $$1\leq k\leq n$$, the $$k$$-th line segment is drawn from $$(k,0)$$ to $$(x_k,1)$$, where $$\{x_1,x_2,...,x_k\}$$ is a permutation of $$\{1,2,...,n\}$$. Define $$a(n)$$ to be the maximal number of distinct points at which two or more line segments intersect.

For example, take $$n=3$$. A maximal construction for $$a(n)$$ would be a segment from $$(1,0)$$ to $$(3,1)$$, $$(2,0)$$ to $$(1,1)$$, and $$(3,0)$$ to $$(2,1)$$, giving $$2$$ distinct intersection points.

I have simulated the maximal values up to $$n=13$$ (and my friend has posted it on OEIS already here: https://oeis.org/A332774), but I am limited by the extreme time complexity of my program (around $$n*n!*\log n$$). The values from $$n=1$$ to $$13$$ are:

$$0,1,2,5,8,13,17,23,30,39,47,57,67$$

I was wondering if a formula for $$a(n)$$ could exist, either recursive or explicit. Could it have something to do with the number of intersections in certain types of bipartite graphs? If no formula can be found, can there be any good estimates for upper / lower bounds?

• I was able to get a bit further and compute $a(14)=79$, $a(15)=90$, $a(16)=103$. (My approach is a branch-and-bound algorithm with the following upper bound on partial permutations: if, say, $n=10$ and $1,2,3,4,5$ are matched to $2,4,6,8,10$ in any order, then in addition the intersections found so far, the unused values $1,3,5,7,9$ will intersect $5,4,3,2,1$ of the existing segments, respectively, and will intersect each other at most $\binom 52$ times.) Dec 25, 2021 at 20:41
• If we take $a(2), \dots, a(16)$, then the second differences are $2, 0, 2, -1, 2, 1, 2, -1, 2, 0, 2, -1, 2$, which looks like it's started repeating every $8$ steps, but there's not enough data to be sure. Dec 25, 2021 at 20:46