Greedy approximation algorithms for sparse collections

We describe a greedy algorithm that approximates the Carleson constant of a collection of general sets. The approximation has a logarithmic loss in a general setting, but is optimal up to a constant with only mild geometric assumptions. The constructive nature of the algorithm gives
additional information about the almost disjoint structure of sparse collections. As applications, we give three results for collections of axis-parallel rectangles in every dimension. The first is a constructive proof of the equivalence between Carleson and sparse collections, first shown by H¨anninen. The second is a structure theorem proving that every finite collection E can be partitioned into O(N) sparse subfamilies, where N is the Carleson constant of E. We also give examples showing that such a decomposition is impossible when the geometric assumptions are dropped. The third application is a characterization of the Carleson constant involving only L1,∞ estimates.