Skip to main content
3 of 4
Added reference to paper
David Roberts
  • 35.5k
  • 11
  • 124
  • 349

How should the proof of the XYZ theorem be understood?

The XYZ Theorem of Shepp [1] 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?

[1] L.A. Shepp, The XYZ conjecture and the FKG inequality, Ann. Probab. 10 (1982) 824--827, doi:10.1214/aop/1176993791

Hao
  • 571
  • 4
  • 9