Defective Ramsey numbers and defective cocolorings
Kusurlu Ramsey sayıları ve kusurlu tam boyamalar
- Tez No: 325551
- Danışmanlar: YRD. DOÇ. TINAZ EKİM AŞICI
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Matematik, Industrial and Industrial Engineering, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2012
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 184
Özet
Ramsey sayısı, R(a, b) herhangi n kişi arasında her zaman birbirini tanıyan a kişi ya da birbirini tanımayan b kişi olmasını sağlayacak en küçük pozitif n tam sayısını vermektedir. Küçük a ve b değerleri için Ramsey sayıları tam olarak bilinmektedir ve bilinmeyen Ramsey sayıları için alt ve üst sınırlar hesaplanmıştır. Bir Ramsey sayısının alt ve üst sınırları, bu Ramsey sayısının alabileceği sırasıyla en küçük ve büyük değerleri ifade etmektedir. Bu çalışmada Ramsey sayılarının bir genelleştirmesi olan kusurlu Ramsey sayıları üzerinde çalıştık. Kusurlu Ramsey sayısı, Rk(a, b), n kişi arasında k istisnayla her zaman birbirini tanıyan a kişi ya da birbirini tanımayan b kişi olmasını sağlayacak en küçük pozitif n tam sayısını vermektedir. Bazı bilinmeyen Rk(a, b) değerleri için alt ve üst sınırları hesapladık ve bunların bazıları için alt sınırları geliştirdik. Ayrıca farklı çizge sınıflarında klasik ve kusurlu Ramsey sayılarını inceledik ve belirli bir çizge sınıfı için tam değerleri veya alt ve üst sınırları veren formüller geliştirdik. İkinci kısımda, çizgelerde tam boyama (cocoloring) problemi üzerinde çalıştık. Bir çizgenin düğümlerini klik ya da da bağımsız kümelere ayırarak her birine bir renk atanmasına problemine tam boyama problemi denir. Klik ya da bağımsız kümeler yerine k-yoğun (k-dense), bir düğümün en fazla k düğüm kaçırdığı klik, ve k-seyrek (k-sparse), bir düğümün en fazla k düğüme bağlanabileceği bağımsız küme, alt çizgelerle ilgilenen kusurlu tam boyama problemi de ele alınmıştır. ck(m) parametresi n düğümlü bütün çizgelerin k-kusurlu olarak en fazla m renkle tam boyanabileceği en büyük n sayısını vermektedir. Bu çalışmada şu sonuçlar elde edilmiştir: c0(4)=12, c1(3)=12 ve c2(2)=10. Ayrıca ck(m) parametresi için alt ve üst sınırlar veren bir formül geliştirildi.
Özet (Çeviri)
Ramsey number, R(a, b), denotes the smallest positive integer n such that, among any n people, there exist a people who know each other or b people who do not know each other. R(a, b) values are known for small a and b values and for unknown R(a, b) values, the lower and upper bounds, namely the minimum and the maximum values that R(a, b) can take, has been calculated. In this study, we study a generalization of Ramsey numbers which is called defective Ramsey numbers. Defective Ramsey number, Rk(a, b), denotes the smallest positive integer n such that, among any n people, there exist a people who know each other or b people who do not know each other with at most k exceptions. We calculate some of the lower and upper bounds on some of the unknown Rk(a, b) values and improve some of the lower bounds. We also study classical and defective Ramsey numbers in some graph classes and derive some formulas that either give the exact value of or an upper bound on Ramsey numbers for a specific graph class. In the second part, we study cocoloring of graphs. Cocoloring of a graph is an assignment of colors to the set of vertices such that each color class induces a clique or an independent set. We also studied defective cocoloring of graphs which considers k-denses, a defective clique in which the vertices can miss at most k vertices, and k-sparses, a defective independent set in which the vertices can be adjacent to at most k vertices, as induced subgraphs. ck(m) is the parameter that gives the maximum graph order n such that all n-graphs can be k-defectively cocolored by using at most m colors. We propose the following results: c0(4) = 12, c1(3) = 12 and c2(2) = 10. We also prove a formula that gives the lower and upper bounds on the ck(m) parameter.
Benzer Tezler
- Amasya kenti'nin fiziksel yapısının tarihsel gelişimi
Historical evolution of the physical structure of Amasya
KANİ KUŞUCULAR
- Donör nefrektomide preoperatif anksiyetenin anesteziden derlenme ve postoperatif ağrı üzerine etkisi
The effects of pre-operative anxiety on anesthetic recovery and post-operative pain in donor nephrectomy
ERBİL TÜRKSAL
Tıpta Uzmanlık
Türkçe
2016
Anestezi ve ReanimasyonEge ÜniversitesiAnesteziyoloji ve Reanimasyon Ana Bilim Dalı
DOÇ. DR. IŞIK ALPER
- Arsa payı karşılığı inşaat sözleşmesinde ayıplı ifa ve sonuçları
Defective performance and consequences in the construction agreement in return for land share
İREM ÖZBAL
Yüksek Lisans
Türkçe
2022
HukukAnkara ÜniversitesiÖzel Hukuk Ana Bilim Dalı
PROF. DR. ARİF BURHANETTİN KOCAMAN
- Türk İdare Hukukunda kusurlu sorumluluk
Defective liability in Turkish Administrative Law
FURKAN MEDAR
- Defective fruits detection using deep convolutional networks
Derin konvolüsyon ağları ile bozulmuş meyvelerin tespiti
RHUDIE GRACE ZANG EDZANG
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGebze Teknik ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DOÇ. DR. MEHMET GÖKTÜRK