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.

  • 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$ – T. Amdeberhan Oct 6 '16 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$ – Per Alexandersson Oct 6 '16 at 23:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.