
تعداد نشریات | 43 |
تعداد شمارهها | 1,685 |
تعداد مقالات | 13,830 |
تعداد مشاهده مقاله | 32,664,707 |
تعداد دریافت فایل اصل مقاله | 12,916,914 |
در مورد حدس روتا | ||
نشریه ریاضی و جامعه | ||
مقاله 6، دوره 2، شماره 1، خرداد 1396، صفحه 77-91 اصل مقاله (1.34 M) | ||
نوع مقاله: مقاله پژوهشی | ||
شناسه دیجیتال (DOI): 10.22108/msci.2017.20430 | ||
نویسندگان | ||
سعید علیخانی* ؛ علی نوروزی | ||
دانشگاه یزد | ||
چکیده | ||
مترویدها در تلاش برای فراهم آوردن یک رفتار مجرد یکسان از وابستگی در جبر خطی و نظریه گراف معرفی شدهاند. نام متروید ساختاری مربوط به یک ماتریس را القا میکند. تعریف ویتنی تنوعی شگفتانگیز از ساختارهای ترکیبیاتی را در برداشت. از این گذشته مترویدها به طور طبیعی در بهینهسازی ترکیبیاتی پدیدار میشوند، زیرا آنها دقیقاً همان ساختارهای ترکیبیاتی هستند که الگوریتم حریصانه برای آن به نتیجه میرسد. یکی از حدسهای مهم در نظریه متروید، حدس روتا میباشد که توسط جیان کارلو روتا، ریاضیدان و فیلسوف مشهور در سال ۱۹۷۰ مطرح شد. ما در این مقاله ضمن بیان مقدمات لازم و معرفی حدس روتا، به بررسی کلیات اثباتی که توسط جیوف ویتل از دانشگاه ویکتوریا با همکاری جیم گیلن از کانادا و برت جراردز از هلند برای آن اخیراً ارائه کردهاند، میپردازیم. | ||
کلیدواژهها | ||
متروید؛ استقلال؛ گراف؛ حدس روتا | ||
مراجع | ||
[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 | ||
آمار تعداد مشاهده مقاله: 810 تعداد دریافت فایل اصل مقاله: 1,506 |