Ingleton's inequality

In mathematics, Ingleton's inequality is an inequality that is satisfied by the rank function of any representable matroid. In this sense it is a necessary condition for representability of a matroid over a finite field. Let M be a matroid and let ρ be its rank function, Ingleton's inequality states that for any subsets X1, X2, X3 and X4 in the support of M, the inequality

ρ(X1)+ρ(X2)+ρ(X1∪X2∪X3)+ρ(X1∪X2∪X4)+ρ(X3∪X4) ≤ ρ(X1∪X2)+ρ(X1∪X3)+ρ(X1∪X4)+ρ(X2∪X3)+ρ(X2∪X4) is satisfied.

Aubrey William Ingleton, an English mathematician, wrote an important paper in 1969[1] in which he surveyed the representability problem in matroids. Although the article is mainly expository, in this paper Ingleton stated and proved Ingleton's inequality, which has found interesting applications in information theory, matroid theory, and network coding.[2]

  1. ^ Ingleton, A.W. (1971). "Representation of matroids". In Welsh, D.J.A. (ed.). Combinatorial mathematics and its applications. Proceedings, Oxford, 1969. Academic Press. pp. 149–167. ISBN 0-12-743350-3. Zbl 0222.05025.
  2. ^ Ahlswede, Rudolf; N. Cai; Shuo-Yen Robert Li; Raymond Wai-Ho Yeung (2000). "Network Information Flow". IEEE Transactions on Information Theory. 46 (4): 1204–1216. doi:10.1109/18.850663.