در مورد حدس روتا

نوع مقاله: مقاله علمی-ترویجی

نویسندگان

دانشگاه یزد

چکیده

مترویدها‎ در تلاش برای فراهم آوردن یک رفتار مجرد یکسان از وابستگی در جبر خطی و نظریه گراف معرفی شده‌اند. نام متروید ساختاری مربوط به یک ماتریس را القا می‌کند. تعریف ویتنی‎‎ تنوعی شگفت‌انگیز از ساختارهای ترکیبیاتی را در برداشت. از این گذشته مترویدها به طور طبیعی در بهینه‌سازی ترکیبیاتی پدیدار می‌شوند، زیرا آنها دقیقا‏ً همان ساختارهای ترکیبیاتی هستند که الگوریتم حریصانه برای آن به نتیجه می‌رسد. یکی از حدس‌های مهم در نظریه متروید، حدس روتا می‌باشد که توسط جیان کارلو روتا‎، ریاضیدان و فیلسوف مشهور در سال ‎۱۹۷۰‎ مطرح شد. ما در این مقاله ضمن بیان مقدمات لازم و معرفی حدس روتا، به بررسی کلیات اثباتی که توسط جیوف ویتل از دانشگاه ویکتوریا با همکاری جیم گیلن از کانادا و برت جراردز از هلند برای آن اخیراً ارائه کرده‌اند، می‌پردازیم.

کلیدواژه‌ها

موضوعات


[1] R. E. Bixby, On Reid’s characterization of ternary matroids, J. Combin. Theory Ser. B, 26 (1979) 174–204.

[2] R. Diestel, Graph theory, Translated from the 1996 German original, Graduate Texts in Mathematics, 173, Springer-Verlag, New York, 1997.

[3] J. Geelen, B. Gerards, T. Huynh and S. van Zwam, Generating k -connected matroids (working title), in preparation.

[4] J. Geelen, B. Gerards and G. Whittle, Excluding a planar graph from GF (q)-representable matroids, J. Combin. Theory Ser. B, 97 (2007) 971–998.

[5] J. F. Geelen, A. M. H. Gerards and A. Kapoor, The excluded minors for GF (۴)-representable matroids, J. Combin. Theory Ser. B, 79 (2000) 247–299.

[6] J. Geelen, B. Gerards and G. Whittle,On inequivalent representations of matroids over non-prime fields, J. Combin. Theory Ser. B, 100 (2010) 740–743.

[7] J. Geelen, B. Gerards and G. Whittle, Solving Rota’s Conjecture, Notices Amer. Math. Soc., 61 (2014) 736–743.

[8] J. Geelen and S. van Zwam, Fixed elements and matroid tangles (working title), in preparation.

[9] J. Geelen and G. Whittle, Inequivalent representations of matroids over prime fields, Adv. in Appl. Math., 51 (2013) 1–175.

[10] J. Kahn, On the uniqueness of matroid representations over GF (4) , Bull. London Math. Soc., 20 (1988) 5–10.

[11] K. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math., 15 (1930) 271–283.

[12] T. Lazarson, The representation problem for independence functions, J. London Math. Soc., 33 (1958) 21–25.

[13] D. Mayhew, M. Newman and G. Whittle, On excluded minors for real-representable matroids, J. Combin. Theory Ser. B, 99 (2009) 685–689.

[14] D. Mayhew, G. Whittle and M. Newman, Is the missing axiom of matroid theory lost forever?, Q. J. Math., 65 (2014) 1397–1415.

[15] J. Oxley, D. Vertigan and G. Whittle, On inequivalent representations of matroids over finite fields, J. Combin. Theory Ser. B, 67 (1996) 325–343.

[16] N. Robertson and P. D. Seymour, Graph minors. IV. Tree-width and well-quasi-ordering, J. Combin. Theory Ser. B, 48 (1990) 227–254.

[17] N. Robertson and P. D. Seymour, Graph Minors. VIII. A Kuratowski theorem for general surfaces, J. Combin. Theory Ser. B, 48 (1990) 255–288.

[18] N. Robertson and P. D. Seymour, Graph minors. XVI. Excluding a nonplanar graph, J. Combin. Theory Ser. B, 89 (2003) 43–76.

[19] N. Robertson and P. D. Seymour, Graph Minors. XX. Wagner’s Conjecture, J. Combin. Theory Ser. B, 92 (2004) 325–357.

[20] G.-C. Rota, Combinatorial theory, old and new, In Proc. Internat. Cong. Math. (Nice, 1970), Gauthier-Villars, Paris, 229–233.

[21] P. D. Seymour, Matroid representation over GF (3) , J. Combin. Theory Ser. B, 26 (1979) 159–173.

[22] J. F. Geelen, A. M. H. Gerards, and A. Kapoor, The excluded minors for GF (4) -representable matroids, J. Combin. Theory Ser. B, 79 (2000) 247–299.

[23] J. F. Geelen, A. M. H. Gerards and A. Kapoor, Recognizing graphic matroids, Combinatorica, 1 (1981) 387–394.

[24] W. T. Tutte, A homotopy theorem for matroids, I, II, Trans. Amer. Math. Soc., 88 (1958) 144–174.

[25] W. T. Tutte, Matroids and graphs, Trans. Amer. Math. Soc., 90 (1959) 527–552.

[26] W. T. Tutte, Lectures on matroids, J. Nat. Bur. Standards Sect. B, 69 (1965) 1–47.

[27] H. Whitney, Non-separable and planar graphs, Trans. Amer. Math. Soc., 34 (1932) 339–362.

[28] H. Whitney, On the abstract properties of linear dependence, Amer. J. Math., 57 (1935) 509–533.

[29] G. Whittle, Stabilizers of classes of representable matroids, J. Combin. Theory Ser. B, 77 (1999) 39–72.

[30] P. Vámos, A necessary and sufficient condition for a matroid to be linear, In Möbius algebras (Proc. Conf. Univ. Waterloo), University of Waterloo, Waterloo, 1971 162–169