Spectral Conditions for the Ingleton Inequality.

Abstract: 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 (cf. Alon, Newman, Shen, Tardos, Vereshchagin, 2007).

Computer scienceMathematics

Audience: researchers in the discipline

Seminar on Algorithmic Aspects of Information Theory

Series comments: This online seminar is a follow up of the Dagstuhl Seminar 22301, www.dagstuhl.de/en/program/calendar/semhp/?semnr=22301.