How many pairs of intersecting intervals can be chosen from two finite sets of disjoint intervals?

53 Views Asked by At

Let $$ \mathcal{K} := \{ I \cap J \mid I \in \mathcal{I}, J \in \mathcal{J} \} \setminus \{ \emptyset\},$$ where $\mathcal{I}$ is a finite set of disjoint real intervals, and so is $\mathcal{J}$.

Obviously $| \mathcal{K}| \leq |\mathcal{I}| |\mathcal{J}|$. Are there any better bounds on the cardinality of $\mathcal{K}$?

Where in the literature can one find related theory and results?

1

There are 1 best solutions below

0
On BEST ANSWER

Consider the bipartite graph with vertices $\mathcal{I}∪\mathcal{J}$ and edges $(I,J)$ if $I$ intersects $J$.

If $I\in \mathcal{I}$ then edges $(I,J)$ mean that either $J\subseteq I$ (and then $J$ is not connected to any other $I′\in \mathcal{I}$) or $J$ contains $I$ (and then $I$ is not connected to any other $J′\in \mathcal{J}$) or $J$ overlaps with $I$ (there are at most two such $J$).

The rest was explained by @Selva:

So we can initially ignore any $I$ that is fully contained in some $J$, and any $J$ that is fully contained in some $I$. Then each remaining node can have at most two edges, and we have a path graph with no more than $N-1$ edges, where $N$ is the number of remaining nodes. The $I$ and $J$ that we initially left out just add one more edge each. It follows that $|\mathcal{K}| < |\mathcal{I}| + |\mathcal{J}|$.