Results on matroids, paths of flats, safe samples, marked pivots and the final count, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Greedy over a base — Lemma 1.4. Keeping the labels of Z not spanned by P and the kept ones gives a set independent over P, of size rk(Z | P), spanning Z over P.
• Greedy is optimal — Lemma 2.1. Priority greedy finds an independent set of maximum weight.
• One sample suffices (OpenAI) — Theorem 3.1. Against an adversary who sees all samples, values and coins, a fixed rule earns at least 2^-293 times the expected optimum.
• Fixed-vector guarantee — Proposition 4.1. For a hidden weight vector, sacrificing revealed labels, the expected worst-order reward is at least 2^-293 OPT.
• One-sample simulation — Lemma 4.2. Samples on the sacrificed set and values elsewhere form a vector with the law of the values, independent of the seed.
• The maximum rule — Lemma 2.1. A fair mask used as a threshold makes the most valuable label accepted with probability at least 1/4 in every order.
• Candidate mass — Lemma 3.1. Labels not spanned by more valuable masked labels carry expected rounded weight at most W, and contain an independent set of expected weight W/2.
• Density expansion — Lemma 1.2. The largest maximizer of revealed count minus kappa times rank above a flat is increasing; further rank captures at most kappa revealed labels per unit.
• Path properties — Lemma 2.1. Nested increasing paths of flats; every nonloop is born at the activation time or at a time whose base two steps earlier is enabled.
• Generator budget — Lemma 3.1. A whole nominal path is generated over the lighter path by at most |D_h|/kappa revealed labels.
• Feasibility — Lemma 1.1. Greedy selection within layers of nested flats is independent after every prefix, for every order.
• Order-uniform rank bound — Lemma 3.1. In every order, acceptances of weight at least that of a group are at least its layer rank statistic.
• Telescoping rank cost — Lemma 4.1. Replacing the nominal path by the final path costs at most the group's guards and the guards and generators of heavier groups.
• Disjoint certificates — Lemma 2.1. Adaptive reads of independent bits yield at most log(1/delta) disjoint positive certificates of an increasing event in expectation.
• Exit mass — Lemma 3.1. Read backwards, a label leaves its nominal path at a step with exit probability at least eta with probability more than 1/2.
• Containment — Lemma 4.2. The hybrid step contains the density expansion of the layer base together with all lighter competitors.
• Safe samples (OpenAI) — Lemma 1.1. In expectation at least eta/4 of the revealed comparison labels of a group are safe, up to |D_h|/kappa.
• Sign patterns — Lemma 1.1. n affine functions on R^d have at most sum over l <= d of C(n, l) strict sign patterns.
• Marked pivots (OpenAI) — Lemma 2.1. Inserting at most s occurrences into a marked sequence yields at most 4^s times sum over l <= s of C(n, l) pivot-mark vectors.
• Residual family — Lemma 2.1. All residuals of a group of size n lie in a family of size exp(1000 n log(kappa)/kappa), fixed before the group's masks.
• Sample-to-rank transfer (OpenAI) — Lemma 3.1. For groups of size at least kappa, the expected unrevealed rank is at least (gamma |Y_i| - 2^-23 n_i)/kappa.
• Minimum over orders — Lemma 2.1. For every seed the worst-order rounded reward is at least half the weighted sum of the layer statistics.
• Secretary rule with an adversarial suffix — Corollary 4.1. After a random observed prefix, any suffix order chosen with full knowledge leaves expected reward at least 2^-293 OPT.

Reading order

Read the lessons in order; the fifth and seventh lessons are self-contained and can be read first.