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.

Let $X$ count $k$-cliques in a binomial random graph on $m$ vertices and $Y$ count distinct ordered pairs sharing an edge. The clique conflict graph gives $Z_k\ge X^2/(X+Y)$: order its vertices randomly and keep each one preceding all its neighbours, then apply the Cauchy-Schwarz inequality. Another application gives $\mathbb{E}{Z}_k\ge (\mathbb{E}X{)}^2/(\mathbb{E}X+\mathbb{E}Y)$. If $\mathbb{E}Y/(\mathbb{E}X{)}^2=O(k^4/m^2)$ and $1/\mathbb{E}X$ is no larger, then $\mathbb{E}{Z}_k=\Omega (m^2/k^4)$. Changing one edge changes $Z_k$ by at most one, so the Azuma-Hoeffding inequality for an edge-exposure martingale yields the displayed exponential absence bound. This supports a union bound over exponentially many adaptive candidate subsets.

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.