On the dimension theory of partially ordered sets and graph coloring
Kısmi sıralı kümelerde boyut kuramı ve çizge renklendirme
Yazar: MEHMET AKİF YETİM
Danışman: PROF. DR. YUSUF CİVAN
Süleyman Demirel Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Ana Bilim Dalı
Derece: Yüksek Lisans, 2014
Konu: Matematik = Mathematics
Dizin: Hiperçizgeler = Hypergraphs ; Latis sıralanmış gruplar = Lattice ordered groups

Özet:
Dört bölümden oluşan bu tezde kısmi sıralı kümelerde boyut, çizge renklendirme ve kenar örtümleri konuları ele alınmıştır. Bu çalışmanın temel amacı, kısmi sıralı kümelerde boyut kavramı ve özelliklerini çizge renklendirme ve örtümleri yardımıyla inceleyerek boyut ve renklendirme arasındaki yeni ilişkilerin varlığını orataya koymak ve boyut kuramının mevcut bazı açık problemlerine çözüm aramaktır.
Boyut kuramıyla ilgili kısa bir literatür özeti ve çalışmamızın motivasyonunun verildiği ilk bölümün ardından gelen ikinci bölümde, kısmi sıralı kümeler ve çizgeler ile ilgili temel kavram ve notasyonlara yer verilmiştir.
Üçüncü bölümde Dilworth'un ünlü zincir ve antizincir örtüm teoremlerinin ardından kısmi sıralı kümelerde genleşme, geren ve boyut kavramları tanıtılmıştır. Bir kısmi sıralı kümenin tam sıralı genleşmelerinin bir ailesinin bu kümenin bir gereni olması için gerek ve yeter koşullar ifade edilerek bu karakterizasyon için gerekli olan ardışık döngü, keskin ardışık döngü ve kritik ikili kavramları tanıtılmıştır. Hiraguchi (1955)'nin bir kısmi sıralı kümeden bir veya birden fazla eleman, zincir veya antizinciri çıkarmanın boyutu nasıl etkilediğini belirten sonuçlarına yer verilmiştir. Bir kısmi sıralı kümenin boyutu için mevcut olan üst sınırlara ve n-elemanlı bir kısmi sıralı kümenin boyutunun alabileceği maksimum değerinin bir analizine yer verilmiştir. Ayrıca bir kısmi sıralı kümenin boyutunun belirlenmesi probleminin hesaplamsal karmaşıklığı incelenmiştir.
Dördüncü bölümde, Felsner ve Trotter (2000)'ın bir kısmi sıralı kümenin boyutunun bu kümenin karşılaştırılamayan (veya kritik) ikililerinin oluşturduğu hiperçizgelerinin kromatik sayısına eşit olduğu sonucunun verilmesinin ardından, bu sonuç yönlü çizgeler için genelleştirilmiştir. Bir kısmi sıralı kümenin boyutunun bu  kümenin hem karşılaştırılamayan ve hem de kritik ikililerinin yönlü çizgesinin dikromatik sayısına eşit olduğu ispatlanmıştır. Yannakakis (1982)'in önemli bir sonucu olan, iki parçalı bir kısmi sıralı kümenin aralık boyutunun bu kısmi sıralı kümenin örtü çizgesinin iki-parçalı tümleyeninin ardıl-üçgensel örtüm sayısına eşit olmasından faydalanılarak; herhangi bir kısmi sıralı kümenin boyutunun, bu kümenin yansımasının örtü çizgesinin iki-parçalı tümleyeninin ardıl-üçgensel örtüm sayısına eşit olduğu gösterilmiştir. Bu eşitlikten yola çıkılarak, Dilworth (1950)'un bir kısmi sıralı kümenin boyutunu, genişliği ile üstten sınırladığı teoremine alternatif bir ispat verilerek bir kısmi sıralı kümenin boyutu için çizge kenar-baskınlık sayısına bağlı yeni bir üst sınır elde edilmiştir. Çizgelerde sıra boyutu tanıtılarak bir çizgenin boyutunun çizge renklendirme problemi olarak ele alınıp alınamayacağı araştırılmıştır. Ayrıca, Hiraguchi (1950)'nin kaldırılabilir ikilinin varlığını özel bir durum için doğrulayan bir sonucu da çizgelerde ardıl-üçgensel örtüm yardımıyla alternatif olarak ispatlanarak bu sav için yeni bir yaklaşım sunulmuştur. Son olarak, boyut kuramı için hala açık olan bazı problemlere yer verilmiştir.

Abstract:
In this thesis, which consists of four chapters, we study the dimension of partially ordered sets (posets in short), graph coloring and covering. The main goal of this dissertation is to investigate the concept and the combinatorial properties of dimension theory by means of graph coloring and covering, explore new relations between poset dimension and graph coloring, and to suggest some methods concerning some open problems.
After the first chapter which gives a brief summary of literature and expressing our motivation of this study, the second chapter provides preliminary definitions and notations which we use in the next two chapters.
In chapter three, which begins with Dilworth (1950)'s famous chain and antichain covering theorems, we introduce the concept of order dimension. After definitions of extension, realizer and dimension, we provide known necessary and sufficient conditions for a family of linear extensions to be a realizer. Alternating and strict alternating cycles are introduced for further characterizations of realizers. We also give Hiraguchi's results that state the effects of removing point(s), a chain and an antichain on the dimension of any poset. An analysis on the lower bouds for the maximum value of the dimension of an n-element poset, and upper bounds due to Dilworth (1950) and Hiraguchi (1955) are stated before ending the third chapter together with a discussion of the complexity of partial order dimension problem.
In chapter four, we extend the result of Felsner and Trotter (2000), stating the equality of the dimension of a poset and the chromatic number of its hypergraph of both incomparable and critical pairs, by proving that the dimension of any poset equals to the dichromatic (acyclic chromatic) number of its directed graph of incomparable or critical pairs. Taking the advantage of the fact that the interval dimension of a bipartite poset equals to the cochordal cover number of its bipartite complement, we also show that the dimension of any poset is just the cochordal cover number of bipartite complement of the cover graph of its split. By using this relation, we gave an alternative proof of Dilworth (1950)'s theorem which provides an upper bound on the dimension of a poset by its width. We also bound the dimension of any poset with edge-domination number of a particular graph related to it. After introducing order dimension for simple graphs, we investigate its connection with graph coloring. Moreover, we suggest a new approach for the removable pair conjecture, based on cochordal covering of graphs, by giving an alternative proof of Hiraguchi (1955)'s theorem which verifies the conjecture in a particular case. In addition, we present several problems of dimension theory, which remain open so far.