首页 | 本学科首页   官方微博 | 高级检索  
     


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 defilignedby 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 isin E(G), the color ofij andkl is the same if and only ifF i cap F j = F k cap 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号