Mathematics – Combinatorics
Scientific paper
2009-05-25
Mathematics
Combinatorics
Scientific paper
Our previous paper applied a lopsided version of the Lov\'asz Local Lemma that allows negative dependency graphs to the space of random injections from an $m$-element set to an $n$-element set. Equivalently, the same story can be told about the space of random matchings in $K_{n,m}$. Now we show how the cited version of the Lov\'asz Local Lemma applies to the space of random matchings in $K_{2n}$. We also prove tight upper bounds that asymptotically match the lower bound given by the Lov\'asz Local Lemma. As a consequence, we give new proofs to results on the enumeration of $d$-regular graphs. The tight upper bounds can be modified to the space of matchings in $K_{n,m}$, where they yield as application asymptotic formulas for permutation and Latin rectangle enumeration problems. The strength of the method is shown by a new result: enumeration of graphs by degree sequence or bipartite degree sequence and girth. As another application, we provide a new proof to the classical probabilistic result of Erd\H os that showed the existence of graphs with arbitrary large girth and chromatic number. If the degree sequence satisfies some mild conditions, almost all graphs with this degree sequence and prescribed girth have high chromatic number.
Lu Linyuan
Szekely Laszlo A.
No associations
LandOfFree
A new asymptotic enumeration technique: the Lovasz Local Lemma does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A new asymptotic enumeration technique: the Lovasz Local Lemma, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A new asymptotic enumeration technique: the Lovasz Local Lemma will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-294459