Every matroid is a submatroid of a uniformly dense matroid (Q1902898)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Every matroid is a submatroid of a uniformly dense matroid |
scientific article |
Statements
Every matroid is a submatroid of a uniformly dense matroid (English)
0 references
13 January 1997
0 references
For a graph \(G\) with at least one edge, define \(d(G)= {|E(G)|\over |V(G)|}\) and \(m(G)= \max\{d(H)\mid H\subseteq G\}\). Györi proved that every connected graph is a subgraph of a graph \(G'\) with \(m(G')= d(G)= m(G)\). A similar extremal problem was investigated by Payan. The authors in this paper show that both problems (and theorems) above are related by matroid elongations. They extend these results to their versions of binary and regular matroids.
0 references
connected graph
0 references
extremal problem
0 references
matroid
0 references
0 references