Consider $n$ points $A=\{A_1,\dotsc,A_n\}$, and another set of points, $B=\{B_1,\dotsc,B_n\}$ in the plane. We can assume they are all disjoint.

For each permutation $\pi$, consider the collection of line segments joining $A_i$ with $B_{\pi(i)}$, and count the total number of intersections. Call this number $int_{AB}(\pi)$, and define the polynomial $$ P_{AB}(q) = \sum_{\pi \in S_n} q^{int_{AB}(\pi)}. $$ Clearly, $P_{AB}(1)=n!$ and all coefficients are non-negative. It is an easy exercise to show that one can choose $A$ and $B$, such that $P_{AB}(q)=[n]_q!$.

Now, considering all possible choices of $A$ and $B$, there are only a finite set such polynomials. This is clear since there are only a finite number of polynomials with non-negative integer coefficients, with bounded coefficient sum.

How many polynomials can be constructed using two sets of $n$ points?

Can we characterize this set of polynomials combinatorially? That is, find a discrete set of objects equinumerous with the polynomials obtainable from $n+n$ points, plus a statistic on these objects, that generate these polynomials.

EDIT: It is probably easier to characterize cases where we keep track of all intersections. That is, $$ P_{AB}(z) = \sum_{\pi \in S_n} \prod_{i,j} z_{ij}^{int_{AB}(\pi,i,j)} . $$ where $int_{AB}(\pi,i,j)=1$ if $A_i$ intersect $B_{\pi(j)}$ and 0 otherwise. Then putting all $z_{ij}=q$, we recover the polynomial above.

  • 1
    $\begingroup$ This could already be interesting if all the $n+n$ points are on a straight line, i.e. a 1-dimensional version of the 2-D problem. It might also be appealing to limit the general location of the points, say anywhere on a circle, etc. $\endgroup$ Oct 6, 2016 at 22:58
  • $\begingroup$ @T.Amdeberhan: Yes, I agree - I am looking a bit on the case when the points in A are of the form (t,t^2) for t=1,2,...n. There are a few generalizations also that I have in mind, but not come up with a good definition: Find a symmetric polynomial defined in a similar spirit. Find a generalization/construction that detects topology/genus of the underlying surface. $\endgroup$ Oct 6, 2016 at 23:18
  • $\begingroup$ What does $[n]_q$ mean here? $\endgroup$
    – user44143
    May 28, 2020 at 8:12
  • $\begingroup$ @MattF. I use the notation of q-analogs, math.upenn.edu/~peal/polynomials/q-analogues.htm $\endgroup$ May 28, 2020 at 12:39
  • $\begingroup$ This has a similar flavor to the allowable sequences of Goodman and Pollack at link.springer.com/chapter/10.1007/978-3-642-58043-7_6. $\endgroup$ May 28, 2020 at 18:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.