نظرية هول للزواج

يترك${\displaystyle {\mathcal {F}}}$لتكن عائلة منتهية من المجموعات (لاحظ أنه على الرغم من${\displaystyle {\mathcal {F}}}$لا يُسمح لها في حد ذاتها بأن تكون لانهائية، ولكن قد تكون المجموعات الموجودة فيها كذلك، و${\displaystyle {\mathcal {F}}}$قد تحتوي على نفس المجموعة عدة مرات ). ^{[ 1 ]} ليكن${\displaystyle X}$كن اتحاد جميع المجموعات في${\displaystyle {\mathcal {F}}}$، مجموعة العناصر التي تنتمي إلى مجموعة واحدة على الأقل من مجموعاتها. مستعرض لـ${\displaystyle {\mathcal {F}}}$هي مجموعة فرعية من${\displaystyle X}$يمكن الحصول على ذلك عن طريق اختيار عنصر مميز من كل مجموعة في${\displaystyle {\mathcal {F}}}$يمكن صياغة هذا المفهوم بشكل رسمي من خلال تعريف المستعرض بأنه صورة دالة أحادية .${\displaystyle f:{\mathcal {F}}\to X}$بحيث${\displaystyle f(S)\in S}$لكل${\displaystyle S\in {\mathcal {F}}}$. مصطلح بديل للمصطلح المستعرض هو نظام الممثلين المتميزين .

المجموعة${\displaystyle {\mathcal {F}}}$يستوفي شرط الزواج عندما تكون كل عائلة فرعية من${\displaystyle {\mathcal {F}}}$تحتوي على عدد من العناصر المتميزة يساوي على الأقل عدد مجموعاتها. أي، بالنسبة لجميع${\displaystyle {\mathcal {G}}\subseteq {\mathcal {F}}}$، $${\displaystyle |{\mathcal {G}}|\leq {\Bigl |}\bigcup _{S\in {\mathcal {G}}}S{\Bigr |}.}$$ إذا وُجد خط عرضي، فإن شرط الزواج يجب أن يكون صحيحًا: الدالة${\displaystyle f}$تُستخدم لتحديد الخرائط المستعرضة${\displaystyle {\mathcal {G}}}$إلى مجموعة فرعية من اتحادها، بحجم يساوي${\displaystyle |{\mathcal {G}}|}$لذا، يجب أن يكون الاتحاد بأكمله على الأقل بنفس الحجم. وتنص نظرية هول على أن العكس صحيح أيضًا:

جاء اسم "نظرية الزواج" من ( هالموس وفون 1950 )

لنفترض أن كل واحد من مجموعة (قد تكون لانهائية) من الأولاد يعرف مجموعة منتهية من الفتيات. ما هي الشروط التي تسمح لكل ولد بالزواج من إحدى معارفه؟ من الواضح أنه من الضروري أن تكون كل مجموعة منتهية من k ولد، مجتمعة، على دراية بما لا يقل عن k فتاة... وهذا الشرط كافٍ أيضاً.

المثال 1

ضع العائلة في اعتبارك${\displaystyle {\mathcal {F}}=\{A_{1},A_{2},A_{3}\}}$مع${\displaystyle X=\{1,2,3,4,5\}}$و$${\displaystyle {\begin{aligned}A_{1}&=\{1,2,3\}\\A_{2}&=\{1,4,5\}\\A_{3}&=\{3,5\}.\\\end{aligned}}}$$العرضي${\displaystyle \{1,3,5\}}$يمكن توليدها بواسطة الدالة التي تقوم بالربط${\displaystyle A_{1}}$ل${\displaystyle 1}$،${\displaystyle A_{2}}$ل${\displaystyle 5}$، و${\displaystyle A_{3}}$ل${\displaystyle 3}$أو بدلاً من ذلك، عن طريق الدالة التي تقوم بالربط${\displaystyle A_{1}}$ل${\displaystyle 3}$،${\displaystyle A_{2}}$ل${\displaystyle 1}$، و${\displaystyle A_{3}}$ل${\displaystyle 5}$وهناك عوارض أخرى، مثل${\displaystyle \{1,2,3\}}$و${\displaystyle \{1,4,5\}}$بما أن هذه العائلة تضم على الأقل فرداً واحداً عابراً، فإن شرط الزواج مُستوفى. كل عائلة فرعية من${\displaystyle {\mathcal {F}}}$له حجم متساوٍ مع مجموعة الممثلين التي يتم تعيينه لها، وهو أقل من أو يساوي حجم اتحاد العائلة الفرعية.

المثال 2

يعتبر${\displaystyle {\mathcal {F}}=\{A_{1},A_{2},A_{3},A_{4}\}}$مع$${\displaystyle {\begin{aligned}A_{1}&=\{2,3,4,5\}\\A_{2}&=\{4,5\}\\A_{3}&=\{5\}\\A_{4}&=\{4\}.\\\end{aligned}}}$$لا يوجد تقاطع صحيح؛ تم انتهاك شرط الزواج كما يتضح من العائلة الفرعية.${\displaystyle {\mathcal {G}}=\{A_{2},A_{3},A_{4}\}}$هنا، عدد المجموعات في العائلة الفرعية هو${\displaystyle |{\mathcal {G}}|=3}$بينما اتحاد المجموعات الثلاث${\displaystyle A_{2}\cup A_{3}\cup A_{4}=\{4,5\}}$يحتوي على عنصرين فقط.

حد أدنى لعدد المقاطع العرضية المختلفة التي تمتلكها عائلة محدودة معينة${\displaystyle {\mathcal {F}}}$من الحجم${\displaystyle n}$قد يتم الحصول على ما يلي: إذا كانت كل مجموعة من المجموعات في${\displaystyle {\mathcal {F}}}$له عددية${\displaystyle \geq r}$ثم عدد المقاطع العرضية المختلفة لـ${\displaystyle {\mathcal {F}}}$إما${\displaystyle r!}$لو${\displaystyle r\leq n}$، أو${\displaystyle r(r-1)\cdots (r-n+1)}$لو${\displaystyle r>n}$[ ^{2 ]​}

تذكر أن المقطع العرضي للعائلة${\displaystyle {\mathcal {F}}}$هي متتالية مرتبة، لذا يمكن أن يحتوي مستعرضان مختلفان على نفس العناصر تمامًا. على سبيل المثال، المجموعة${\displaystyle A_{1}=\{1,2,3\}}$،${\displaystyle A_{2}=\{1,2,5\}}$لديه${\displaystyle (1,2)}$و${\displaystyle (2,1)}$كعناصر عرضية متميزة.

مشكلة في الصياغة التوافقية، تُعرَّف بواسطة عائلة منتهية من المجموعات المنتهية${\displaystyle {\mathcal {F}}}$مع النقابة${\displaystyle X}$يمكن ترجمتها إلى رسم بياني ثنائي الأجزاء${\displaystyle G=({\mathcal {F}},X,E)}$حيث يربط كل ضلع مجموعة في${\displaystyle {\mathcal {F}}}$إلى عنصر من تلك المجموعة.${\displaystyle {\mathcal {F}}}$- يُعرّف التطابق التام في هذا الرسم البياني نظامًا من الممثلين الفريدين لـ${\displaystyle {\mathcal {F}}}$. في الاتجاه الآخر، من أي رسم بياني ثنائي الأجزاء${\displaystyle G=(X,Y,E)}$يمكن تعريف عائلة منتهية من المجموعات، وهي عائلة جوارات الرؤوس في${\displaystyle X}$بحيث يتوافق أي نظام من الممثلين الفريدين لهذه العائلة مع${\displaystyle X}$-تطابق مثالي في${\displaystyle G}$وبهذه الطريقة، يكون الصياغة التوافقية للعائلات المحدودة من المجموعات المحدودة والصياغة النظرية للرسوم البيانية المحدودة متكافئة.

وينطبق التكافؤ نفسه على العائلات اللانهائية من المجموعات المنتهية وعلى بعض الرسوم البيانية اللانهائية. في هذه الحالة، يتوافق شرط أن تكون كل مجموعة منتهية مع شرط أن تكون في الرسم البياني ثنائي الأجزاء${\displaystyle G=(X,Y,E)}$، كل رأس في${\displaystyle X}$يجب أن تكون درجة الرؤوس محدودة . درجات الرؤوس في${\displaystyle Y}$غير مقيدة.

من خلال فحص برهان فيليب هول الأصلي بعناية، تمكن مارشال هول الابن (لا تربطه صلة قرابة بفيليب هول) من تعديل النتيجة بطريقة سمحت للبرهان بالعمل في حالة اللانهاية.${\displaystyle {\mathcal {F}}}$[ ^{10 ] هذا} المتغير يوسع نظرية الزواج لفيليب هول.

لنفترض أن${\displaystyle {\mathcal {F}}=\{A_{i}\}_{i\in I}}$، هي عائلة (ربما لا نهائية) من المجموعات المنتهية التي لا يشترط أن تكون متميزة، إذن${\displaystyle {\mathcal {F}}}$يكون مستعرضًا إذا وفقط إذا${\displaystyle {\mathcal {F}}}$يفي بشرط الزواج.

يوضح المثال التالي، الذي يعود إلى مارشال هول جونيور، أن شرط الزواج لن يضمن وجود قاطع في عائلة لانهائية يُسمح فيها بالمجموعات اللانهائية.

يترك${\displaystyle {\mathcal {F}}}$كن عائلة،${\displaystyle A_{0}=\mathbb {N} }$،${\displaystyle A_{i}=\{i-1\}}$ل${\displaystyle i\geq 1}$ينطبق شرط الزواج على هذه العائلة اللانهائية، ولكن لا يمكن إنشاء أي تقاطع. ^{[ 11 ]}

يمكن صياغة نظرية الزواج في الرسم البياني، وفقًا لتوسيع مارشال هول لنظرية الزواج، على النحو التالي: إذا كان لدينا رسم بياني ثنائي الأجزاء بأضلاع A و B ، نقول إن مجموعة جزئية C من B أصغر من أو تساوي في الحجم مجموعة جزئية D من A في الرسم البياني إذا وُجد تقابل داخلي (باستخدام حواف الرسم البياني فقط) من C إلى D ، وأنها أصغر تمامًا في الرسم البياني إذا لم يكن هناك تقابل داخلي في الرسم البياني في الاتجاه المعاكس. تجدر الإشارة إلى أن حذف التقابل الداخلي في الرسم البياني يُعطي المفهوم المعتاد لمقارنة عدد عناصر كل مجموعة. تنص نظرية الزواج اللانهائية على أنه يوجد تقابل داخلي من A إلى B في الرسم البياني، إذا وفقط إذا لم تكن هناك مجموعة جزئية C من A بحيث يكون N ( C ) أصغر تمامًا من C في الرسم البياني. ^{[ 12 ]}

إن المشكلة الأكثر عمومية المتمثلة في اختيار عنصر (ليس بالضرورة متميزًا) من كل مجموعة من المجموعات غير الفارغة (دون قيود على عدد المجموعات أو حجم المجموعات) مسموح بها بشكل عام فقط إذا تم قبول بديهية الاختيار .