نظرية روبرتسون-سيمور

في نظرية المخططات ، تنص نظرية روبرتسون-سيمور (المعروفة أيضًا بنظرية المخططات الصغرى ^{[ 1 ]} ) على أن المخططات غير الموجهة ، المرتبة جزئيًا بعلاقة المخططات الصغرى ، تُشكل ترتيبًا شبه منتظم . ^{[ 2 ]} وبالمثل، يمكن تعريف كل عائلة من المخططات المغلقة تحت أخذ المخططات الصغرى بمجموعة منتهية من المخططات الصغرى المحظورة ، بنفس الطريقة التي تُميز بها نظرية فاغنر المخططات المستوية بأنها المخططات التي لا تمتلك مخططًا كاملاً.${\displaystyle K_{5}}$أو الرسم البياني الثنائي الكامل${\displaystyle K_{3,3}}$بصفتهم قاصرين.

سُميت نظرية روبرتسون-سيمور نسبةً إلى عالمي الرياضيات نيل روبرتسون وبول د. سيمور ، اللذين أثبتاها في سلسلة من عشرين بحثًا امتدت على أكثر من 500 صفحة بين عامي 1983 و2004. ^{[ 3 ]} قبل إثباتها، عُرفت صيغة النظرية باسم حدسية فاغنر نسبةً إلى عالم الرياضيات الألماني كلاوس فاغنر ، على الرغم من أن فاغنر نفى أنه وضع هذه الحدسية قط. ^{[ 4 ]}

[ 5 ]​​​​​​^​​​

أحد أجزاء الرسم البياني غير الموجه${\displaystyle G}$أي رسم بياني يمكن الحصول عليه من${\displaystyle G}$من خلال سلسلة من صفر أو أكثر من انقباضات حواف${\displaystyle G}$وحذف الحواف والرؤوس من${\displaystyle G}$تشكل علاقة التقسيم الجزئي ترتيبًا جزئيًا على مجموعة جميع الرسوم البيانية المحدودة غير الموجهة المتميزة، لأنها تخضع لبديهيات الترتيب الجزئي الثلاث: فهي انعكاسية (كل رسم بياني هو تقسيم جزئي لنفسه)، ومتعدية (تقسيم جزئي لتقسيم جزئي لـ${\displaystyle G}$وهي نفسها قاصر من${\displaystyle G}$)، ومتناظر عكسيًا (إذا كان هناك رسمان بيانيان)${\displaystyle G}$و${\displaystyle G}$إذا كانت الرسوم البيانية المتماثلة جزئية لبعضها البعض، فلا بد أنها متماثلة . ومع ذلك، إذا أمكن اعتبار الرسوم البيانية المتماثلة كائنات متميزة، فإن ترتيب الجزئيات على الرسوم البيانية يشكل ترتيبًا جزئيًا ، وهي علاقة انعكاسية ومتعدية ولكنها ليست بالضرورة مضادة للتناظر. ^{[ 6 ]}

يُقال إن الترتيب المسبق يُشكل ترتيبًا شبه جيد إذا لم يحتوِ على سلسلة تنازلية لانهائية ولا على سلسلة مضادة لانهائية . ^{[ 7 ]} على سبيل المثال، يُعد الترتيب المعتاد للأعداد الصحيحة غير السالبة ترتيبًا شبه جيد، لكن الترتيب نفسه على مجموعة جميع الأعداد الصحيحة ليس كذلك، لأنه يحتوي على السلسلة التنازلية اللانهائية 0، -1 ، -2 ، -3 ... مثال آخر هو مجموعة الأعداد الصحيحة الموجبة المرتبة حسب قابلية القسمة ، والتي لا تحتوي على سلاسل تنازلية لانهائية، ولكن الأعداد الأولية تُشكل فيها سلسلة مضادة لانهائية.   

تنص نظرية روبرتسون-سيمور على أن الرسوم البيانية غير الموجهة المحدودة والمخططات الجزئية تشكل ترتيبًا شبه منتظم. لا تحتوي علاقة المخطط الجزئي على أي سلسلة تنازلية لانهائية، لأن كل انكماش أو حذف يقلل من عدد الحواف والرؤوس في الرسم البياني (عدد صحيح غير سالب). ^{[ 8 ]} الجزء غير البديهي من النظرية هو أنه لا توجد سلاسل مضادة لانهائية، أي مجموعات لانهائية من الرسوم البيانية غير المرتبطة ببعضها البعض بترتيب المخطط الجزئي.${\displaystyle {\mathcal {S}}}$هي مجموعة من الرسوم البيانية، و${\displaystyle {\mathcal {M}}}$هي مجموعة فرعية من${\displaystyle {\mathcal {S}}}$يحتوي على رسم بياني تمثيلي واحد لكل فئة تكافؤ من العناصر الدنيا (الرسوم البيانية التي تنتمي إلى${\displaystyle {\mathcal {S}}}$لكن لا ينتمي إليها أي قاصر مناسب${\displaystyle {\mathcal {S}}}$)، ثم${\displaystyle {\mathcal {M}}}$يشكل سلسلة مضادة؛ لذلك، فإن طريقة مكافئة لصياغة النظرية هي أنه في أي مجموعة لانهائية${\displaystyle {\mathcal {S}}}$بالنسبة للرسوم البيانية، يجب أن يكون هناك عدد محدود فقط من العناصر الدنيا غير المتماثلة.

صيغة أخرى مكافئة للنظرية هي أنه في أي مجموعة غير منتهية${\displaystyle {\mathcal {S}}}$من بين كل مجموعة من الرسوم البيانية، يجب أن يكون هناك زوج من الرسوم البيانية يكون أحدهما أصغر من الآخر. ^{[ 8 ]} إن القول بأن كل مجموعة لانهائية تحتوي على عدد محدود من العناصر الدنيا يستلزم هذا الشكل من النظرية، لأنه إذا كان هناك عدد محدود فقط من العناصر الدنيا، فإن كل رسم بياني من الرسوم البيانية المتبقية يجب أن ينتمي إلى زوج من هذا النوع مع أحد العناصر الدنيا. وفي الاتجاه الآخر، يستلزم هذا الشكل من النظرية القول بأنه لا يمكن أن توجد سلاسل مضادة لانهائية، لأن السلسلة المضادة اللانهائية هي مجموعة لا تحتوي على أي زوج مرتبط بعلاقة أصغر.

عائلة${\displaystyle {\mathcal {F}}}$يُقال إن مجموعة من الرسوم البيانية مغلقة تحت عملية أخذ المحددات الصغرى إذا كان كل محدد صغرى لرسم بياني في${\displaystyle {\mathcal {F}}}$ينتمي أيضًا إلى${\displaystyle {\mathcal {F}}}$. لو${\displaystyle {\mathcal {F}}}$إذا كانت عائلة صغيرة مغلقة، فدع${\displaystyle {\mathcal {S}}}$ليكن فئة الرسوم البيانية التي ليست في${\displaystyle {\mathcal {F}}}$( مكمل لـ${\displaystyle {\mathcal {F}}}$وفقًا لنظرية روبرتسون-سيمور، توجد مجموعة منتهية${\displaystyle {\mathcal {H}}}$من العناصر الدنيا في${\displaystyle {\mathcal {S}}}$تشكل هذه العناصر الدنيا توصيفًا للرسم البياني المحظور لـ${\displaystyle {\mathcal {F}}}$الرسوم البيانية في${\displaystyle {\mathcal {F}}}$هي بالضبط الرسوم البيانية التي لا تحتوي على أي رسم بياني في${\displaystyle {\mathcal {H}}}$بصفته قاصرًا. ^{[ 9 ]} أعضاء${\displaystyle {\mathcal {H}}}$يُطلق عليهم اسم القاصرين المستبعدين (أو القاصرين الممنوعين ، أو القاصرين ذوي العوائق البسيطة ) بالنسبة للعائلة${\displaystyle {\mathcal {F}}}$.

على سبيل المثال، تكون الرسوم البيانية المستوية مغلقة عند أخذ المحددات الصغرى: فتقليص حافة في رسم بياني مستوٍ، أو إزالة حواف أو رؤوس من الرسم البياني، لا يمكن أن يُخلّ بخاصية استوائه. لذلك، تتميز الرسوم البيانية المستوية بخاصية المحددات الصغرى المحظورة، والتي تُعطى في هذه الحالة بواسطة نظرية فاغنر : المجموعة${\displaystyle {\mathcal {H}}}$تحتوي مجموعة الرسوم البيانية غير المستوية ذات الحد الأدنى على رسمين بيانيين فقط، وهو الرسم البياني الكامل${\displaystyle K_{5}}$والرسم البياني الثنائي الكامل${\displaystyle K_{3,3}}$والرسوم البيانية المستوية هي تحديدًا الرسوم البيانية التي لا تحتوي على قاصر في المجموعة${\displaystyle {\mathcal {H}}=\{K_{5},K_{3,3}\}.}$

إن وجود خصائص فرعية محظورة لجميع عائلات الرسوم البيانية المغلقة فرعيًا هو طريقة مكافئة لصياغة نظرية روبرتسون-سيمور. على سبيل المثال، لنفترض أن كل عائلة مغلقة فرعيًا${\displaystyle {\mathcal {F}}}$لها مجموعة منتهية${\displaystyle {\mathcal {H}}}$من الحد الأدنى من القاصرين الممنوعين، ودع${\displaystyle {\mathcal {S}}}$ليكن أي مجموعة لانهائية من الرسوم البيانية. حدد${\displaystyle {\mathcal {F}}}$من${\displaystyle {\mathcal {S}}}$باعتبارها عائلة الرسوم البيانية التي لا تحتوي على صغرى في${\displaystyle {\mathcal {S}}}$. ثم${\displaystyle {\mathcal {F}}}$هي مجموعة مغلقة جزئياً ولها مجموعة منتهية${\displaystyle {\mathcal {H}}}$من الحد الأدنى من القاصرين الممنوعين. دع${\displaystyle {\mathcal {C}}}$كن مكملاً لـ${\displaystyle {\mathcal {F}}}$.${\displaystyle {\mathcal {S}}}$هي مجموعة فرعية من${\displaystyle {\mathcal {C}}}$منذ${\displaystyle {\mathcal {S}}}$و${\displaystyle {\mathcal {F}}}$منفصلة، ​​و${\displaystyle {\mathcal {H}}}$هي الرسوم البيانية الدنيا في${\displaystyle {\mathcal {C}}}$لنفترض وجود رسم بياني${\displaystyle G}$في${\displaystyle {\mathcal {H}}}$.${\displaystyle G}$لا يمكن الحصول على تخصص فرعي مناسب في${\displaystyle {\mathcal {S}}}$منذ${\displaystyle G}$ضئيل في${\displaystyle {\mathcal {C}}}$في الوقت نفسه،${\displaystyle G}$يجب أن يكون لديه تخصص فرعي في${\displaystyle S}$وإلا${\displaystyle G}$سيكون عنصرًا في${\displaystyle {\mathcal {F}}}$. لذلك،${\displaystyle G}$هو عنصر في${\displaystyle {\mathcal {S}}}$، أي،${\displaystyle {\mathcal {H}}}$هي مجموعة فرعية من${\displaystyle {\mathcal {S}}}$وجميع الرسوم البيانية الأخرى في${\displaystyle {\mathcal {S}}}$يوجد رسم بياني فرعي ضمن الرسوم البيانية في${\displaystyle {\mathcal {H}}}$، لذا${\displaystyle {\mathcal {H}}}$هي المجموعة المحدودة من العناصر الدنيا لـ${\displaystyle {\mathcal {S}}}$.

ولإثبات الاتجاه الآخر للتكافؤ، افترض أن كل مجموعة من الرسوم البيانية تحتوي على مجموعة جزئية منتهية من الرسوم البيانية الدنيا، ولتكن مجموعة مغلقة جزئيًا${\displaystyle {\mathcal {F}}}$لدينا مجموعة معطاة. نريد إيجاد مجموعة${\displaystyle {\mathcal {H}}}$من الرسوم البيانية بحيث يكون الرسم البياني في${\displaystyle {\mathcal {F}}}$إذا وفقط إذا لم يكن لديه قاصر في${\displaystyle {\mathcal {H}}}$. يترك${\displaystyle {\mathcal {E}}}$لتكن الرسوم البيانية التي ليست رسومًا بيانية صغيرة لأي رسم بياني في${\displaystyle {\mathcal {F}}}$ودع${\displaystyle {\mathcal {H}}}$لتكن المجموعة المنتهية من الرسوم البيانية الدنيا في${\displaystyle {\mathcal {E}}}$الآن، لنفترض وجود رسم بياني عشوائي${\displaystyle G}$لنفترض أولاً أن${\displaystyle G}$هو في${\displaystyle {\mathcal {F}}}$.${\displaystyle G}$لا يجوز أن يكون هناك قاصر في${\displaystyle {\mathcal {H}}}$منذ${\displaystyle G}$هو في${\displaystyle {\mathcal {F}}}$و${\displaystyle {\mathcal {H}}}$هي مجموعة فرعية من${\displaystyle {\mathcal {E}}}$والآن افترض أن${\displaystyle G}$ليس في${\displaystyle {\mathcal {F}}}$. ثم${\displaystyle G}$ليس قاصرًا لأي رسم بياني في${\displaystyle {\mathcal {F}}}$، منذ${\displaystyle {\mathcal {F}}}$مغلق جزئيًا. لذلك،${\displaystyle G}$هو في${\displaystyle {\mathcal {E}}}$، لذا${\displaystyle G}$لديه تخصص فرعي في${\displaystyle {\mathcal {H}}}$.

المجموعات التالية من الرسوم البيانية المحدودة مغلقة جزئيًا، وبالتالي (بحسب نظرية روبرتسون-سيمور) لها خصائص فرعية محظورة:

• الغابات ، والغابات الخطية ( اتحادات منفصلة من مخططات المسار )، والغابات الزائفة ، ومخططات الصبار ؛
• الرسوم البيانية المستوية ، والرسوم البيانية الخارجية المستوية ، والرسوم البيانية الرأسية (التي تتشكل بإضافة رأس واحد إلى رسم بياني مستوٍ)، والرسوم البيانية الحلقية ، والرسوم البيانية التي يمكن تضمينها على أي مشعب ثنائي الأبعاد ثابت ؛ ^{[ 10 ]}
• الرسوم البيانية التي يمكن تضمينها بدون روابط في الفضاء الإقليدي ثلاثي الأبعاد، والرسوم البيانية التي يمكن تضمينها بدون عقد في الفضاء الإقليدي ثلاثي الأبعاد؛ ^{[ 10 ]}
• الرسوم البيانية ذات مجموعة رؤوس التغذية الراجعة بحجم محدود بثابت ثابت؛ الرسوم البيانية ذات ثابت الرسم البياني كولين دي فيرديير المحدود بثابت ثابت؛ الرسوم البيانية ذات عرض الشجرة أو عرض المسار أو عرض الفرع المحدود بثابت ثابت.

كانت بعض الأمثلة على مجموعات العوائق المحدودة معروفة بالفعل لفئات محددة من الرسوم البيانية قبل إثبات نظرية روبرتسون-سيمور. على سبيل المثال، العائق لمجموعة جميع الغابات هو الرسم البياني الحلقي (أو، إذا اقتصرنا على الرسوم البيانية البسيطة ، الدورة ذات الرؤوس الثلاثة). هذا يعني أن الرسم البياني غابة إذا وفقط إذا لم يكن أي من أجزائه الصغرى هو الرسم البياني الحلقي (أو الدورة ذات الرؤوس الثلاثة، على التوالي). العائق الوحيد لمجموعة المسارات هو الشجرة ذات الرؤوس الأربعة، أحدها من الدرجة 3. في هذه الحالات، تحتوي مجموعة العوائق على عنصر واحد، ولكن هذا ليس هو الحال بشكل عام. تنص نظرية فاغنر على أن الرسم البياني مستوٍ إذا وفقط إذا لم يكن يحتوي على أي من${\displaystyle K_{5}}$ولا${\displaystyle K_{3,3}}$كتخصص فرعي. بعبارة أخرى، المجموعة${\displaystyle \{K_{5},K_{3,3}\}}$هي مجموعة عوائق لمجموعة جميع الرسوم البيانية المستوية، وهي في الواقع مجموعة العوائق الدنيا الوحيدة. وتنص نظرية مماثلة على أن${\displaystyle K_{4}}$و${\displaystyle K_{2,3}}$هي القواسم الصغرى المحظورة لمجموعة الرسوم البيانية الخارجية المستوية.

على الرغم من أن نظرية روبرتسون-سيمور تُعمم هذه النتائج لتشمل عائلات الرسوم البيانية المغلقة جزئيًا، إلا أنها لا تُغني عنها تمامًا، لأنها لا تُقدم وصفًا صريحًا لمجموعة العوائق لأي عائلة. فعلى سبيل المثال، تُخبرنا أن مجموعة الرسوم البيانية الحلقية لها مجموعة عوائق محدودة، لكنها لا تُحدد أي مجموعة من هذا القبيل. ولا تزال المجموعة الكاملة للقواسم المحظورة للرسوم البيانية الحلقية مجهولة، ولكنها تحتوي على 17535 رسمًا بيانيًا على الأقل. ^{[ 11 ]}

تُعدّ نظرية روبرتسون-سيمور ذات أهمية بالغة في مجال التعقيد الحسابي، وذلك بفضل البرهان الذي قدمه روبرتسون وسيمور والذي ينص على أنه لكل رسم بياني ثابت${\displaystyle H}$يوجد خوارزمية زمنية متعددة الحدود لاختبار ما إذا كان الرسم البياني يحتوي على${\displaystyle H}$كعنصر فرعي. زمن تشغيل هذه الخوارزمية مكعب (في حجم الرسم البياني المراد فحصه)، مع وجود عامل ثابت يعتمد بشكل فائق على حجم العنصر الفرعي.${\displaystyle H}$تم تحسين وقت التشغيل إلى تربيعي بواسطة كاواراباياشي وكوباياشي وريد. ^{[ 12 ]} ونتيجة لذلك، لكل عائلة قاصر مغلقة${\displaystyle {\mathcal {F}}}$يوجد خوارزمية زمنية متعددة الحدود لاختبار ما إذا كان الرسم البياني ينتمي إلى${\displaystyle {\mathcal {F}}}$: تحقق مما إذا كان الرسم البياني المعطى يحتوي على${\displaystyle H}$لكل قاصر ممنوع${\displaystyle H}$في مجموعة العوائق من${\displaystyle {\mathcal {F}}}$[ ^{13 ]​}

مع ذلك، تتطلب هذه الطريقة مجموعة عوائق محدودة محددة لكي تعمل، ولا توفرها النظرية. تُثبت النظرية وجود مثل هذه المجموعة المحدودة من العوائق، وبالتالي فإن المسألة متعددة الحدود بفضل الخوارزمية المذكورة أعلاه. ولكن، لا يمكن استخدام الخوارزمية عمليًا إلا في حال توفر هذه المجموعة المحدودة من العوائق. ونتيجة لذلك، تُثبت النظرية إمكانية حل المسألة في زمن متعدد الحدود، لكنها لا تُقدم خوارزمية محددة متعددة الحدود لحلها. تُعدّ هذه البراهين على تعددية الحدود غير بنائية : فهي تُثبت تعددية حدود المسائل دون تقديم خوارزمية صريحة متعددة الحدود. ^{[ 14 ]} في العديد من الحالات الخاصة، يمكن التحقق من انتماء رسم بياني إلى عائلة مغلقة جزئيًا معينة بكفاءة أكبر: على سبيل المثال، يمكن التحقق من كون الرسم البياني مستويًا في زمن خطي.

بالنسبة لثوابت الرسم البياني التي تتميز بالخاصية التالية، لكل${\displaystyle k}$، الرسوم البيانية ذات الثابت على الأكثر${\displaystyle k}$إذا كانت المجموعات الفرعية مغلقة، ينطبق عليها نفس الأسلوب. على سبيل المثال، وفقًا لهذه النتيجة، فإن عرض الشجرة، وعرض الفرع، وعرض المسار، وتغطية الرؤوس ، والحد الأدنى لجنس التضمين، كلها قابلة لهذا النهج، ولأي قيمة ثابتة${\displaystyle k}$توجد خوارزمية ذات وقت متعدد الحدود لاختبار ما إذا كانت هذه الثوابت على الأكثر${\displaystyle k}$، حيث لا يعتمد الأس في وقت تشغيل الخوارزمية على${\displaystyle k}$تكمن إحدى المشكلات المتعلقة بهذه الخاصية في إمكانية حلها في وقت متعدد الحدود لأي قيمة ثابتة.${\displaystyle k}$مع أس لا يعتمد على${\displaystyle k}$، وهو ما يُعرف باسم قابلية المعالجة ذات المعلمات الثابتة .

ومع ذلك، لا توفر هذه الطريقة بشكل مباشر خوارزمية واحدة قابلة للمعالجة بمعاملات ثابتة لحساب قيمة المعامل لرسم بياني معين ذي معلمات غير معروفة.${\displaystyle k}$بسبب صعوبة تحديد مجموعة القواسم الصغرى المحظورة. إضافةً إلى ذلك، فإن العوامل الثابتة الكبيرة المتضمنة في هذه النتائج تجعلها غير عملية للغاية. لذلك، فإن تطوير خوارزميات صريحة ذات معلمات ثابتة لهذه المشكلات، مع تحسين الاعتماد على${\displaystyle k}$ولا يزال هذا المجال يمثل خطاً بحثياً مهماً.

أظهر فريدمان وروبرتسون وسيمور (1987) أن النظرية التالية تُظهر ظاهرة الاستقلال من خلال كونها غير قابلة للإثبات في أنظمة رسمية مختلفة أقوى بكثير من حساب بيانو ، ومع ذلك فهي قابلة للإثبات في أنظمة أضعف بكثير من ZFC : ^{[ 15 ]}

النظرية : لكل عدد صحيح موجب${\displaystyle n}$يوجد عدد صحيح${\displaystyle m}$كبيرة جدًا لدرجة أنه إذا${\displaystyle G_{1},\dots ,G_{m}}$هي سلسلة من الرسوم البيانية غير الموجهة المحدودة، حيث كل${\displaystyle G_{i}}$حجمه في أقصى حد${\displaystyle n+i}$، ثم${\displaystyle G_{j}\leq G_{k}}$بالنسبة للبعض${\displaystyle j\leq k}$.

(هنا، حجم الرسم البياني هو العدد الإجمالي لرؤوسه وحوافه، و ≤ يشير إلى الترتيب الأدنى.)

يستخدم فريدمان هذه النتيجة على الرسوم البيانية شبه المكعبة البسيطة لإنشاء الدالة سريعة النمو، SSCG . ^{[ 16 ]}

• نظرية بنية الرسم البياني

• بينستوك، دانيال؛ لانغستون، مايكل أ. (1995)، "الآثار الخوارزمية لنظرية الرسم البياني الصغرى" (ملف PDF) ، نماذج الشبكات ، كتيبات في بحوث العمليات وعلوم الإدارة، المجلد  7، الصفحات 481-502 ، doi : 10.1016/S0927-0507(05)80125-2 ، ISBN  978-0-444-89292-8.
• ديستل، راينهارد ( 2005)، "المجموعات الفرعية، والأشجار، وWQO"، نظرية الرسم البياني (PDF) (الطبعة الإلكترونية 2005  )، سبرينغر، ص 326-367 .
• فيلوز، مايكل ر .؛ لانغستون، مايكل أ. (1988)، "أدوات غير بنائية لإثبات قابلية الحسم في وقت متعدد الحدود"، مجلة ACM ، 35 (3): 727-739 ، doi : 10.1145/44483.44491.
• فريدمان، هارفي ؛ روبرتسون، نيل ؛ سيمور، بول (1987)، "الرياضيات الفوقية لنظرية الرسم البياني الصغرى"، في سيمبسون، س. (محرر)، المنطق والتوافقية ، الرياضيات المعاصرة، المجلد  65، الجمعية الرياضية الأمريكية ، الصفحات 229-261 .
• فريدمان، هارفي (2006). " [ FOM ] 274: أعداد الرسوم البيانية شبه المكعبة" . قسم الرياضيات ، جامعة ولاية أوهايو . مؤرشف من الأصل في 7 أبريل 2024.
• كاواراباياشي، كين-إيتشي ؛ كوباياشي، يوسوكي؛ ريد، بروس (2012)، "مسألة المسارات المنفصلة في زمن تربيعي" (ملف PDF) ، مجلة نظرية التوافيق، السلسلة ب ، 102 (2): 424-435 ، doi : 10.1016/j.jctb.2011.07.004.
• Lovász، László (2005)، “Graph Minor Theory”، نشرة الجمعية الرياضية الأمريكية ، سلسلة جديدة، 43 (1): 75–86 ، دوى : 10.1090 / S0273-0979-05-01088-8.
• ميرفولد، ويندي ؛ وودكوك، جينيفر (2018)، "مجموعة كبيرة من عوائق الطارة وكيف تم اكتشافها" ، المجلة الإلكترونية للتوافقية ، 25 (1): P1.16، doi : 10.37236/3797.
• روبرتسون، نيل ؛ سيمور، بول (1983)، "الرسوم البيانية الصغرى. الجزء الأول: استبعاد الغابة"، مجلة نظرية التوافيق، السلسلة ب ، 35 (1): 39-61 ، doi : 10.1016/0095-8956(83)90079-5.
• روبرتسون، نيل ؛ سيمور، بول (1995)، "الرسوم البيانية الصغرى. الثالث عشر. مشكلة المسارات المنفصلة"، مجلة نظرية التوافيق، السلسلة ب ، 63 (1): 65-110 ، doi : 10.1006/jctb.1995.1006.
• روبرتسون، نيل ؛ سيمور، بول (2004)، "الرسوم البيانية الصغرى. العشرون. حدسية فاغنر"، مجلة نظرية التوافيق، السلسلة ب ، 92 (2): 325-357 ، doi : 10.1016/j.jctb.2004.08.001.

• وايسشتاين، إريك دبليو ، "نظرية روبرتسون-سيمور" ، عالم الرياضيات