Introduction to the Theory of Matroids

نظریه ماتروئید منشأ خود را در مقاله ای از H. Whitney با عنوان "در مورد ویژگی های انتزاعی وابستگی خطی" [35]، که در سال 1935 ظاهر شد. ویژگی‌های مفاهیم وابستگی و استقلال خطی در فضاهای برداری، و استفاده از آنها برای تعریف بدیهی یک شی جبری جدید، یعنی ماتروئید. علاوه بر این، ویتنی نشان داد که این بدیهیات نیز انتزاعی از مفاهیم خاص گراف-نظری هستند. هنگامی که مفاهیم اساسی ساختار یک ماتروئید را در نظر می گیریم، این امر بسیار مشهود است: برخی منشأ جبری خطی آنها را منعکس می کنند، در حالی که برخی دیگر منشا نظری گراف آنها را منعکس می کنند. ویتنی همچنین تعدادی از نمونه های مهم ماتروئید را مطالعه کرد. پیشرفت عمده بعدی در دهه چهل با تعمیم ماتروئیدی قضیه معروف P. هال توسط R. Rado به وجود آمد. این انگیزه های جدیدی را برای نظریه عرضی فراهم کرد، که در آن ماتروئیدها امروزه نقش اساسی را تحت نام "ساختارهای استقلال" ایفا می کنند. رساله نظریه عرضی ال. میرسکی [26J. تقریباً در همان زمان R.P. Dilworth ارتباط بین ماتروئیدها و نظریه شبکه را برقرار کرد. بنابراین ماتروئیدها به بخشی ضروری از ریاضیات ترکیبی تبدیل شدند. حدود ده سال بعد W.T. Tutte [30] مبانی ماتروئیدها را به تفصیل از دیدگاه نظری گراف توسعه داد و ماتروئیدهای گرافیکی و همچنین طبقه بزرگتری از آن دسته از ماتروئیدها را که در هر زمینه ای قابل نمایش هستند مشخص کرد.

Matroid theory has its origin in a paper by H. Whitney entitled "On the abstract properties of linear dependence" [35], which appeared in 1935. The main objective of the paper was to establish the essential (abstract) properties of the concepts of linear dependence and independence in vector spaces, and to use these for the axiomatic definition of a new algebraic object, namely the matroid. Furthermore, Whitney showed that these axioms are also abstractions of certain graph-theoretic concepts. This is very much in evidence when one considers the basic concepts making up the structure of a matroid: some reflect their linear­ algebraic origin, while others reflect their graph-theoretic origin. Whitney also studied a number of important examples of matroids. The next major development was brought about in the forties by R. Rado's matroid generalisation of P. Hall's famous "marriage" theorem. This provided new impulses for transversal theory, in which matroids today play an essential role under the name of "independence structures", cf. the treatise on transversal theory by L. Mirsky [26J. At roughly the same time R.P. Dilworth estab­ lished the connection between matroids and lattice theory. Thus matroids became an essential part of combinatorial mathematics. About ten years later W.T. Tutte [30] developed the funda­ mentals of matroids in detail from a graph-theoretic point of view, and characterised graphic matroids as well as the larger class of those matroids that are representable over any field.