Examples and Important Classes of Matroids

Matroid の例として, 代表的なのは次のものである。

• graph の cycle から定義される matroid
• ベクトルの集合の1次従属性あるいや1次独立性から定義される matroid

最初の例の方法で graph から作られる matroid を graphic matroid という。 どのような matroid が graphic か, という問題が考えられるが, これについては Seymour の論文 [Sey81] がある。 これを元に Geelen ら [GGW18] により quasi-graphic matroid という matroid の class が定義されている。

• graphic matroid
• quasi-graphic matroid

2番目の例で, unoriented matroid だと \(\R \) 以外の体上のベクトル空間を考えることができる。体 \(k\) 上のベクトル空間のベクトルの有限集合の1次独立性で定義される matroid と同値になる matroid は, \(k\) 上 representable であるという。特に \(\F _2\) 上 representable な matroid を binary matroid という。

• 体 \(k\) 上 representable な matroid
• binary matroid

よって, 体を変えたときの representability について考えることもできる。 例えば, Pendavingh と van Zwam の [PZ10b; PZ10a] など。 それによると, 有名なのは Tutte の [Tut65] の結果のようである。

線形独立性の他にも代数的独立性からも matroid が得られる。体の拡大 \(K/k\) と \(K\) の有限集合 \(E\) が与えられたとき, \(E\) の 部分集合 \(I\) で \(k\) 上代数的独立であることを independent とすると matroid が得られる。 このような matroid を algebraic matroid と呼ぶようである。 あまり良い名前とは思えないが。そして algebraic matroid として実現できるとき, algebraically representable と呼ぶ。

• algebraic matroid
• algebraic representability

与えられた matroid が algebraic かどうかを判定する algorithm が存在しないことが, Boege と Yashfe [BY] により示されている。

References

[BY]

Tobias Boege and Geva Yashfe. Recognition of algebraic matroids is undecidable. arXiv: 2607.14907.

[GGW18]

Jim Geelen, Bert Gerards, and Geoff Whittle. “Quasi-graphic matroids”. In: J. Graph Theory 87.2 (2018), pp. 253–264. arXiv: 1512.03005. url: https://doi.org/10.1002/jgt.22177.

[PZ10a]

R. A. Pendavingh and S. H. M. van Zwam. “Confinement of matroid representations to subsets of partial fields”. In: J. Combin. Theory Ser. B 100.6 (2010), pp. 510–545. arXiv: 0806.4487. url: https://doi.org/10.1016/j.jctb.2010.04.002.

[PZ10b]

R. A. Pendavingh and S. H. M. van Zwam. “Lifts of matroid representations over partial fields”. In: J. Combin. Theory Ser. B 100.1 (2010), pp. 36–67. arXiv: 0804.3263. url: https://doi.org/10.1016/j.jctb.2009.03.006.

[Sey81]

P. D. Seymour. “Recognizing graphic matroids”. In: Combinatorica 1.1 (1981), pp. 75–78. url: http://dx.doi.org/10.1007/BF02579179.

[Tut65]

W. T. Tutte. “Lectures on matroids”. In: J. Res. Nat. Bur. Standards Sect. B 69B (1965), pp. 1–47.