Return to Answer

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\}$. 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_{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_{M_i}} \right) \geq \left(1 - \frac{1}{n}\right)^n, $$ which converges to $\frac{1}{e}$ as $n \rightarrow \infty$.

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 \middle\vert \bigwedge_{i \in S} A_i\right) \leq \Pr(A_k) $$ for any fixed event $A_k$ and collection $S$ 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\}$. 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_{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_{M_i}} \right) \geq \left(1 - \frac{1}{n}\right)^n, $$ which converges to $\frac{1}{e}$ as $n \rightarrow \infty$.

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$.

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\}$. 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_{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_{M_i}} \right) \geq \left(1 - \frac{1}{n}\right)^n, $$ which converges to $\frac{1}{e}$ as $n \rightarrow \infty$.

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$.

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$.