2
$\begingroup$

I have a list $[1, 2, \ldots, T]$. I want to create a collection of subsets, such that:

  1. each element belongs to a small number of subsets
  2. each prefix is a union of small number of subsets (these subsets can intersect, but they must exactly cover the prefix)

For a given collection of subsets, let $F$ and $G$ be the maximums of the values from the first and second properties respectively.

Examples:

  • binary tree: each elements belongs to $\log T$ subsets (so, $F = \log T$) and each prefix can be represented by a union of $\log T$ subsets ($G = \log T$)
  • prefixes themselves, i.e. $[1]$, $[1, 2]$, $[1, 2, 3]$, $\ldots$, $[1, 2, \ldots, T]$. Here, element 1 belongs to $T$ subsets, and each prefix is exactly 1 subset. Therefore, $F = T$ and $G = 1$.

My question is, which structure minimises $G \log F$?

In particular, compared to binary search structure, where $F = G = \log T$, I would like to have a smaller value of $G$ in the expense of larger $F$.

My intuition is that it is possible to have $G = O(\log^w \log T)$ while $F = O(\log^k T)$, for some constant $w$ and $k$, which would give $G \log F = O(\log^{w+1} \log T)$.

On the other hand, maybe there exist some lowerbounds from coding theory?

I looked at the van Emde Boas tree, but could not improve $G \log F$.

Thank you!

$\endgroup$
1
  • 1
    $\begingroup$ The obvious parameter setting to explore is $G=2$. Then to do better than what you've got so far, you need to have $F < \sqrt{T}$. So I think the first natural question is, is there a way to achieve both $F<\sqrt{T}$ and $G=2$? That seems pretty challenging. $\endgroup$
    – D.W.
    Commented Oct 15, 2023 at 0:47

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.