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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

5 Citaten (Scopus)

114 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	1145-1153
Aantal pagina's	9
Tijdschrift	SIAM Journal on Discrete Mathematics
Volume	32
Nummer van het tijdschrift	2
DOI's	https://doi.org/10.1137/17M1160094
Status	Gepubliceerd - 1 jan. 2018

Toegang tot document

10.1137/17M1160094

publisher versionDefinitieve gepubliceerde versie, 306 KB

Andere bestanden en links

Link to publication in Scopus

Citeer dit

@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 - https://www.scopus.com/pages/publications/85049570433

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

Samenvatting

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit