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


Panchromatic 3-colorings of random hypergraphs
Abstract:The paper deals with panchromatic 3-colorings of random hypergraphs. A vertex 3-coloring is said to be panchromatic for a hypergraph if every color can be found on every edge. Let H(n,k,p) denote the binomial model of a random k-uniform hypergraph on n vertices. For given fixed c>0, k3 and p=cnnk, we prove that if c<ln3332kln32O32kthen H(n,k,p) admits a panchromatic 3-coloring with probability tending to 1 as n, but if k is large enough and c>ln3332kln32+O34kthen H(n,k,p) does not admit a panchromatic 3-coloring with probability tending to 1 as n.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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