NDLI: The Minimal Set of Ingleton Inequalities

Content Provider	IEEE Xplore Digital Library
Author	Guille, L. Chan, T. Grant, A.
Copyright Year	1963
Abstract	The Ingleton inequalities are the inequality constraints known to be required of representable matroids. For a matroid of n elements, there are 16n Ingleton inequalities. In this paper, we show that many of these inequalities are redundant. We explicitly determine the unique minimal set of Ingleton inequalities, which number on the order of 6n/4- O(5n). In information theory, these inequalities are required of the entropy functions of certain random variables constructed from linear subspaces. As a result, these inequalities appear as constraints in linear programming outer bounds for the capacity region of multisource network coding where the codes are required to be linear. Ingleton inequalities have also played an instrumental role in demonstrating the insufficiency of linear codes for multisource network coding. The reduction that we obtain for Ingleton inequalities is sufficiently large to meaningfully reduce the complexity of these linear programming bounds.
Sponsorship	IEEE Information Theory Society
Starting Page	1849
Ending Page	1864
Page Count	16
File Size	338686
File Format	PDF
ISSN	00189448
Volume Number	57
Issue Number	4
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-04-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Random variables Vectors Entropy Network coding Context Cramer-Rao bounds Shannon inequalities Entropy functions Ingleton inequalities
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Truncation Technique for Characterizing Linear Polymatroids

A Recursive Construction of the Set of Binary Entropy Vectors and Related Algorithmic Inner Bounds for the Entropy Region

Secret Sharing and Non-Shannon Information Inequalities

Balanced information inequalities

Book Inequalities

Six New Non-Shannon Information Inequalities

Conditional Information Inequalities for Entropic and Almost Entropic Points

Finite p-Groups, Entropy Vectors, and the Ingleton Inequality for Nilpotent Groups

Secret Sharing, Rank Inequalities, and Information Inequalities

The Minimal Set of Ingleton Inequalities

Similar Documents

Truncation Technique for Characterizing Linear Polymatroids

A Recursive Construction of the Set of Binary Entropy Vectors and Related Algorithmic Inner Bounds for the Entropy Region

Secret Sharing and Non-Shannon Information Inequalities

Balanced information inequalities

Book Inequalities

Six New Non-Shannon Information Inequalities

Conditional Information Inequalities for Entropic and Almost Entropic Points

Finite p-Groups, Entropy Vectors, and the Ingleton Inequality for Nilpotent Groups

Secret Sharing, Rank Inequalities, and Information Inequalities

The Minimal Set of Ingleton Inequalities