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


A note on panchromatic colorings
Authors:Danila Cherkashin
Institution:Saint Petersburg State University, Faculty of Mathematics and Mechanics, Russian Federation;Moscow Institute of Physics and Technology, Laboratory of Advanced Combinatorics and Network Applications, Russian Federation;St. Petersburg Department of V. A. Steklov Institute of Mathematics of the Russian Academy of Sciences, Russian Federation
Abstract:This paper studies the quantity p(n,r), that is the minimal number of edges of an n-uniform hypergraph without panchromatic coloring (it means that every edge meets every color) in r colors. If rcnlnn then all bounds have a type A1(n,lnn,r)(rr?1)np(n,r)A2(n,r,lnr)(rr?1)n, where A1, A2 are some algebraic fractions. The main result is a new lower bound on p(n,r) when r is at least cn; we improve an upper bound on p(n,r) if n=o(r32).Also we show that p(n,r) has upper and lower bounds depending only on nr when the ratio nr is small, which cannot be reached by the previous probabilistic machinery.Finally we construct an explicit example of a hypergraph without panchromatic coloring and with (rr?1+o(1))n edges for r=o(nlnn).
Keywords:Hypergraph colorings  Panchromatic colorings
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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