| The configuration model of Bollobas is the right way to look at random regular graphs or random graphs with prescribed degree sequence. Linyuan Lu and Szekely investigated settings, in which the Lopsided Lovasz Local Lemma of Spencer and Erdos that requires only negative dependency graphs instead of dependency graphs works. (The difficulty is at finding negative dependency graphs that are not dependency graphs.) The new settings in which the Lopsided Lovasz Local Lemma works include the uniform probability space of perfect matchings in complete and complete bipartite graphs, when restrict our interest to canonical events. (An event is canonical, if it consists of all extensions of a partial matching to perfect matching.) As the configuration model derives random graphs with prescribed degree sequence from random matchings in the configuration space, it is no surprise that we can obtain lower bounds on the probability of certain properties. More surprising is that these lower bounds are tight for many properties, and matching upper bounds can be obtained, resulting in new proofs for many results on asymptotic enumeration, and also some new results. While the earlier results of Wormald, McKay and others on asymptotic enumeration usually allow a wider range of parameters, our results are more versatile and fairly easily can be adapted for modified problems. An interesting application is revisiting a classical result of Erdos: existence of graphs with large girth and large chromatic number. We show that almost all graphs with prescribed degree sequence and girth have large chromatic number, if the degree sequence satisfies some non-degeneracy conditions. |
|