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
    0 references
    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

    Identifiers