# Cluster mempool definitions & theory

**URL:** <https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202>\
**Category:** Implementation\
**Tags:** wg-cluster-mempool\
**Created:** [November 17, 2023, 2:40am UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202 "2023-11-17T02:40:41Z")\
**Posts on this page:** 1\
**Showing post:** 8

<div class="post-metadata">

**Author:** ![sipa](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/sipa/32/1100_2.png) [@sipa](https://delvingbitcoin.org/u/sipa)\
**Post date:** [December 12, 2023, 4:09am UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/8 "2023-12-12T04:09:42Z")

</div>

TIL about [directed sets](https://en.wikipedia.org/wiki/Directed_set): sets with a preorder \geq and the additional property that for any pair of elements (a, b) an element c exists such that c \geq a and c \geq b.

In a directed set, every maximal element (m is maximal if no x \> m exists) is a greatest element (m is greatest if for every x it holds that m \geq x).

Linearizations (and chunkings) of graphs/clusters are directed sets (with \gtrsim as the direction). The merge-intersection algorithm computes the c mentioned above given a and b. The “move highest feerate subset to front, continue with remainder” algorithm by construction computes a maximal element, which is thus a greatest element. “Optimal linearization” is the name we have for greatest element.

---

_[View the full topic](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202)._