3
$\begingroup$

Yesterday I came up with this problem and I just cannot get it out of my head:

Problem: Consider a finite $I$ set of integer-valued intervals $I_i=(a_i,b_i)$ $i = 1,\ldots,n; a_i \in \mathbb{N_0}, k \in \mathbb{N}, I=( I_1,\ldots,I_n\ )$

Assume there is a map $\phi: I \longrightarrow \{1,\ldots,k\}$ such that

$(*): \{l, m\} \subset \{1,\ldots,n\}, l \neq m, \phi(I_l)=\phi(I_m) \Rightarrow I_l \cap I_m=\emptyset$

Now if $M=(x,y)$ is an inteval such that $(**): M\cap\left(\bigcap_{i=1}^k\left(\bigcup\{I_j|\phi(I_j) = i\}\right)\right)=\emptyset$. then $M$ can be always appended to $I$ with a new map $\phi'$ such that property $(*)$ holds.

Example: $k=3$, $I=( (0,2), (3,5), (2,4), (5,7), (0,3), (4,6) )$, $\phi(I)=( 1,1,2,2,3,3)$

This corresponds to the following image (edit: the $k$ on the left side is a bit misleading, better ignore it):

enter image description here

As you can see the property $(*)$ is fullfilled (no intervals are overlapping in their time line). We can also see that for the interval $(2,4)$ he have the property $(**)$ i.e. we find spaces to put it into the image:

enter image description here

Now the theorem tells us that there is a new image where the green interval does not have to be broken. And indeed we find $\phi(I \cup (2,4))=(1,2,3,2,2,2,1,1)$. Or in the image:

enter image description here

I hope I could explain the problem well. I am not sure if the theorem is correct but I tried quite a few examples and it always worked out.

  • 0
    @joriki: Thank you I understood the point now and updated it in the question.2012-01-18

2 Answers 2

4

Assuming that instead of $(**)$ you meant $M\cap\left(\bigcap_{i=1}^k\left(\bigcup\{I_j|\phi(I_j) = i\}\right)\right)=\emptyset$, then yes, this will always work.

Without loss of generality, we can assume that the only spaces left in the rows are exactly the ones required for $M$; if not, we can fill any remaining empty spaces without making the problem easier.

Now within a row there may be transitions from empty space to filled space and/or from filled space to empty space. Since there is at most one empty space per column and the empty spaces are all consecutive ($M$ being an interval), these two types of transitions are paired up, except for an unpaired initial transition from filled space to empty space and an unpaired final transition from empty space to filled space (where the margins count as filled space in case $M$ touches them).

Now in each row except for the one containing the unpaired initial transition, go through from the front and when you hit a transition from filled space to empty space switch to the row containing the corresponding transition from empty space to filled space. In this manner you can fill an entire row with filled space. What's left after this is the filled space before the unpaired initial transition and the filled space after the unpaired final transition. Put these together in the remaining row, and $M$ fits snugly between them.

  • 1
    @Listing: Glad to be of service -- sweet dreams! :-)2012-01-18
2

The conjecture is true. To avoid endpoint details I’m going to replace your open intervals by left-closed intervals, and instead of $\phi$, I’m going to talk about levels of the picture.

Suppose that $[j,k)$ is the interval to be added that satisfies $(**)$. Write $[j,k)$ as a union of pairwise disjoint intervals, each of which fits into an empty slot on some level; I’ll call them the green intervals. In the example, $[2,4)$ gets split into the green subintervals $[2,3)$ and $[3,4)$. Each level then consists of (possibly) one or more green intervals and some of the old red intervals. Replace the red intervals on each level by the maximal intervals disjoint from the green intervals on that level; call these blue intervals. In the example that would result in blue intervals $[0,2)$ and $[3,7)$ on level $1$, a single blue interval $[0,7)$ on level $2$, and blue intervals $[0,3)$ and $[4,7)$ on level $3$. Each blue interval is a union of original red intervals and possibly some unused spaces, so moving blue intervals intact also preserves the red intervals within them.

Say that the green intervals, from left to right ignoring level, are $G_1,\dots,G_r$. $G_1$ together with the blue interval to its left (if any) exactly matches the blue interval to the left $G_2$, so these intervals can be interchanged to put $G_1$ adjacent to $G_2$ on the same level. (This is not what was done in the example: it would have left level $2$ unchanged, put $[0,3)$ and $[3,5)$ on level $1$, and put the rest on level $3$.) Now replace $G_1$ by $G_1\cup G_2$ and $G_i$ by $G_{i+1}$ for $i=2,\dots,r-1$ and repeat until there is just one green interval.