Matroids having the same connectivity function (Q1332425)

From MaRDI portal





scientific article; zbMATH DE number 626347
Language Label Description Also known as
default for all languages
No label defined
    English
    Matroids having the same connectivity function
    scientific article; zbMATH DE number 626347

      Statements

      Matroids having the same connectivity function (English)
      0 references
      0 references
      14 February 1995
      0 references
      Let \(M_ i\) be matroids on the same set \(E\) having rank functions \(r_ i\), and let \(\xi(M_ i,X)= r_ i(X)+ r_ i(E\backslash X)- r_ i(E)+ 1\) for all \(X\subseteq E\) and \(1\leq i\leq 4\). Then \((M_ 1,M_ 2)\) is said to be connected provided that \(\xi(M_ 1,X)+ \xi(M_ 2,X)> 2\) for every \(\varnothing\neq X\subset E\). And moreover, \((M_ 1,M_ 2)\sim (M_ 3,M_ 4)\) provided that \(r_ 1(X)+ r_ 2(X)= r_ 3(X)+ r_ 4(X)\) for every \(X\subseteq E\). Using these concepts the author formulates and proves the following main theorem: If \((M_ 1,M_ 2)\sim (M_ 3,M_ 4)\) and \((M_ 1,M_ 2)\) is connected, then \(B\) is a base of \(M_ 1\) or \(M_ 2\) if and only if \(B\) is a base of \(M_ 3\) or \(M_ 4\). Several interesting consequences are discussed including the following one: Let \(M\) be a connected matroid on \(E\) with dual matroid \(M^*\) such that \(r(M)\neq r(M^*)\). If \(N\) is a matroid on \(E\) having the same connectivity function as \(M\), then \(M= N\) or \(M= N^*\). This is a generalization of an earlier result proved by \textit{P. D. Seymour} [J. Comb. Theory, Ser. B 28, 305-359 (1980; Zbl 0443.05027)] for the case of binary matroids.
      0 references
      0 references
      matroids
      0 references
      rank functions
      0 references
      connectivity function
      0 references

      Identifiers