2
$\begingroup$

Consider the integers $[1,n]=\{1,\dots,n\}$ and call subsets of the type $[a,b]=\{a,\dots,b\}$ with $1\le a < b\le n$ intervals. We say that two intervals $[a,b],[c,d]$ are crossing if either $a<c<b<d$ or $c<a<d<b$. Otherwise we say that the intervals are non-crossing. So $[1,3],[2,4]$ are crossing, but $[1,3],[2,3]$ or $[1,3],[3,4]$ are non-crossing.

Let $A_n$ denote the collection of pairwise non-crossing sets of intervals. So the first few are \begin{align} A_2&=\Bigl\{\emptyset,\{[1,2]\}\Bigr\}\\ A_3&=\Bigl\{ \emptyset,\{[1,2]\},\{[2,3]\},\{[1,2],[2,3]\},\\ &\qquad\{[1,3]\},\{[1,2],[1,3]\},\{[2,3],[1,3]\},\{[1,2],[1,3],[2,3]\} \Bigr\}\\ A_4 &= \Bigl\{ \emptyset,\{[1,2]\},\{[1,3],[3,4]\},\{[1,2],[2,4],[1,4]\},\dots \Bigr\}. \end{align}

It seems that there is an easy recursion for the number of such sets of non-crossing intervals: $$|A_n| = 2 \Bigl(2|A_{n-1}||A_2|-|A_2|^2|A_{n-2}|\Bigr)=8(|A_{n-1}| - |A_{n-2}|) \tag{*},$$ so that $$(|A_2|,|A_3|,|A_4|,\dots)=(2,8, 48, 320, 2176, 14848, 101376,\dots)$$ which seems to be https://oeis.org/A228568.

Questions:

  • Is there some standard name for sets sets of non-crossing intervals in the literature? Is the number of such sets known?
  • Is the recursion above correct?

My reasoning for (*) is as follows: Any non-crossing collection of sets on $[1,n]$ can be obtained from non-crossing collections on $[1,n-1]$ and $[n-1,n]$ or $[1,2]$ and $[2,n]$ by optionally adding the interval $[1,n]$. However, this is over-counting the intervals which can be obtained from combining non-crossing collections on $[1,2],[2,n-1],[n-1,n]$.

Edit: My reasoning for (*) was flawed and the conclusion was incorrect. The correct number of sets seems to be $$(|A_2|,|A_3|,\dots)=(2, 8, 48, 352, 2880, 25216, 231168, \dots)$$ which is https://oeis.org/A054726.

$\endgroup$
  • $\begingroup$ This is reminiscent of non-crossing partitions, but not quite. $\endgroup$ – Per Alexandersson Mar 28 '20 at 20:06
  • $\begingroup$ Have you done computations to verify $|A_8|=101376$? $\endgroup$ – Gerry Myerson Mar 29 '20 at 11:32
  • $\begingroup$ @GerryMyerson I got the number just from ($\ast$). But today I noticed that ($\ast$) is actually flawed, and in particular the numbers of sets I got was wrong. I updated the post with an updated guess for the number of sets $\endgroup$ – Julian Mar 29 '20 at 15:06
  • 1
    $\begingroup$ The "number of graphs on n nodes on a circle without crossing edges" interpretation is clearly right, FWIW. $\endgroup$ – Sam Hopkins Mar 29 '20 at 15:08
  • 1
    $\begingroup$ @GerryMyerson: Done. $\endgroup$ – Sam Hopkins Mar 30 '20 at 18:18
4
$\begingroup$

As discussed in the comments, the number in question is clearly the same as the number of graphs on $n$ vertices drawn on a circle without crossing edges, which is in the OEIS at https://oeis.org/A054726. As discussed in that OEIS entry, the number is $2^n$ times a "little Schroeder number": recall that one interpretation of the little Schroeder number is as the number of (not necessarily maximal) dissections of a convex $n$-gon; in other words, these count collections of noncrossing diagonals; the only difference between these and graphs without crossing edges is that the graphs may include edges of the form $\{i,i+1\}$, and any such subset is also allowed, hence the factor of $2^n$. Since the little Schroeder numbers are very well-studied, this is the best formula you could hope for.

$\endgroup$
  • 1
    $\begingroup$ Thanks! Small addition: The little-Schroeder numbers count the number of non-crossing graphs on the circle without next-neighbour edges. Since there are $n$ such next-neighbour edges it follows that the total number of graphs is $2^n$ times the little-Schroeder numbers. For more details on the generating functions the paper <mathscinet.ams.org/mathscinet-getitem?mr=345872> is also a good reference. $\endgroup$ – Julian Mar 30 '20 at 23:16
  • $\begingroup$ @Julian: ah, yes, I see- if we think of the little Schroeder numbers as counting (not necessarily maximal) dissections of an $n$-gon then this interpretation is indeed clear. $\endgroup$ – Sam Hopkins Mar 30 '20 at 23:53

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.