Abstract
In multiple-choice data structures each element \(x\) in a set \(S\) of \(m\) keys is associated with a random set \(e(x) \subseteq [n]\) of buckets with capacity \(\ell \geq 1\) by hash functions. This setting is captured by the hypergraph \(H = ([n],\\{e(x) \mid x \in S\\})\). Accomodating each key in an associated bucket amounts to finding an \(\ell\)-orientation of \(H\) assigning to each hyperedge an incident vertex such that each vertex is assigned at most \(\ell\) hyperedges. If each subhypergraph of \(H\) has minimum degree at most \(\ell\), then an \(\ell\)-orientation can be found greedily and \(H\) is called \(\ell\)-peelable. Peelability has a central role in invertible Bloom lookup tables and can speed up the construction of retrieval data structures, perfect hash functions and cuckoo hash tables. Many hypergraphs exhibit sharp density thresholds with respect to \(\ell\)-orientability and \(\ell\)-peelability, i.e. as the density \(c = \frac\{m\}\{n\}\) grows past a crit