A generalized switching method for combinatorial estimation

The method of switchings is a standard tool for enumerative and probabilistic applications in combinatorics. In its simplest form, it analyses a relation between two sets to estimate the ratio of their sizes. Via a sequence of such pairwise ratios, the relative sizes of a larger family of sets can be estimated. However, in some situations, the available relations might not form a simple chain in this manner. For example, a relation might be denned by an operation that takes an object in one set and converts it to an object that is only known to lie in some subfamily of other sets (rather than in a single known other set). In this article, we describe this situation in a general setting and present it as an optimisation problem. Then we prove that its optimal solution can be assumed to have a very simple form. To illustrate this result we give two examples. First we extend a special case of a lemma of Greenhill and McKay (2006) that bounds the probability of large entries in certain integer matrices. Then we strengthen a lemma of McKay, Wormald and Wysocka (2004) that bounds the number of edges that lie in short cycles in a random regular graph.