The combinatorial cost

We study the combinatorial analogues of the classical invariants of measurable equivalence relations. We introduce the notion of cost and $\beta$-invariants (the analogue of the first $L^2$-Betti number introduced by Gaboriau) for sequences of finite graphs with uniformly bounded vertex degrees and examine the relation of these invariants and the rank gradient resp. mod $p$ homology gradient invariants introduced by Lackenby for residually finite groups.