Doubly exponentially many ingleton matroids

Peter Nelson; Jorn van der Pol

doi:10.1137/17M1160094

Doubly exponentially many ingleton matroids

Peter Nelson, Jorn van der Pol

Mathematics and Computer Science

Research output: Contribution to journal › Article › Academic › peer-review

5 Citations (Scopus)

89 Downloads (Pure)

Abstract

A matroid is Ingleton if all quadruples of subsets of its ground set satisfy Ingleton’s inequality. In particular, representable matroids are Ingleton. We show that the number of Ingleton matroids on ground set [n] is doubly exponential in n; it follows that almost all Ingleton matroids are nonrepresentable.

Original language	English
Pages (from-to)	1145-1153
Number of pages	9
Journal	SIAM Journal on Discrete Mathematics
Volume	32
Issue number	2
DOIs	https://doi.org/10.1137/17M1160094
Publication status	Published - 1 Jan 2018

Keywords

Enumeration
Matroid
Representable

Access to Document

10.1137/17M1160094

publisher versionFinal published version, 306 KB

Cite this

@article{ee5640ea98d3423fbfd6826a40c9f01a,

title = "Doubly exponentially many ingleton matroids",

abstract = "A matroid is Ingleton if all quadruples of subsets of its ground set satisfy Ingleton{\textquoteright}s inequality. In particular, representable matroids are Ingleton. We show that the number of Ingleton matroids on ground set [n] is doubly exponential in n; it follows that almost all Ingleton matroids are nonrepresentable.",

keywords = "Enumeration, Matroid, Representable",

author = "Peter Nelson and {van der Pol}, Jorn",

year = "2018",

month = jan,

day = "1",

doi = "10.1137/17M1160094",

language = "English",

volume = "32",

pages = "1145--1153",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

number = "2",

}

TY - JOUR

T1 - Doubly exponentially many ingleton matroids

AU - Nelson, Peter

AU - van der Pol, Jorn

PY - 2018/1/1

Y1 - 2018/1/1

N2 - A matroid is Ingleton if all quadruples of subsets of its ground set satisfy Ingleton’s inequality. In particular, representable matroids are Ingleton. We show that the number of Ingleton matroids on ground set [n] is doubly exponential in n; it follows that almost all Ingleton matroids are nonrepresentable.

AB - A matroid is Ingleton if all quadruples of subsets of its ground set satisfy Ingleton’s inequality. In particular, representable matroids are Ingleton. We show that the number of Ingleton matroids on ground set [n] is doubly exponential in n; it follows that almost all Ingleton matroids are nonrepresentable.

KW - Enumeration

KW - Matroid

KW - Representable

UR - http://www.scopus.com/inward/record.url?scp=85049570433&partnerID=8YFLogxK

U2 - 10.1137/17M1160094

DO - 10.1137/17M1160094

M3 - Article

AN - SCOPUS:85049570433

SN - 0895-4801

VL - 32

SP - 1145

EP - 1153

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -

Doubly exponentially many ingleton matroids

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this