# Combinatorial characterization of intersecting intervals in the plane

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.

• 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. Oct 6, 2016 at 22:58
• @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. Oct 6, 2016 at 23:18
• What does $[n]_q$ mean here?
– user44143
May 28, 2020 at 8:12
• @MattF. I use the notation of q-analogs, math.upenn.edu/~peal/polynomials/q-analogues.htm May 28, 2020 at 12:39
• 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. May 28, 2020 at 18:19