Connected Balanced Subgraphs in Random Regular Multigraphs Under the Configuration Model

摘要

Our previous paper [9] applied a lopsided version of the Lovasz Local Lemma that allows negative dependency graphs [5] to the space of random matchings in K_(2n), deriving new proofs to a number of results on the enumeration of regular graphs with excluded cycles through the configuration model [3]. Here we extend this from excluded cycles to some excluded balanced subgraphs, and derive asymptotic results on the probability that a random regular multi-graph from the configuration model contains at least one from a family of balanced subgraphs in question.