Upper bound on the average number of overlaps for an interval within a set of intervals

Question

Let $\mathcal{I}$ be a set of intervals with cardinality $L$, where each interval $I_i \in \mathcal{I}$ is of the form $[a_i, b_i]$ and $a_i, b_i$ are pairwise distinct non-negative integers bounded by a constant $C$ i.e. $0 \leq a_i < b_i \leq C$. We say a pair of intervals $I_i, I_j \in \mathcal{I}$ overlap if the length of overlap is $> 0$.

Define a function $F(i)$ which computes the number of intervals in $\mathcal{I} \backslash I_i$ that interval $I_i$ overlaps with. \begin{equation} F(i) = \sum_{j=1, j \neq i}^{L} Overlap(I_i, I_j) \end{equation} where the function $Overlap(I_i, I_j)$ is an indicator function which returns 1 if $I_i, I_j$ overlap, else it returns 0.

The average number of overlaps for the intervals in $\mathcal{I}$, denoted by $Avg(\mathcal{I})$ is given by $Avg(\mathcal{I}) = \dfrac{\sum_{i=1}^{L}F(i)}{L}$.

The question is, suppose we are allowed to choose the intervals in the set $\mathcal{I}$ with the following additional conditions:

1. For any $t \in [0, C]$, we have at most $M$ (and $M < L$) intervals in $\mathcal{I}$ such that $t$ is contained within those $M$ intervals. Stated differently, at most $M$ intervals overlap at any point in time.
2. Any interval in $\mathcal{I}$ overlaps with at most $K$ other intervals, and $M < K < L$.

then, what is an upper bound on $Avg(\mathcal{I})$ for any choice of the intervals in $\mathcal{I}$ satisfying 1, 2?

In case you are wondering, this problem is of interest to me in order to be able to study the run-time of a scheduling algorithm.

I am unable to come up with a non-trivial upper bound for $Avg(\mathcal{I})$ and would be interested to know if the problem I stated has been studied. I am also open to ideas on how one may be able to obtain a tight upper bound for $Avg(\mathcal{I})$.

Answer 1

If we ignore $L$ and focus only on the parameters $C,K,M$, the following upper bound is asymptotically tight, i.e., it's about the best you can do, up to a constant factor:

$$\text{Avg}(\mathcal{I}) \le \min(MC,K).$$

---

Proof that it's an upper bound: Fix any interval. We're promised that it overlaps with at most $K$ others. Also, the interval has at most $C$ points in it, so by a union bound over those points, we can also infer it overlaps with at most $MC$ others. Therefore, it overlaps with at most $\min(MC,K)$ others. Now the average of a bunch of numbers that are all $\le \min(MC,K)$ will itself be $\le \min(MC,K)$.

---

Proof that it's tight: I will show the construction of a set of intervals where $\text{Avg}(\mathcal{I}) \sim \min(MC,K)/4$. There are two cases:

• Case 1: $K \ge MC$. Then use $M/2$ copies of each interval of the form $[i,i]$ (i.e., each length-0 interval), and use $M/2$ copies of the interval $[1,C]$. You can observe that the latter each intersect with $\sim MC/2$ other intervals (and all intersect with fewer than $K$). So, the average is about $MC/4$. This gives a collection of intervals where each point intersects with $M$ intervals, each interval intersects with $\le K$ others, and $\text{Avg}(\mathcal{I}) \sim MC/4 = \min(MC,K)/4$.

• Case 2: $K < MC$. Set $C' = K/M$, apply the above construction to the interval $[1,C']$ instead of $[1,C]$, and we obtain a collection of intervals where each point intersects with $M$ intervals, each interval intersects with $\le K$ others, and $\text{Avg}(\mathcal{I}) \sim MC'/4 = K/4 = \min(MC,K)/4$.

---

If you also care about the dependence on $L$, you might be able to build on the above analysis to see how it might depend on $L$.