What’s the Absorption Method?

Question

What’s the absorption method in extremal combinatorics?

Is it related to the absorption law from discrete math? Or is it related to renormalization groups and dimensionality reductions of graphs?

Answer 1

The absorption method is a strategy for solving packing problems; it is not related to the other things you mention.

The packing problems are usually graph-theoretical, but you can imagine that we're talking about tiling a chessboard with dominoes, or something like that. With an actual chessboard, we have a bird's-eye view of the "correct" way to tile, but we usually don't have that with harder problems; our best attempt might look more like "plop dominoes onto the chessboard randomly until there's no more space left".

The absorption method tries to solve this, without having to be any more clever most of the time.

The key ingredient is finding an absorber in the chessboard: a particularly nicely shaped section of the board that we understand very well, with the following absorbing property: we know how to tile any region that consists of the absorber plus a few scattered pieces.

To use the absorber, we do the following:

1. Find the absorber and set it aside.
2. Use a not-very-good heuristic to tile the rest of the chessboard, without touching any part of the absorber. This will leave a few scattered pieces that we can't tile, because our heuristic isn't very good.
3. Use the absorbing property to tile both the absorber and the leftover scattered pieces.

Here is an explanation of how it works in a case where we're packing edge-disjoint subgraphs into a graph, from Optimal packing of bounded-degree trees by F. Joos, J. Kim, D. Kühn, and D. Osthus:

Roughly speaking, an absorbing approach to find an optimal packing means that we first find and remove an absorbing graph $G_{\text{abs}}$ from the host graph $G$. In our case, we would then aim to find a near-optimal packing $\phi$ of most of the trees $T_i$ into $G−E(G_{\text{abs}})$, which leaves some sparse remainder $G_{\text{rem}}$ of $G$ uncovered. The properties of $G_{\text{abs}}$ then should ensure that we can find an optimal packing of the remaining trees into $G_{\text{abs}} \cup G_{\text{rem}}$, altogether leading to an (optimal) packing of $T_1, \dots ,T_n$ into $G$.