Systems of overlap representation for families of intervals (Q2115149)

For a positive integer \(n\), let \([n]\) denote \(\{1, \dots, n\}\). Two sets overlap if they intersect and neither contains the other. Given a family \(\mathcal{A}\) of distinct sets \(A_1, \dots, A_r\), a family \(\mathcal{S}\) of sets \(S_1, \dots, S_r\) is a system of overlap representation (SOR) of \(\mathcal{A}\) if for each \(i \in [r]\), \(S_i \subseteq A_i\) and \(S_i \cap S_j \neq \emptyset\) for each \(j \in [r]\) such that \(A_i\) and \(A_j\) overlap. For two integers \(a\) and \(b\) with \(1 \leq a \leq b\), let \([a,b]\) denote the interval \(\{i \in [b] \colon i \geq a\}\). Let \(\mathcal{F}_n\) denote the family \(\{[a,b] : a, b \in [n], \, a \leq b\}\). Let \(f(n)\) denote \(\min\{\max\{|S| \colon S \in \mathcal{S}\} : \mathcal{S} \mbox{ is an SOR of } \mathcal{F}_n\}\). The authors show that \((1 - o(1)) \log_2 n \leq f(n) \leq 2\log_2(n-1)\).