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


Some heterochromatic theorems for matroids
Authors:Criel Merino  Juan José Montellano-Ballesteros
Institution:Instituto de Matemáticas, Universidad Nacional Autónoma de México, México City, México
Abstract:The anti-Ramsey number of Erdös, Simonovits and Sós from 1973 has become a classic invariant in Graph Theory. To extend this invariant to Matroid Theory, we use the heterochromatic number hc(H) of a non-empty hypergraph H. The heterochromatic number of H is the smallest integer k such that for every colouring of the vertices of H with exactly k colours, there is a totally multicoloured hyperedge of H.Given a matroid M, there are several hypergraphs over the ground set of M we can consider, for example, C(M), whose hyperedges are the circuits of M, or B(M), whose hyperedges are the bases of M. We determine hc(C(M)) for general matroids and characterise the matroids with the property that hc(B(M)) equals the rank of the matroid. We also consider the case when the hyperedges are the Hamiltonian circuits of the matroid. Finally, we extend the known result about the anti-Ramsey number of 3-cycles in complete graphs to the heterochromatic number of 3-circuits in projective geometries over finite fields, and we propose a problem very similar to the famous problem on the anti-Ramsey number of the p-cycles.
Keywords:Anti-Ramsey number  Hypergraph  Matroid
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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