A negative dependency graph is as a dependency graph except that independence is replaced with the inequality $$\Pr\left(A_k \mid \bigwedge_{i=1} A_i\right) \leq \Pr(A_i)$$ for any fixed event $A_k$ and collection $\{A_i \mid i \in [n]\}$ of non-neighbors of $A_k$. Erdos and Spencer showed the Lovasz Local Lemma holds with negative dependency graphs in place of dependency graphs.
Let $\Omega$ be the probability space of all perfect matchings of $K_{n,n}$ equipped with the uniform distribution. For a partial matching $M$ of $K_{n,n}$, define the event $$A_M = \{M^\prime \in \Omega \mid M \subseteq M^\prime\}$$ (all perfect matching that contain the partial matching $M$).
Given a collection $\mathcal{M}$ of partial matchings of $K_{n,n}$, construct a graph with vertex set $\{A_M \mid M \in \mathcal{M}\}$ and set two matchings adjacent if their union is not again a matching. L. Lu and L. A. Szekely showed this graph is a negative dependency graph.
Finally we can address the problem at hand. Let the partite sets of $K_{n,n}$ be $\{1, \dots, n\}$ and $\{1^\prime, \dots, n^\prime\}$. Let $\mathcal{M}$ consist of the one-edge matchings $ii^\prime$ for all For $1 \leq i \leq n$. , let $M_i$ be the one-edge matching $ii^\prime$. Viewing perfect matchings of $K_{n,n}$ as permutations of an $n$-element set, the event $\bigwedge_{i=1}^n \overline{A_i}$ overline{A_{M_i}}$contains precisely those permutations not having a fixed point. Choosing$x_i = \frac{1}{n}$for the purposes of the Lopsided Lovasz Local Lemma, we get $$\Pr\left( \bigwedge_{i=1}^n \overline{A_i} overline{A_{M_i}} \right) \geq \left(1 - \frac{1}{n}\right)^n,$$ which converges to$\frac{1}{e}$as$n \rightarrow \infty$. 2 added 18 characters in body L. Lu and L. A. Szekely have successfully applied the Lopsided (i.e. Negative Dependency Graph) Lovasz Local Lemma to this problem. A negative dependency graph is as a dependency graph except that independence is replaced with the inequality $$\Pr\left(A_k \mid \bigwedge_{i=1} A_i\right) \leq \Pr(A_i)$$ for any fixed event$A_k$and collection$\{A_i \mid i \in [n]\}$of non-neighbors of$A_k$. Erdos and Spencer showed the Lovasz Local Lemma holds with negative dependency graphs in place of dependency graphs. Let$\Omega$be the probability space of all perfect matchings of$K_{n,n}$equipped with the uniform distribution. For a partial matching$M$of$K_{n,n}$, define the event $$A_M = \{M^\prime \in \Omega \mid M \subseteq M^\prime\}$$ (all perfect matching that contain the partial matching$M$). Given a collection$\mathcal{M}$of partial matchings of$K_{n,n}$, construct a graph with vertex set$\{A_M \mid M \in \mathcal{M}\}$and set two matchings adjacent if their union is not again a matching. L. Lu and L. A. Szekely showed this graph is a negative dependency graph. Finally we can address the problem at hand. Let the partite sets of$K_{n,n}$be$\{1, \dots, n\}$and$\{1^\prime, \dots, n^\prime\}$. Let$\mathcal{M}$consist of the one-edge matchings$ii^\prime$for all$1 \leq i \leq n$. Viewing perfect matchings of$K_{n,n}$as permutations of an$n$-element set, the event$\bigwedge_{i=1}^n \overline{A_i}$contains precisely those permutations not having a fixed point. Choosing$x_i = \frac{1}{n}$for the purposes of the Lopsided Lovasz Local Lemma, we get $$\Pr\left( \bigwedge_{i=1}^n \overline{A_i} \right) \geq \left(1 - \frac{1}{n}\right)^n,$$ which converges to$\frac{1}{e}$as$n \rightarrow \infty$. 1 Lu and Szekely have successfully applied the Lopsided (i.e. Negative Dependency Graph) Lovasz Local Lemma to this problem. A negative dependency graph is as a dependency graph except that independence is replaced with the inequality $$\Pr\left(A_k \mid \bigwedge_{i=1} A_i\right) \leq \Pr(A_i)$$ for any fixed event$A_k$and collection$\{A_i \mid i \in [n]\}$of non-neighbors of$A_k$. Erdos and Spencer showed the Lovasz Local Lemma holds with negative dependency graphs in place of dependency graphs. Let$\Omega$be the probability space of all perfect matchings of$K_{n,n}$equipped with the uniform distribution. For a partial matching$M$of$K_{n,n}$, define the event $$A_M = \{M^\prime \in \Omega \mid M \subseteq M^\prime\}$$ (all perfect matching that contain the partial matching$M$). Given a collection$\mathcal{M}$of partial matchings of$K_{n,n}$, construct a graph with vertex set$\{A_M \mid M \in \mathcal{M}\}$and set two matchings adjacent if their union is not again a matching. Lu and Szekely showed this graph is a negative dependency graph. Finally we can address the problem at hand. Let the partite sets of$K_{n,n}$be$\{1, \dots, n\}$and$\{1^\prime, \dots, n^\prime\}$. Let$\mathcal{M}$consist of the one-edge matchings$ii^\prime$for all$1 \leq i \leq n$. Viewing perfect matchings of$K_{n,n}$as permutations of an$n$-element set, the event$\bigwedge_{i=1}^n \overline{A_i}$contains precisely those permutations not having a fixed point. Choosing$x_i = \frac{1}{n}$for the purposes of the Lopsided Lovasz Local Lemma, we get $$\Pr\left( \bigwedge_{i=1}^n \overline{A_i} \right) \geq \left(1 - \frac{1}{n}\right)^n,$$ which converges to$\frac{1}{e}$as$n \rightarrow \infty\$.