Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650078 | Discrete Mathematics | 2009 | 6 Pages |
Abstract
We investigate the maximum size of a subset of the edges of the nn-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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Andrew Thomason, Peter Wagner,