3
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Misha Lavrov
    Dec 25, 2021 at 20:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – Misha Lavrov
    Dec 25, 2021 at 20:46

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.