Publication at Faculty of Mathematics and Physics |
2012
Abstract
We prove a conjecture of Castaneda and Gotchev that for every set F of at most n(n-1)/2 vertices, the hypercube of dimension n contains a cycle of length at least 2^n-2|F| that avoids F. We also prove that for every set F of at most (n^2+n-4)/4 vertices, the hypercube of dimension n contains a path of length at least 2n-2|F|-2 between any two vertices such that each of them has at most 3 neighbors in F.
We introduce a new technique of potentials which could be of independent interest.