# Density expansions and paths of flats

*Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).*

This lesson builds, before any arrival, a family of increasing paths of flats from the revealed labels of the listed weight groups of [Rounding, a maximum rule and candidates](rounding-a-maximum-rule-and-candidates.md). Each group enlarges the flats it receives from the lighter groups by a *density expansion*: the largest flat that gains many revealed labels of the group per unit of rank. Revealed *guards* then enlarge each flat one step of auxiliary time early. The last section shows that a whole path of density expansions is generated by few labels, at most \(|D_h|/\kappa\) of them. Notation and the facts about rank and closure are those of [Prophets, matroids and an almighty adversary](prophets-matroids-and-an-almighty-adversary.md); \(L=\operatorname{cl}(\varnothing)\) is the set of loops.

Throughout, the masks \(H,D,C\) are fixed, so the listed groups \(G_1,\ldots,G_m\) and the sets \(D_h=D\cap G_h\), \(C_h=C\cap G_h\) are fixed. All these labels are candidates, hence nonloops.

## 1. Density expansions

For a listed group \(h\) and every flat \(Z\) put
\[
f_h(Z)=|D_h\cap Z|-\kappa\operatorname{rk}(Z).
\]
The first term counts revealed labels of the group inside \(Z\); the second charges \(\kappa=2^{100}\) for each unit of rank.

**Lemma 1.1 (supermodularity).** For all flats \(Z,Z'\),
\[
\begin{aligned}
&f_h(Z\cap Z')+f_h\bigl(\operatorname{cl}(Z\cup Z')\bigr)\\
&\quad\geq f_h(Z)+f_h(Z').
\end{aligned}
\]

*Proof.* Counting gives
\[
\begin{aligned}
&|D_h\cap Z\cap Z'|+|D_h\cap\operatorname{cl}(Z\cup Z')|\\
&\quad\geq|D_h\cap Z\cap Z'|+|D_h\cap(Z\cup Z')|\\
&\quad=|D_h\cap Z|+|D_h\cap Z'|.
\end{aligned}
\]
Submodularity of rank, with \(\operatorname{rk}(\operatorname{cl}(Z\cup Z'))=\operatorname{rk}(Z\cup Z')\), shows that \(\operatorname{rk}(Z\cap Z')+\operatorname{rk}(\operatorname{cl}(Z\cup Z'))\) is at most \(\operatorname{rk}(Z)+\operatorname{rk}(Z')\). Multiply this inequality by \(-\kappa\) and add the counting inequality. \(\square\)

**Lemma 1.2 (density expansion).** For every flat \(P\) the maximum of \(f_h\) over the flats \(Z\supseteq P\) is attained, and among the maximizers there is a largest one, \(Q_h(P)\). The map \(Q_h\) is extensive (\(P\subseteq Q_h(P)\)) and increasing (\(P\subseteq P'\) implies \(Q_h(P)\subseteq Q_h(P')\)). If \(Q=Q_h(P)\), then for every set \(Z\)
\[
\begin{aligned}
&\bigl|D_h\cap\bigl(\operatorname{cl}(Q+Z)\setminus Q\bigr)\bigr|\\
&\quad\leq\kappa\operatorname{rk}(Z\mid Q).
\end{aligned}\tag{1.1}
\]

*Proof.* There are finitely many flats, and \(P\) itself is feasible, so maximizers exist. If \(Q_1,Q_2\) are maximizers, so are \(Q_1\cap Q_2\) and \(\operatorname{cl}(Q_1\cup Q_2)\): both are feasible flats, so each has value at most the maximum, while by Lemma 1.1 their values add up to at least twice the maximum. Hence the closure of the union of all maximizers is a maximizer containing every maximizer; this is \(Q_h(P)\), and it contains \(P\).

Let \(P\subseteq P'\), \(Q=Q_h(P)\), \(Q'=Q_h(P')\). The flat \(Q\cap Q'\) contains \(P\), so \(f_h(Q\cap Q')\leq f_h(Q)\); the flat \(\operatorname{cl}(Q\cup Q')\) contains \(P'\), so \(f_h(\operatorname{cl}(Q\cup Q'))\leq f_h(Q')\). Lemma 1.1 gives the reverse inequality for the sums, so both inequalities are equalities. In particular \(\operatorname{cl}(Q\cup Q')\) is a maximizer for \(P'\), hence contained in the largest one: \(Q\subseteq\operatorname{cl}(Q\cup Q')\subseteq Q'\).

Finally \(\operatorname{cl}(Q+Z)\) is a flat containing \(P\), so \(f_h(\operatorname{cl}(Q+Z))\leq f_h(Q)\), that is,
\[
\begin{aligned}
&|D_h\cap\operatorname{cl}(Q+Z)|-|D_h\cap Q|\\
&\quad\leq\kappa\bigl(\operatorname{rk}(Q\cup Z)-\operatorname{rk}(Q)\bigr)\\
&\quad=\kappa\operatorname{rk}(Z\mid Q).\qquad\square
\end{aligned}
\]

For a set \(X\) that is not a flat, put \(Q_h(X)=Q_h(\operatorname{cl}(X))\); the map stays increasing and \(X\subseteq Q_h(X)\). Inequality (1.1) says that beyond a density expansion, every unit of extra rank captures at most \(\kappa\) further revealed labels of the group. Maximizing cardinality minus a multiple of rank is the idea behind principal partitions of matroids, which go back to Edmonds's matroid partition theorem; here the maximization is restricted to flats above a given flat and counts only the revealed labels of one group.

## 2. Nominal and guarded paths

An integer \(k\) will be called an *auxiliary time*; it has nothing to do with the order of arrival. Put
\[
F_0(k)=\begin{cases}L,&k<0,\\ E,&k\geq0.\end{cases}
\]
For a listed group \(h\) let \(a_h=-3h\), its *activation time*, and define the *enabled expansion*
\[
Q_{h,k}(P)=\begin{cases}Q_h(P),&k\geq a_h,\\P,&k<a_h.\end{cases}
\]
In increasing order of \(h\) define the *nominal path* \(X_h\) and the *guarded path* \(F_h\) by
\[
\begin{aligned}
X_h(k)&=Q_{h,k}\bigl(F_{h-1}(k)\bigr),\\
\Gamma_h(k)&=C_h\cap X_h(k+1),\\
F_h(k)&=\operatorname{cl}\bigl(X_h(k)+\Gamma_h(k)\bigr).
\end{aligned}
\]
Every \(X_h(k)\) and \(F_h(k)\) is a flat; \(\Gamma_h(k)\) is the set of *guards used at time* \(k\). A guard \(c\in C_h\) enters \(F_h\) at the time just before it enters the nominal path \(X_h\): this is the meaning of using \(X_h(k+1)\) in the definition of \(F_h(k)\). The *final path* is \(\widehat F=F_m\); if \(m=0\), then \(\widehat F=F_0\). All these flats depend only on the matroid, \(D\) and \(C\), so the rule computes them before the first arrival, although the weights of most labels in them are unknown.

**Lemma 2.1 (path properties).** For every listed group \(h\):

(a) the paths \(X_h\) and \(F_h\) are increasing in \(k\), and for all \(k\)
\[
\begin{aligned}
F_{h-1}(k)&\subseteq X_h(k)\subseteq F_h(k)\\
&\subseteq X_h(k+1);
\end{aligned}\tag{2.1}
\]

(b) \(X_h(k)=F_h(k)=E\) for \(k\geq0\);

(c) \(X_h(k)=L\) for \(k<a_h\), and \(F_h(k)=L\) for \(k<a_h-1\);

(d) every nonloop \(e\) has a *nominal birth* \(b_h(e)=\min\{k:e\in X_h(k)\}\), and either \(b_h(e)=a_h\), which happens exactly when \(e\in Q_h(L)\), or \(a_h+2\leq b_h(e)\leq0\).

Consequently \(X_h(k)\subseteq\widehat F(k)\) for all \(h\) and \(k\).

*Proof.* The map \(Q_{h,k}\) is extensive, increasing in its argument, and increasing in \(k\): for \(k<a_h\leq k'\), \(Q_{h,k}(P)=P\subseteq Q_h(P)=Q_{h,k'}(P)\). We argue by induction on \(h\); the path \(F_0\) is increasing and consists of flats.

(a) If \(F_{h-1}\) is increasing, so is \(X_h\), and then so is \(F_h\), by the rules defining the two paths. The first inclusion in (2.1) is extensiveness, the second is clear, and the third holds because \(X_h(k)\subseteq X_h(k+1)\), the guards \(C_h\cap X_h(k+1)\) lie in \(X_h(k+1)\), and \(X_h(k+1)\) is a flat.

(b) For \(k\geq0\), \(F_0(k)=E\), and every later path contains it.

(c) We show along with the induction that \(F_{h-1}(k)=L\) for \(k<a_h+2\). For \(h=1\) this holds because \(F_0(k)=L\) for \(k<0\) and \(a_1+2=-1\). For \(k<a_h\) the expansion is not enabled, so \(X_h(k)=F_{h-1}(k)=L\). For \(k<a_h-1\) both \(X_h(k)\) and \(X_h(k+1)\) equal \(L\); the guards are nonloops, so none lies in \(X_h(k+1)\), and \(F_h(k)=\operatorname{cl}(L)=L\). Since \(a_{h+1}+2=a_h-1\), this is the statement \(F_h(k)=L\) for \(k<a_{h+1}+2\) needed at the next step.

(d) For \(k\in\{a_h,a_h+1\}\) we have \(k<a_h+2\), so \(F_{h-1}(k)=L\) and \(X_h(k)=Q_h(L)\): the nominal path does not change between \(a_h\) and \(a_h+1\). Together with (b) and (c), a nonloop enters \(X_h\) at \(a_h\) if it lies in \(Q_h(L)\), and otherwise at some time in \([a_h+2,0]\).

The last statement follows from (2.1): \(X_h(k)\subseteq F_h(k)\subseteq\cdots\subseteq F_m(k)\). \(\square\)

The spacing \(3\) between activation times is what makes part (d) possible: a label is either present from the start of the group's path or is born at a time \(b\) with \(b-2\geq a_h\), when the group's own density expansion is already enabled (Exercise 4.5).

## 3. A generator budget for the whole path

Comparing a density expansion with the previous one at a single time would charge the same revealed labels again and again. The next lemma chooses one set of generators for all times at once.

**Lemma 3.1 (generator budget).** For each listed group \(h\) there are a set \(J_h\subseteq D_h\) with
\[
|J_h|\leq\frac{|D_h|}\kappa,
\]
and an *insertion time* \(\tau(g)\in[a_h,0]\) for every \(g\in J_h\), such that, with \(J_h(k)=\{g\in J_h:\tau(g)\leq k\}\), for every integer \(k\)
\[
\begin{aligned}
&X_h(k)\\
&\quad=\operatorname{cl}\bigl(F_{h-1}(k)+J_h(k)\bigr).
\end{aligned}\tag{3.1}
\]
In particular \(\operatorname{rk}(Q_h(L))\leq|D_h|/\kappa\).

*Proof.* For \(k<a_h\), (3.1) holds with no generators, since \(X_h(k)=F_{h-1}(k)\) is a flat. For \(k>0\) both sides equal \(E\). We choose generators at the times \(k=a_h,a_h+1,\ldots,0\) in this order and check (3.1) by induction; write \(J(k)\) for the generators chosen at times up to \(k\), so that \(J(k)=J_h(k)\) in the end.

At time \(k\) put \(P_k=\operatorname{cl}(F_{h-1}(k)+X_h(k-1))\). Since \(F_{h-1}(k)\) and \(X_h(k-1)\) lie in the flat \(X_h(k)\), we have \(P_k\subseteq X_h(k)\). The flat \(P_k\) contains \(F_{h-1}(k)\), so it is feasible in the maximization defining \(X_h(k)=Q_h(F_{h-1}(k))\) (enabled, as \(k\geq a_h\)). Hence \(f_h(P_k)\leq f_h(X_h(k))\), and since \(X_h(k-1)\subseteq P_k\), with \(d_k=|D_h\cap X_h(k)|\),
\[
\begin{aligned}
&\kappa\bigl(\operatorname{rk}X_h(k)-\operatorname{rk}P_k\bigr)\\
&\quad\leq d_k-d_{k-1}.
\end{aligned}\tag{3.2}
\]
Next, \(R_k=\operatorname{cl}(F_{h-1}(k)+(D_h\cap X_h(k)))\) is a feasible flat contained in \(X_h(k)\) with the same number of labels of \(D_h\). If \(R_k\neq X_h(k)\), then \(\operatorname{rk}R_k<\operatorname{rk}X_h(k)\) (Lemma 1.3(d) of the first lesson) and \(f_h(R_k)>f_h(X_h(k))\), which is impossible. So \(R_k=X_h(k)\), and therefore \(X_h(k)=\operatorname{cl}(P_k+(D_h\cap X_h(k)))\). Scanning \(D_h\cap X_h(k)\) in label order and keeping the labels not spanned by \(P_k\) and the kept ones (Lemma 1.4 of the first lesson) yields a set \(N_k\subseteq D_h\cap X_h(k)\), independent over \(P_k\), with
\[
\begin{gathered}
\operatorname{cl}(P_k\cup N_k)=X_h(k),\\
|N_k|=\operatorname{rk}X_h(k)-\operatorname{rk}P_k.
\end{gathered}
\]
Give every \(g\in N_k\) the insertion time \(\tau(g)=k\). These labels lie outside \(P_k\), which contains all earlier generators, so all generators are distinct.

By induction \(X_h(k-1)=\operatorname{cl}(F_{h-1}(k-1)+J(k-1))\), and \(F_{h-1}(k-1)\subseteq F_{h-1}(k)\); so \(P_k=\operatorname{cl}(F_{h-1}(k)+J(k-1))\) and \(X_h(k)=\operatorname{cl}(F_{h-1}(k)+J(k-1)+N_k)\), which is (3.1) at time \(k\). Summing (3.2) over \(k=a_h,\ldots,0\) telescopes:
\[
\kappa|J_h|=\kappa\sum_{k=a_h}^0|N_k|\leq d_0-d_{a_h-1}\leq|D_h|.
\]
At \(k=a_h\) the lower path is \(F_{h-1}(a_h)=L\), so \(Q_h(L)=X_h(a_h)=\operatorname{cl}(L+N_{a_h})\) has rank \(|N_{a_h}|\leq|J_h|\). \(\square\)

The generators \(J_h\) are revealed labels, chosen by a fixed rule from \(D_h\); they are a device of the analysis, and the online rule never needs them. The lemma is used twice: in the seventh and eighth lessons to describe the whole nominal path of a group by at most \(|D_h|/\kappa\) insertions, and in the ninth lesson to pay for all later enlargements of the path with one rank budget.

## 4. Exercises

**4.1.** Show that \(Q_h\) is idempotent: \(Q_h(Q_h(P))=Q_h(P)\).

**4.2.** Let \(M\) be the uniform matroid of rank \(r\) on \(n\) labels, so that the flats are the sets of fewer than \(r\) labels together with \(E\). For a flat \(P\neq E\), show that \(Q_h(P)=E\) when \(|D_h\setminus P|\geq\kappa(r-|P|)\), and \(Q_h(P)=P\) otherwise.

**4.3.** With one listed group and \(C_1=\varnothing\), describe \(X_1\) and \(F_1\), and list the possible nominal births.

**4.4.** Show that \(F_h(k)\subseteq\operatorname{cl}(X_h(k)+C_h)\) and \(X_h(k)\subseteq\operatorname{cl}(F_{h-1}(k)+J_h)\) for all \(k\).

**4.5.** Suppose the activation times were \(a_h=-2h\). Which part of Lemma 2.1 could fail, and why would that matter for a label born at \(a_h+1\)?

## 5. Solutions

**4.1.** Let \(Q=Q_h(P)\) and \(Q'=Q_h(Q)\supseteq Q\). The flat \(Q\) is feasible for \(Q\), so \(f_h(Q')\geq f_h(Q)\); the flat \(Q'\) contains \(P\), so \(f_h(Q')\leq f_h(Q)\). Thus \(Q'\) is a maximizer for \(P\), and \(Q'\subseteq Q\) because \(Q\) is the largest one.

**4.2.** For a proper flat \(Z\supseteq P\), \(\operatorname{rk}Z=|Z|\), so \(f_h(Z)=|D_h\cap Z|-\kappa|Z|\); adding a label to \(Z\) changes this by at most \(1-\kappa<0\), so among proper flats \(Z=P\) is best. The flat \(E\) has value \(|D_h|-\kappa r\). It is a maximizer exactly when \(|D_h|-\kappa r\geq|D_h\cap P|-\kappa|P|\), that is, \(|D_h\setminus P|\geq\kappa(r-|P|)\); being the largest flat, it is then the largest maximizer.

**4.3.** Here \(a_1=-3\) and \(F_0(k)=L\) for \(k<0\), so \(X_1(k)=L\) for \(k<-3\), \(X_1(k)=Q_1(L)\) for \(-3\leq k\leq-1\), and \(X_1(k)=E\) for \(k\geq0\); with no guards \(F_1=X_1\). Nonloops are born at \(-3\) (those in \(Q_1(L)\)) or at \(0\).

**4.4.** The first inclusion holds because \(C_h\cap X_h(k+1)\subseteq C_h\). The second follows from (3.1), since \(\{g\in J_h:\tau(g)\leq k\}\subseteq J_h\).

**4.5.** With spacing two, \(F_{h-1}(k)=L\) is guaranteed only for \(k<a_h+1\), so \(X_h(a_h+1)=Q_h(F_{h-1}(a_h+1))\) may be larger than \(X_h(a_h)=Q_h(L)\), and part (d) fails. A label born at \(a_h+1\) would belong to the layer \((a_h-1,a_h+1]\), whose base time \(a_h-1\) precedes the activation of the group's density expansion; the safety argument of the sixth lesson needs the expansion to be enabled at the base time \(b-2\).

## References

- [OpenAI-P] OpenAI, *One Sample Suffices for Matroid Prophet Inequalities against an Almighty Adversary*, OpenAI Math Release preprint, 23 September 2026, Section 3. https://github.com/openai/math/tree/main/preprints/One-Sample-Suffices-for-Matroid-Prophet-Inequalities-against-an-Almighty-Adversary-September-23-2026
- J. Edmonds, *Minimum partition of a matroid into independent subsets*, Journal of Research of the National Bureau of Standards 69B (1965), 67–72, published by NIST. https://doi.org/10.6028/jres.069B.004
- R. Santiago, I. Sergeev and R. Zenklusen (2025) and J. A. Soto (2013) used principal partitions for secretary problems in the random-assignment model; they are named for credit, and the course does not use their results.