Article ID Journal Published Year Pages File Type
4650078 Discrete Mathematics 2009 6 Pages PDF
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
, ,