Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
Every matroid is a submatroid of a uniformly dense matroid - MaRDI portal

Every matroid is a submatroid of a uniformly dense matroid (Q1902898)

From MaRDI portal





scientific article; zbMATH DE number 822837
Language Label Description Also known as
English
Every matroid is a submatroid of a uniformly dense matroid
scientific article; zbMATH DE number 822837

    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