Edge-disjoint clique packing ($Z_r(G)$)

An edge-disjoint clique packing is a collection of $r$-cliques no two of which share an edge; they may share vertices. Its maximum cardinality $Z_r(G)$ changes by at most one when a single edge is toggled. Removing that edge destroys at most one packed clique, which makes this variable suitable for an edge-exposure martingale.

The clique conflict graph has one vertex for each $r$-clique of a fixed graph, and joins two when they share an edge. Its independent sets correspond exactly to edge-disjoint clique packings. The Caro-Wei bound converts clique-count and overlap estimates into a packing lower bound.