10
$\begingroup$

Suppose I am given a set of $n$ intervals, each having length $\ell_i$. Is there a bound on the number of possible orderings of their left and right endpoints? For example, if each interval is represented by $[x_i,y_i]$, with $y_i-x_i=\ell_i$, then one possible ordering would be $x_1\leq x_3\leq y_1\leq x_2 \leq y_2 \leq y_3$. If the lengths are not fixed, then it is clear that the number of orderings is $(2n)!/2^n$. Does fixing the lengths permit a significantly better upper bound?

$\endgroup$
  • 1
    $\begingroup$ Do you assume that the given lengths are ordered or, in other words, that $x_1\leq\dots \leq x_n$? $\endgroup$ – Max Alekseyev Nov 13 '17 at 17:01
  • $\begingroup$ @MaxAlekseyev thanks, clarified (the answer is "no"). $\endgroup$ – Tom Solberg Nov 13 '17 at 17:23
  • $\begingroup$ Just to make it clear what exactly you are looking for: 1) Are you interested in the worst case scenario? 2) How much better do you want it? (even if we cannot get the right bound, we may be able to get something sufficient for your purposes; some slight improvements are certainly trivial). $\endgroup$ – fedja Nov 13 '17 at 18:15
  • $\begingroup$ @fedja Worst-case scenario would certainly be enlightening. I mainly want to know how weak the bound of $(2n)!/2^n$ is, or if the actual count turns out to be somewhat close to that. $\endgroup$ – Tom Solberg Nov 13 '17 at 18:23
10
$\begingroup$

If all the interval lengths are the same, then the number of ways is $n!C_n$, where $C_n$ is a Catalan number. If we are interested only in the number of ways we can specify whether $y_i<x_j$ or $x_j<y_i$ for all $i,j$, then the number of ways is the number of regions of the hyperplane arrangement $\mathcal{A}(\ell_1,\dots,\ell_n)$ in $\mathbb{R}^n$ with hyperplanes $x_i-x_j=\ell_i$, for $1\leq i<j\leq n$. If the $\ell_i$'s are sufficiently generic (e.g., linearly independent over $\mathbb{Q}$ or super-increasing) and if $c_n$ is the number of regions of $\mathcal{A}(\ell_1,\dots,\ell_n)$, then the generating function $z=\sum_{n\geq 0}c_n\frac{x^n}{n!}$ is uniquely determined by the condition $\frac{z'}{z}=y^2$, $z(0)=1$, where $1=y(2-e^{xy})$. See http://math.mit.edu/~rstan/papers/nas.pdf.

Addendum. For the actual question, the number $f(n)$ of arrangements is the number of regions of the hyperplane arrangement $\mathcal{I}_n$ defined by $$ x_i - x_j = 0,\ \ i<j $$ $$ x_i - x_j = \ell_i,\ \ i\neq j $$ $$ x_i-x_j = \ell_i-\ell_j,\ \ i\neq j. $$ An upper bound would be the number $g(n)$ of regions of $$ x_i-x_j = a_{ij}, b_{ij}, c_{ij}, d_{ij}, e_{ij}, $$ where the $a_{ij}$'s, $\dots, e_{ij}$'s are generic. This number is given by $$ g(n) = \sum_F 5^{e(F)}, $$ where the sum is over all forests $F$ on $n$ vertices, and $e(F)$ is the number of edges of $F$. It has the generating function $$ \sum_{n\geq 0}g(n)\frac{x^n}{n!} = \exp \sum_{i\geq 1} 5^{i-1} i^{i-2}\frac{x^i}{i!}. $$ I wonder how close this upper bound is to $f(n)$.

With a little more work, one should be able to give a slightly better upper bound by computing the number of regions of $$ x_i-x_j = 0, a_{ij}, b_{ij}, c_{ij}, d_{ij}. $$ It may even be possible to compute the number of regions of $\mathcal{I}_n$ itself when the $\ell_i$'s are generic using methods similar to those used for $\mathcal{A}(\ell_1,\dots,\ell_n)$. Details of the proof are in Section 6 of http://math.mit.edu/~rstan/papers/deform.pdf.

The interpretation of $f(n)$ in terms of hyperplane arrangements has the interesting consequence that as long as the $\ell_i$'s are sufficiently generic real numbers (in particular, the set of nongeneric $(\ell_1,\dots,\ell_n)\in\mathbb{R}^n$ has measure 0), the number $f(n)$ of arrangements depends only on $n$. Note that the set of possible orderings of the $x_i$'s and $y_i$'s does depend on the actual generic $\ell_i$'s.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So $z = \exp \int y$ and $y$ is holomorphic on a disc of radius $\approx 0.204378$ if I didn't make any errors. So $c_n \approx n! (0.204378)^{-n} \approx n! (4.8929)^n$. It seems like a natural question is the largest $\alpha$ for which we can have group like $n! \alpha^n$. $\endgroup$ – David E Speyer Nov 14 '17 at 3:34
  • $\begingroup$ Unless the exponential makes the radius of convergence larger, but it looks (in the sense that I plotted it and looked at it) like the singularity is $y \approx a+b(x-0.204378)^{1/2}$, so I would expect the exponential to remain singular. $\endgroup$ – David E Speyer Nov 14 '17 at 3:35
  • $\begingroup$ @DavidSpeyer: I could not understand the sentence "It seems like a natural question ..." $\endgroup$ – Richard Stanley Nov 14 '17 at 14:10
  • $\begingroup$ Oh, sorry, the typos can't have helped. It seems like the natural question is, if we get to chose the lengths $\ell_1$, $\ell_2$, \ldots, $\ell_n$, for how large an $\alpha$ can we get the number of arrangements to grow like $n! \alpha^n$. Your Catalan example gives $n! 4^n$, and this example gives a lower bound of $n! (4.8929)^n$. $\endgroup$ – David E Speyer Nov 14 '17 at 14:12
  • $\begingroup$ Fascinating stuff! $\endgroup$ – Tom Solberg Nov 14 '17 at 19:55
7
$\begingroup$

Edit My criticism of Richard's post no longer applies after he edited it drastically, so I edited it out :-)

First, note that it is enough to bound the number of compatible pairs of permutations of $x$ and $y$ separately. Indeed, since we have at most ${2n\choose n}=e^{O(n)}$ insertions of those orders, we can that get the whole thing up to an exponential error, so if we are not after an exact asymptotics, we do not lose much this way.

To do it, we will just play with collision graphs. The idea is pretty simple: start moving intervals around without changing any of the two relevant orders until left ends or right ends of something nearly collide, after which move the tangled piece together until some more similar ends collide somewhere, and so on until we bring the configuration to a single piece. The graph is just the set of some disjoint red cliques corresponding to bunches of $x$-s that are all squashed nearly together and blue cliques corresponding to $y$'s. Note that the entire graph is connected (using both colors), so once we know the graph and the resolution of all cliques, we know the entire configuration. Suppose also that the lengths are generic (say, independent over $\mathbb Q$). If we are interested just in the strict orders, that can be done without any loss of generality. Our collision graph is then just a pair of disjoint clique graphs. Let us assume that the red graph has $k_j$ $j$-cliques and the blue graph $\ell_j$ $j$-cliques, so $$ \sum_j jk_j=\sum_j j\ell_j=n\,. $$ Now note that there are $\frac{n!}{(k_1!k_2!\dots)(1!)^{k_1}(2!)^{k_2}\dots}$ possible red graphs and, thereby, $\frac{n!}{k_1!k_2!\dots}$ resolved red graphs. Note also that such red graph has $\sum k_j$ components. Suppose that the red graph is given. Let us see where we can place the blue graph drawing its cliques in some natural order. Observe that when we do the first clique, we have to take all vertices from differentconnected components (otherwise we get a non-trivial relation between lengths) and once we draw it, we create a big stiff component that cannot have any more blue edges. Also, the number of components drops by the size of the clique minus one. The same argument (only the last sentence is relevant) applies to the second clique and so on. Thus, if the red and the blue graphs were compatible at all, we must have $n-\sum_j\ell_j\le \sum_j k_j$ (the component reduction should not exceed the number of components available from the beginning), i.e., $n\le\sum_j\ell_j+\sum_j k_j$ is a necessary compatibility condition.

Now we just forget anything except this last observation and write $$ \frac{n!}{k_1!k_2!\dots}\frac{n!}{\ell_1!\ell_2!\dots}\le \frac{n!^2}{n^{n}}\frac {n^{k_1+k_2+\dots}}{k_1!k_2!\dots}\frac {n^{\ell_1+\ell_2+\dots}}{\ell_1!\ell_2!\dots} $$ We need to sum such expressions over all $k$'s and $\ell$'s satisfying $\sum_j jk_j=\sum_j j\ell_j=n$. This amounts to the square of the $n$-the Taylor coefficient of $e^{nz}e^{nz^2}e^{nz^3}\dots=e^{\frac {nz}{1-z}}$. The Cauchy bound with the radius $1/2$ (yeah, one can optimize here, but we have already missed our chance for the exact asymptotics when deciding to separate the orders, so why to care now?) gives $(2e)^{2n}$ and the final estimate of $$ \frac{(2n)!}{n^n}(4e^2)^n=n!e^{O(n)} $$ The end :-)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I feel stupid for asking, but where does the $(2n)!/n^n$ in the last line come from? $\endgroup$ – Tom Solberg Nov 16 '17 at 6:38
  • $\begingroup$ @TomSolberg We have $\frac{(2n)!}{(n!)^2}$ possible insertions of compatible orders to get the full ordering of $x$ and $y$ together. This is multiplied by the pre-factor $\frac{(n!)^2}{n^n}$ on the last but one displayed line and gives $\frac{(2n)!}{n^n}$. The huge sum over admissible $k$ and $\ell$ of the remaining products of fractions with factorials is bounded by $(2e)^{2n}$ as outlined. $\endgroup$ – fedja Nov 16 '17 at 17:20
2
$\begingroup$

One term you might want to search is "interval order" https://en.m.wikipedia.org/wiki/Interval_order

If you fix the interval lenghts it might be open. Not the expect. One time, in an unrelated search I found this

Bousquet-Mélou, Mireille; Claesson, Anders; Dukes, Mark; Kitaev, Sergey (2010), "(2+2) free posets, ascent sequences and pattern avoiding permutations", Journal of Combinatorial Theory, Series A, 117 (7): 884–909, MR 2652101, doi:10.1016/j.jcta.2009.12.007

| cite | improve this answer | |
$\endgroup$

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.