Skip to main content
2 of 4
added 8 characters in body
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171

How should the proof of the XYZ theorem be understood?

The XYZ Theorem of Shepp states that for a given poset $P$. Consider the probability space of all the linear extensions of $P$, where each possible extension is equally likely. Then for any three elements $x, y, z \in P$, we have $$\mathbb{P}[x \le y \textrm{ and } x \le z] \ge \mathbb{P}[x \le y] \cdot \mathbb{P}[x \le z].$$

Shepp's proof uses FKG inequality on a distributive lattice on $[m]^n$, in which $x \le y$ iff $x_1>y_1$ and $x_i-x_1 \le y_i-y_1$ for $i \ge 2$, and the meet and join are defined as: $$(x \wedge y)_i=\min\{x_i-x_1, y_i-y_1\}+\max\{x_1, y_1\},$$ $$(x \vee y)_i=\max\{x_i-x_1, y_i-y_1\}+\min\{x_1, y_1\}.$$

I can verify that this gives a distributive lattice and thus FKG applies. But what is the motivation behind it, i.e. what makes Shepp believe that this is even a distributive poset?

Hao
  • 571
  • 4
  • 9