Contents

-

Connected Balanced Subgraphs in Random Regular Multigraphs Under the Configuration Model

Linyuan Lu 1, Austin Mohr1, Laszlé Székely 1
1Department of Mathematics University of South Carolina 1523 Greene Street, Columbia, SC 29208

Abstract

Our previous paper [9] applied a lopsided version of the Lovász Local Lemma that allows negative dependency graphs [5] to the space of random matchings in K2n, 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 multigraph from the configuration model contains at least one from a family of balanced subgraphs in question.