Teorema 6.29. Teorema Fishburn.
Misalkan \(\PXP\) suatu poset. Poset \(\bfP\) merupakan urutan interval jika dan hanya jika tidak memuat subposet yang isomorfik dengan \(\bftwo+\bftwo\text{.}\)
Subbab 6.6 Urutan Interval
Ketika membahas Teorema Dilworth, kita menyebutkan bahwa aspek-aspek algoritmiknya akan ditunda hingga bagian selanjutnya dalam buku ini. Namun, ada satu kelas urutan penting yang solusi lengkapnya mudah diperoleh.
Suatu poset \(\PXP\) disebut urutan interval jika terdapat fungsi \(I\) yang memetakan setiap elemen \(x\in
X\) ke suatu interval tertutup \(I(x)=[a_x,b_x]\) pada garis bilangan real \(\reals\) sedemikian sehingga untuk semua \(x\text{,}\) \(y\in X\text{,}\) berlaku \(x\lt y\) dalam \(P\) jika dan hanya jika \(b_x\lt a_y\) dalam \(\reals\text{.}\) Kita menyebut \(I\) sebagai representasi interval dari \(\bfP\text{,}\) atau singkatnya sebagai representasi. Agar ringkas, setiap kali kita mengatakan bahwa \(I\) merupakan representasi suatu urutan interval \(\PXP\text{,}\) kita akan menggunakan notasi alternatif \([a_x,b_x]\) untuk interval tertutup \(I(x)\text{.}\) Selain itu, kita menggunakan \(|I(x)|\) untuk menyatakan panjang interval tersebut, i.e., \(|I(x)|=b_x-a_x\text{.}\) Kembali ke poset \(\bfP_3\text{,}\) representasi yang ditampilkan dalam Gambar 6.28 menunjukkan bahwa poset ini merupakan urutan interval.
Diagram Hasse poset enam titik di sebelah kiri dan representasi intervalnya di sebelah kanan; setiap ruas interval berlabel elemen poset yang diwakilinya.
Perhatikan bahwa titik-titik ujung interval yang digunakan dalam suatu representasi tidak harus berbeda. Bahkan, titik-titik berbeda \(x\) dan \(y\) dari \(X\) dapat memenuhi \(I(x)=I(y)\text{.}\) Kita juga mengizinkan interval degenerat, i.e., interval berbentuk \([a,a]\text{.}\) Di sisi lain, suatu representasi dikatakan pembeda jika semua intervalnya tidak degenerat dan semua titik ujungnya berbeda. Cukup mudah untuk melihat bahwa setiap urutan interval memiliki representasi pembeda.
Seperti yang akan segera kita lihat, urutan interval dapat dicirikan secara ringkas melalui subposet terlarang. Sebelum menyatakan pencirian ini, kita perlu memperkenalkan sedikit notasi tambahan. Dengan \(\bfn\) (untuk bilangan bulat \(n\geq 1\)), kita maksudkan rantai dengan \(n\) titik. Lebih tepatnya, kita mengambil himpunan dasar \(\{0,1,\dots,n-1\}\text{,}\) dengan \(i \lt j\) dalam \(\bfn\) jika dan hanya jika \(i\lt
j\) dalam \(\ints\text{.}\) Jika \(\PXP\) dan \(\QYQ\) merupakan poset dengan \(X\) dan \(Y\) saling lepas, maka \(\bfP+\bfQ\) adalah poset \(\bfR=(X\cup
Y,R)\) yang urutan parsialnya diberikan oleh \(z\leq w\) dalam \(R\) jika dan hanya jika (a) \(z,w\in
X\) dan \(z\leq w\) dalam \(P\text{,}\) atau (b) \(z,w\in Y\) dan \(z\leq w\) dalam \(Q\text{.}\) Jadi, \(\bfn+\bfm\) terdiri atas sebuah rantai dengan \(n\) titik dan sebuah rantai dengan \(m\) titik, tanpa keterbandingan di antara keduanya. Secara khusus, \(\bftwo+\bftwo\) dapat dipandang sebagai poset empat titik dengan himpunan dasar \(\{a,b,c,d\}\text{,}\) dengan \(a\lt b\) dan \(c\lt d\) sebagai satu-satunya relasi (selain relasi-relasi yang diperlukan agar relasinya refleksif).
Bukti.
Kita hanya menunjukkan bahwa urutan interval tidak dapat memuat subposet yang isomorfik dengan \(\bftwo+\bftwo\text{;}\) pembuktian arah sebaliknya ditunda hingga bagian berikutnya. Sekarang, misalkan \(\PXP\) merupakan poset, \(\{x,y,z,w\}\subseteq X\text{,}\) dan subposet yang ditentukan oleh keempat titik ini isomorfik dengan \(\bftwo+\bftwo\text{.}\) Kita akan menunjukkan bahwa \(\bfP\) bukan urutan interval. Andaikan sebaliknya bahwa \(I\) merupakan representasi interval dari \(\bfP\text{.}\) Tanpa mengurangi keumuman, kita boleh mengasumsikan bahwa \(x\lt y\) dan \(z\lt w\) dalam \(P\text{.}\) Jadi, \(x\Vert w\) dan \(z\Vert y\) dalam \(P\text{.}\) Dengan demikian, \(b_x\lt
a_y\) dan \(b_z \lt a_w\) dalam \(\reals\text{,}\) sehingga \(a_w \le b_x \lt a_y \le b_z\text{,}\) yang merupakan kontradiksi.
