Spectral Conditions for the Ingleton Inequality

The Ingleton inequality is a classical linear information inequality that holds for representable matroids but fails to be universally valid for entropic vectors.

Understanding the extent to which this inequality can be violated has been a longstanding problem in information theory.

In this paper, we show that for a broad class of jointly distributed random variables $(X,Y)$ the Ingleton inequality holds up to a small additive error, even even though the mutual information between $X$ and $Y$ is far from being extractable.

Contrary to common intuition, strongly non-extractable mutual information does not lead to large violations of the Ingleton inequality in this setting.

More precisely, we consider pairs $(X,Y)$ that are uniformly distributed on their joint support and whose associated biregular bipartite graph is an expander.

For all auxiliary random variables $A$ and $B$ jointly distributed with $(X,Y)$, we establish a lower bound on the Ingleton quantity $I(X;Y | A) + I(X;Y | B) + I(A;B) - I(X;Y)$ in terms of the spectral parameters of the underlying graph.

Our proof combines the expander mixing lemma with a partitioning technique for finite sets.