Fundamental cycles in grid graphs

Abstract

We show that the average length of a fundamental cycle with respect to any fixed spanning tree of the $n\times n$ square grid is at least $\Omega (\log n)$; the bound is asymptotically tight. This result answers in the affirmative a question posed by McCarty in relation to sparse representations of binary matroids.

An anonymous reviewer brought the paper "N. Alon et al.: A graph-theoretic game and its application to the k-server problem, SIAM J. Comput. 24 (1995), 78-100" to our attention. Since our main result is contained in Section 6 there, we will not pursue publication of this paper. We keep it publicly available on arXiv in case our proof argument may be of use in another setting