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

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. $$$$F(i) = \sum_{j=1, j \neq i}^{L} Overlap(I_i, I_j)$$$$ 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})$$.

• What's the best upper bound you have so far? What's the best lower bound you have so far? (i.e., explicit construction of a set of intervals that makes Avg(I) as large as possible)
– D.W.
Jan 6, 2020 at 18:22

## 1 Answer

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$$.