Unweighted One-Sided Code Sparsifiers and Thin Subgraphs

For a linear code $\mathcal{C}\subseteq {\mathbb{F}}_2^n$ and $\alpha \in [0,1]$, call a set $S\subseteq [n]$ an (unweighted) one-sided $\alpha$-sparsifier of $\mathcal{C}$ if for all $c\in \mathcal{C}$, $\mathrm{w}\mathrm{t}(c_S)\ge \alpha \cdot \mathrm{w}\mathrm{t}(c)$, where $c_S$ is the projection of $c$ onto the coordinates in $S$ and $\mathrm{w}\mathrm{t}(c)$ is the Hamming weight of $c$. \ We show that every $k$-dimensional linear code $\mathcal{C}\subseteq {\mathbb{F}}_2^n$ has at least $2^{n-k}$ many unweighted one-sided $1\mathrm{/}2$-sparsifiers and hence one of size at most $n\mathrm{/}2+O(\sqrt{nk})$. As an application, letting $\mathcal{C}\subseteq {\mathbb{F}}_2^E$ denote the cut-space of a graph $G=(V,E)$, we show a lower bound of $2^{\mid E\mid -(\mid V\mid -1)}$ on the number of $1\mathrm{/}2$-thin subgraphs of $G$ and the existence of a $1\mathrm{/}2$-thin subgraph with at least $\mid E\mid \mathrm{/}2-O(\sqrt{\mid E\mid \cdot \mid V\mid })$ edges. In contrast to previous results on thin subgraphs, our proofs are purely “combinatorial”.