Transitive Edge Coloring of Graphsand Dimension of Lattices |
| |
Authors: | András?Gyárfás mailto:gyarfas@sztaki.hu" title=" gyarfas@sztaki.hu" itemprop=" email" data-track=" click" data-track-action=" Email author" data-track-label=" " >Email author |
| |
Affiliation: | (1) Computer and Automation Research Institute of the Hungarian Academy of Sciences, Budapest, 63, Hungary-1518 |
| |
Abstract: | ![]() We explore properties of edge colorings of graphs de nedby set intersections. An edge coloring of a graphG with vertex setV ={1,2, . . . ,n} is calledtransitive if one canassociate sets F 1,F 2, . ..,F nto vertices of G so that forany two edges ij,kl E(G), the color ofij andkl is the same if and only ifF i F j = F k F l . The termtransitive refers to anatural partial order on the color set of thesecolorings.We prove a canonical Ramsey type result for transitivecolorings of complete graphs which is equivalent to a strongerform of a conjecture of A. Sali on hypergraphs. This—through thereduction of Sali—shows that the dimension ofn-element lattices iso(n) as conjectured by Füredi andKahn.The proof relies on concepts and results which seem tohave independent interest. One of them is a generalization ofthe induced matching lemma of Ruzsa and Szemerédi for transitivecolorings. * Research supported in part by OTKA GrantT029074. |
| |
Keywords: | 05C15 |
本文献已被 SpringerLink 等数据库收录! |
|