Lewati ke konten utama

Indeks Sblm Naik Lnjt

\(\newcommand{\set}[1]{\{#1\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\text{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\ds}{\displaystyle} \newcommand{\mbf}[1]{\mathbf{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Subbab 11.2 Bilangan Ramsey Kecil

Menentukan secara tepat bilangan Ramsey \(R(m,n)\) yang disebutkan dalam Teorema 11.2 ternyata merupakan persoalan yang terkenal sangat sulit, dan hanya segelintir nilainya diketahui secara tepat. Secara khusus, \(R(3,3)=6\) dan \(R(4,4)=18\text{,}\) sedangkan \(43\le R(5,5)\le 49\text{.}\) Matematikawan Hungaria terkemuka Paul Erdős berulang kali mengatakan bahwa nilai tepat \(R(5,5)\) mungkin dapat ditentukan jika seluruh bakat matematika di dunia dipusatkan pada persoalan tersebut. Namun, ia juga mengatakan bahwa mencari nilai tepat \(R(6,6)\) mungkin melampaui kemampuan kolektif kita.

Tabel berikut menyajikan informasi tentang bilangan Ramsey \(R(m,n)\) ketika \(m\) dan \(n\) sedikitnya \(3\) dan paling banyak \(9\text{.}\) Jika sebuah sel berisi satu bilangan, bilangan itu merupakan jawaban tepat. Jika terdapat dua bilangan, keduanya menyatakan batas bawah dan batas atas.

	\(n\)	3	4	5	6	7	8	9
\(m\)
3		6	9	14	18	23	36	39
4			18	25	36, 41	49, 61	58, 84	73, 115
5				43, 49	58, 87	80, 143	101, 216	126, 316
6					102, 165	113, 298	127, 495	169, 780
7						205, 540	217, 1031	241, 1713
8							282, 1870	317, 3583
9								565, 6588

Gambar 11.3. Bilangan Ramsey kecil \(R(m,n)\)

Untuk data tambahan (atau yang lebih mutakhir), lihat Dynamic Survey #DS1: “Small Ramsey Numbers” karya Stanisław Radziszowski dalam Electronic Journal of Combinatorics. (Gambar 11.3 terakhir diperbarui menggunakan versi artikel tersebut bertanggal 12 Januari 2014.)

Sblm Ke Atas Lnjt