Geri Dön

Defective Ramsey numbers and defective cocolorings

Kusurlu Ramsey sayıları ve kusurlu tam boyamalar

  1. Tez No: 325551
  2. Yazar: AHU AKDEMİR
  3. Danışmanlar: YRD. DOÇ. TINAZ EKİM AŞICI
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Matematik, Industrial and Industrial Engineering, Mathematics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2012
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. Amasya kenti'nin fiziksel yapısının tarihsel gelişimi

    Historical evolution of the physical structure of Amasya

    KANİ KUŞUCULAR

    Doktora

    Türkçe

    Türkçe

    1994

    Mimarlıkİstanbul Teknik Üniversitesi

    PROF. DOĞAN KUBAN

  2. 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

    Türkçe

    2016

    Anestezi ve ReanimasyonEge Üniversitesi

    Anesteziyoloji ve Reanimasyon Ana Bilim Dalı

    DOÇ. DR. IŞIK ALPER

  3. 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

    Türkçe

    2022

    HukukAnkara Üniversitesi

    Özel Hukuk Ana Bilim Dalı

    PROF. DR. ARİF BURHANETTİN KOCAMAN

  4. Türk İdare Hukukunda kusurlu sorumluluk

    Defective liability in Turkish Administrative Law

    FURKAN MEDAR

    Yüksek Lisans

    Türkçe

    Türkçe

    2017

    HukukKocaeli Üniversitesi

    Kamu Hukuku Ana Bilim Dalı

    DOÇ. DR. MÜSLÜM AKINCI

  5. Defective fruits detection using deep convolutional networks

    Derin konvolüsyon ağları ile bozulmuş meyvelerin tespiti

    RHUDIE GRACE ZANG EDZANG

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGebze Teknik Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MEHMET GÖKTÜRK