Infinite Matroids

Matroid は通常有限集合を ground set として定義されるが, その無限集合への拡張も古くから考えられている。

Bruhn と Wollan の [BW12] によると, 無限集合上の matroid として最初に考えられたのは Higgs [Hig69a; Hig69b; Hig69c] による B-matroid のようである。

その後, Oxley [Oxl78; Oxl92] が independence space の名前で現在 finitary matroid と呼ばれるものを調べているが, その Oxley の論文では Welsh の本 [Wel76] の 385 ページと 387 ページ, そして Mirsky の本 [Mir71] の 90 ページが参照されている。 また, Fornasiero と Kaplan の [FK24] によると, 同じものが pregeometry という名前で model theory に登場しているようである。彼等は Tent と Ziegler の monograph [TZ12] の Appendix C.1 を参照している。

• finitary matroid

有限集合上の matroid は様々な公理で定義できるが, infinite matroid の公理としては Bruhn らの [Bru+13; BD11] に述べられているものがある。そこでは次の公理が述べられている。

• independence axioms
• base axioms
• closure axioms
• circuit axioms
• rank axioms

Rank axioms は, Pendavingh [Pen] により導入されたが, その後上記の [Bru+13] に統合されている。

Aigner-Horev, Carmesin, Fröhlich の[ACF] によると, 一般には infinite matroid の union は matroid にはならない。彼等は, finitary matroid の union はまた finitary matroid になることを示している。また [ACF18] では, finitary matroid より大きな nearly finitary matroid という class を定義している。

• nearly finitery matroid

Oriented matroid の無限版は, あまり調べられていないように思うが, 最近 Delucchi と Knauer [DK21] が finiteary affine oriented matroid を導入し調べている。

• finitary affine oriented matroid

References

[ACF]

Elad Aigner-Horev, Johannes Carmesin, and Jan-Oliver Fröhlich. Infinite matroid union. arXiv: 1111.0602.

[ACF18]

Elad Aigner-Horev, Johannes Carmesin, and Jan-Oliver Fröhlich. “On the intersection of infinite matroids”. In: Discrete Math. 341.6 (2018), pp. 1582–1596. arXiv: 1111.0606. url: https://doi.org/10.1016/j.disc.2018.02.018.

[BD11]

Henning Bruhn and Reinhard Diestel. “Infinite matroids in graphs”. In: Discrete Math. 311.15 (2011), pp. 1461–1471. arXiv: 1011.4749. url: http://dx.doi.org/10.1016/j.disc.2010.12.015.

[Bru+13]

Henning Bruhn, Reinhard Diestel, Matthias Kriesell, Rudi Pendavingh, and Paul Wollan. “Axioms for infinite matroids”. In: Adv. Math. 239 (2013), pp. 18–46. arXiv: 1003.3919. url: http://dx.doi.org/10.1016/j.aim.2013.01.011.

[BW12]

Henning Bruhn and Paul Wollan. “Finite connectivity in infinite matroids”. In: European J. Combin. 33.8 (2012), pp. 1900–1912. arXiv: 1101.5621. url: http://dx.doi.org/10.1016/j.ejc.2012.05.006.

[DK21]

Emanuele Delucchi and Kolja Knauer. “Finitary affine oriented matroids”. In: Sém. Lothar. Combin. 85B (2021), Art. 48, 12. arXiv: 2011.13348.

[FK24]

Antongiulio Fornasiero and Elliot Kaplan. “Hilbert polynomials for finitary matroids”. In: Pacific J. Math. 333.2 (2024), pp. 273–308. arXiv: 2208.01560. url: https://doi.org/10.2140/pjm.2024.333.273.

[Hig69a]

D. A. Higgs. “Infinite graphs and matroids”. In: Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968). Academic Press, New York, 1969, pp. 245–253.

[Hig69b]

D. A. Higgs. “Matroids and duality”. In: Colloq. Math. 20 (1969), pp. 215–220. url: https://doi.org/10.4064/cm-20-2-215-220.

[Hig69c]

Denis Higgs. “Equicardinality of bases in \(B\)-matroids”. In: Canad. Math. Bull. 12 (1969), pp. 861–862. url: https://doi.org/10.4153/CMB-1969-112-6.

[Mir71]

L. Mirsky. Transversal theory. An account of some aspects of combinatorial mathematics. Mathematics in Science and Engineering, Vol. 75. Academic Press, New York-London, 1971, pp. ix+255.

[Oxl78]

James G. Oxley. “Infinite matroids”. In: Proc. London Math. Soc. (3) 37.2 (1978), pp. 259–272. url: https://doi.org/10.1112/plms/s3-37.2.259.

[Oxl92]

James Oxley. “Infinite matroids”. In: Matroid applications. Vol. 40. Encyclopedia Math. Appl. Cambridge Univ. Press, Cambridge, 1992, pp. 73–90. url: https://doi.org/10.1017/CBO9780511662041.004.

[Pen]

R. A. Pendavingh. Relative rank axioms for infinite matroids. arXiv: 1004.0154.

[TZ12]

Katrin Tent and Martin Ziegler. A course in model theory. Vol. 40. Lecture Notes in Logic. Association for Symbolic Logic, La Jolla, CA; Cambridge University Press, Cambridge, 2012, pp. x+248. isbn: 978-0-521-76324-0. url: https://doi.org/10.1017/CBO9781139015417.

[Wel76]

D. J. A. Welsh. Matroid theory. L. M. S. Monographs, No. 8. London: Academic Press [Harcourt Brace Jovanovich Publishers], 1976, pp. xi+433.