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


Minors of a random binary matroid
Authors:Colin Cooper  Alan Frieze  Wesley Pegden
Abstract:Let A be an n × m matrix over GF 2 where each column consists of k ones, and let M be an arbitrary fixed binary matroid. The matroid growth rate theorem implies that there is a constant CM such that mCMn2 implies that the binary matroid induced by A contains M as a minor. We prove that if the columns of A = A n,m,k are chosen randomly, then there are constants kM,LM such that kkM and mLMn implies that A contains M as a minor with high probability .
Keywords:binary  matroids  minors  random
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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