On combinatorial structures in linear codes

Understand

In this work we show that given a connectivity graph $G$ of a $[[n,k,d]]$ quantum code, there exists $\{K_i\}_i, K_i \subset G$, such that $\sum_i |K_i|\in \Omega(k), \ |K_i| \in \Omega(d)$, and the $K_i$'s are $\tilde{\Omega}( \sqrt{{k}/{n}})$-expander.

• If the codes are classical we show instead that the $K_i$'s are $\tilde{\Omega}\left({{k}/{n}}\right)$-expander.
• We also show converses to these bounds.
• In particular, we show that the BPT bound for classical codes is tight in all Euclidean dimensions.