Weak colorings of steiner triple systems

Abstract

Bir Steiner Äuc.lÄu sistemi (S ÄUS), (S,T) s. eklinde bir s³ral³ ikili ile ifade edilebilir,Äoyleki, bu ifadede S sistemin elemanlar kÄumesini, T bu elemanlar kÄumesinin 3elemanl³ baz³ altkÄumelerinden olus.an bir kÄumeyi temsil eder. T kÄumesi Äuzerindekikos.ul, S'ye ait her eleman »ciftinin birlikte T'nin elemanlar³ndan yaln³z ve ancakbirinde yer almas³d³r. C kÄumesini renkler kÄumesi olarak kabul etti¸gimizde, kÄos.erenklendirmesi, S kÄumesinden C kÄumesine tan³mlanm³s. bir fonksiyondur, bu fonksiy-onu f olarak isimlendirirsek, renklendirmenin Äuzerindeki s. art, her (x,y,z) Äuc.lÄusÄu ic.ini»cin, f(x), f(y), f(z)'den olus.an kÄumenin boyutunun 2'den buyuk-es.it olmas³d³r. BirSteiner Äu»clÄu sistemi, hi»c bir Äuc.lÄu tek renkle boyanmayacak s. ekilde k renkle ren-klendirilip daha az renkle renklendirilemedi¸ginde sisteme, k-kromatik diyoruz. Butez, bu konuda daha Äonce yap³lm³s. »cal³s.malar ÄustÄune bir inceleme niteli·gindedir.1

A Steiner triple system (STS) is an ordered pair (S,T) where S denotes a setof points and T denotes a set of three element subsets of S called triples with theproperty that any pair of elements of S is a subset of exactly one triple. Let C be aset of colors. A (weak) k-coloring of a STS(v) is a map f, from S to C such that thesize of the set consisting of the elements f(x), f(y), f(z)should be greater than or equalto two, for every triple including x, y, x in T. A Steiner triple system is k-chromatic ifit admits a k-coloring but not a (k-1)-coloring. In this case we say that the STS haschromatic number k and we write Chr(S) = k. This thesis is a survey on colorings ofSteiner triple systems.1