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


Bounding the size of square-free subgraphs of the hypercube
Authors:Andrew Thomason  Peter Wagner
Institution:DPMMS, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WB, UK
Abstract:We investigate the maximum size of a subset of the edges of the n-cube that does not contain a square, or 4-cycle. The size of such a subset is trivially at most 3/4 of the total number of edges, but the proportion was conjectured by Erd?s to be asymptotically 1/2. Following a computer investigation of the 4-cube and the 5-cube, we improve the known upper bound from 0.62284… to 0.62256… in the limit.
Keywords:Hypercube  _method=retrieve&  _eid=1-s2  0-S0012365X08001234&  _mathId=si36  gif&  _pii=S0012365X08001234&  _issn=0012365X&  _acct=C000069490&  _version=1&  _userid=6211566&  md5=c83725a51894aa2cef002e71d3633d26')" style="cursor:pointer  n-cube" target="_blank">" alt="Click to view the MathML source" title="Click to view the MathML source">n-cube  4-cycle
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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