Unweighted One-Sided Code Sparsifiers and Thin Subgraphs

Abstract

For a linear code $\mathcal{C}\subseteq {\mathbb{F}}_2^n$ and $\hat{I}\pm \in [0,1]$, call a set $S\subseteq [n]$ an (unweighted) one-sided $\hat{I}\pm$-sparsifier of $\mathcal{C}$ if for all $c\in \mathcal{C}$, $\mathrm{wt}(c_S)\ge \hat{I}\pm \cdot \mathrm{wt}(c)$, where $c_S$ is the projection of $c$ onto the coordinates in $S$ and $\mathrm{wt}(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/2$-sparsifiers and hence one of size at most $n/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^{|E|-(|V|-1)}$ on the number of $1/2$-thin subgraphs of $G$ and the existence of a $1/2$-thin subgraph with at least $|E|/2-O(\sqrt{|E|\cdot |V|})$ edges. In contrast to previous results on thin subgraphs, our proofs are purely "combinatorial".