Perpustakaan Digital ITB

Bilangan Ramsey merupakan salah satu konsep fundamental dalam teori graf, yang berkaitan dengan penentuan orde minimum untuk menjamin adanya struktur graf tertentu dalam suatu graf lengkap. Bilangan Ramsey ini telah dikaji secara ekstensif, lihat (Radziszowski, 2021). Selanjutnya, berbagai studi perluasan perumuman dan variasi dari teori Ramsey telah banyak dikembangkan, diantaranya bilangan Ramsey untuk graf (Radziszowski, 2021), bilangan Ramsey sisi (Erd?os dkk., 1978), bilangan Ramsey bipartit (Beineke dan Schwenk, 1975a), bilangan Ramsey multipartit-ukuran (Burger dan Van Vuuren, 2004b), bilangan Ramsey multipartit-himpunan (Burger dan Van Vuuren, 2004a), bilangan k-Ramsey (Andrews dkk., 2017), dan graf Ramsey minimal (Burr dkk., 1976). Untuk j ? 2, bilangan Ramsey multipartit-ukuran dari graf sederhana G1,G2, dinotasikan dengan mj(G1,G2), adalah bilangan asli terkecil n sedemikian sehingga untuk setiap pewarnaan sisi pada graf Kj×n senantiasa terdapat subgraf monokromatik Gi untuk suatu i ? {1, 2}. Sedangkan, bilangan Ramsey multipartithimpunan Mj(G1,G2) merupakan bilangan asli terkecil n sedemikian sehingga setiap pewarnaan sisi pada graf Kn×j senantiasa menghasilkan subgraf monokromatik Gi untuk suatu i ? {1, 2}. Kedua bilangan Ramsey tersebut diperkenalkan oleh Burger dan Van Vuuren (2004a dan 2004b) dengan mengkaji Gi sebagai graf multipartit lengkap. Selanjutnya, bilangan Ramsey multipartit-ukuran mulai dikaji untuk graf Gi yang tidak harus graf lengkap oleh Syafrizal, Baskoro, dan Uttunggadewa (2005). Lebih lanjut, kajian bilangan Ramsey multipartit-ukuran dengan dua warna telah dilakukan pada graf bintang (Lusiani, Baskoro, dan Saputro (2016, 2019a, 2019b, 2020)). Sementara itu, Perondi dan Carmelo (2019) mengaitkan bilangan Ramsey multipartit dengan eksistensi matriks Hadamard dan graf regular kuat. Lebih jauh, mereka menunjukkan bahwa jika terdapat graf regular kuat dengan parameter (4n? 2, 2n ? 2, n ? 2n ? 1) dan matriks Hadamard simetris berorde m dengan m ? 4n, maka berlaku Mm(K2,m(n?1)+1,K2,m(n?1)+1) = 4n ? 1. Disertasi ini mengembangkan lebih lanjut hubungan antara bilangan Ramsey multipartit-ukuran dan multipartit-himpunan dengan struktur aljabar. Secara khusus, disertasi ini menggunakan matriks Hadamard yang diperumum untuk memperoleh bilangan Ramsey multipartit-ukuran dan multipartit-himpunan dari graf bipartit. Kemudian, diperoleh bilangan Ramsey multipartit-ukuran dan multipartit-himpunan dari graf bintang, graf galaksi, dan graf bintang ganda. Hasil dari disertasi ini, terutama tentang hubungan matriks Hadamard yang diperluas dengan bilangan Ramsey multipartit-himpunan dan ukuran, membuka peluang eksplorasi lebih lanjut, khususnya dalam pengembangan metode aljabar untuk menentukan nilai bilangan Ramsey multipartit pada kelas graf yang lebih kompleks. Disertasi ini juga mengkaji bilangan k-Ramsey multiwarna dan memperkenalkan konsep bilangan k-Ramsey diperumum. Perumuman dilakukan dengan memperluas domain graf dari semula graf k-partit seimbang lengkap menjadi graf k-partit lengkap. Dalam studi ini, bilangan k-Ramsey dari graf bintang untuk kasus multiwarna berhasil ditentukan, dan diperoleh pula batas atas untuk bilangan k-Ramsey diperumum dari graf bintang pada kasus multiwarna. Selain itu, disertasi ini menentukan nilai eksak bilangan k-Ramsey diperumum untuk pasangan graf (C4,C4) serta pasangan (K1,4,K1,4).