Çizgelerin Sperner sayıları

Abstract

Dört bölümden olu¸san bu tezde Çizgelerin Sperner say¬lar¬tan¬t¬lm¬¸s ve incelenmi¸stir.Bu çal¬¸smaya gerekli olan baz¬temel Çizgeler teorisi ile ilgili tan¬mlarla giri¸s yap¬lm¬¸st¬r.·Ilk bölümde çal¬¸smam¬zla ilgili olan Milner¬n bir teoremine yer verilmi¸stir (Milner,1968). Bu çal¬¸smada Milner¬n bu teoreminin ·Ispat¬Scottdan al¬nm¬¸st¬r (Scott, 1999).·Ikinci bölümde arakesit çizgesi ve bir çizgenin Sperner say¬s¬tan¬t¬lm¬¸st¬r ve her sonluçizgenin bir Sperner say¬s¬oldu¼gu ispatlanm¬¸st¬r. Milner¬n teoremi yard¬m¬yla tam çiz-genin Sperner say¬s¬hesaplanm¬¸st¬r; ayr¬ca iki-çoklu çizgenin de Sperner say¬s¬buradaverilmi¸stir. Bir G çizgesinin verilen herhangi bir v kö¸sesi için vnin Sperner derecesitan¬t¬lm¬¸s ve vnin Sperner derecesi ile vnin kom¸suluklar¬n¬n indirgedi¼gi altçizgenintamsal örtüm say¬s¬aras¬ndaki ili¸skiyi veren bir teorem ispatlanm¬¸st¬r.Üçüncü bölümde, bu çal¬¸sma çizgelerin regüler gerenleriyle geni¸sletilmi¸stir ve regülerSperner say¬lar¬ tan¬mlanm¬¸st¬r. Verilen bir çizgenin bir k-regüler gereninin hangidurumlarda mevcut oldu¼gu incelenmi¸stir. Sperner say¬s¬ ile regüler Sperner say¬s¬aras¬nda ili¸skiye de¼ginilmi¸stir. Örnek olarak tam çizgenin ve tam iki-çoklu çizgeninregüler Sperner say¬lar¬hesaplanm¬¸st¬r.Son bölümde çizgelerin Sperner say¬lar¬için çe¸sitli s¬n¬rlar bulman¬n üzerinde durul-mu¸stur. ·Ilk önce bir çizgenin Sperner say¬s¬n¬n ba¼g¬ms¬zl¬k say¬s¬n¬n iki kat¬ndan dahabüyük veya e¸sit oldu¼gu ifade ve ispat edilmi¸stir. Ard¬ndan bu ifadenin e¸sitlik duru-muna bak¬lm¬¸st¬r; yani bir çizgenin Sperner say¬s¬n¬n, ba¼g¬ms¬zl¬k say¬s¬n¬n iki kat¬nae¸sit oldu¼gu durumlar incelenmi¸stir. Daha sonra da ba¼g¬ms¬zl¬k say¬s¬n¬n iki kat¬n-dan daha büyük oldu¼gu durumlara bak¬lm¬¸st¬r. Bunlar¬n ard¬nda ise bir çizgenin birkenar¬n¬n at¬lmas¬yla ve bir kenar¬n¬n büzülmesiyle Sperner say¬s¬n¬n nas¬l de¼gi¸siklikgösterdi¼gi incelenmi¸stir. Son olarak bir çizgenin Sperner say¬s¬ile bütünleyeninin kro-matik say¬s¬aras¬ndaki ili¸ski aç¬klanm¬¸s, bunun bir sonucu olarak bir çizgenin Spernersay¬s¬n¬n tamsal örtüm say¬s¬ndan daha büyük veya e¸sit oldu¼gu görülmü¸stür.Anahtar Kelimeler: Çizge, Sperner say¬s¬, geren, ba¼g¬ms¬zl¬k say¬s¬.2009, 50 sayfa

In this thesis that consists of four chapters we introduce and study the Spernernumbers of graphs. We begin our work with providing some basic denitions of graphtheory that are needed throughout our thesis.Apart from the common terminologies of graph theory, we supply some of the knownresults such as Milners theorem (Milner, 1968, Katona, 1998) that are related to ourwork in the rst chapter. The proof of Milners theorem that we state here is due toScott (Scott, 1999).The denition of the Sperner number of a graph is given in the second chapter, wherewe also prove that it is well-dened, that is, every nite graph has a Sperner number.We there compute the Sperner number of complete graphs (by use of Milners theorem)and complete bipartite graphs. For any given vertex v of a graph G, we introduce theSperner degree of v, and prove a theorem that relates the Sperner degree of v to theclique-covering number of the subgraph induced by the neighborhoods of v.In chapter three, we extend our work to include uniform realizers of graphs, and denethe regular Sperner numbers. We investigate the existence of a k-regular realizer of agiven graph, and discuss the relation between k-regular Sperner numbers and ordinarySperner numbers of graphs. As examples, we compute k-regular Sperner numbers ofcomplete and complete bipartite graphs.The nal chapter is devoted to nd various bounds on the Sperner numbers of graphs.We prove that the Sperner number of a graph is bounded below by the twice of theindependence number of that graph. In the case of equality, we o¤er a detailed analysisof graphs satisfying this condition. Moreover, we also study those graphs such that thisbound is strict. We there also investigate how the Sperner number is e¤ected undersome graph operations, such as edge-contractions. Finally, we explain the relationbetween the Sperner number of a graph and the chromatic number of its complement.As a result, we prove that the Sperner number of a given graph is greater than or equalto the clique-covering number of the graph.Keywords: Graph, Sperner number, realizer, independence number.2009, 50 pages