कबूतर सिद्धांत और यादृच्छिक ग्राफ
मुझे यह अभ्यास है
(पीटर जे। कैमरून) साबित करें कि हर अनंत गणना योग्य ग्राफ के लिए $M$ निम्नलिखित बराबर हैं
- $M$ या तो यादृच्छिक है, पूर्ण या खाली (यानी $r^M = \emptyset$, दूसरे शब्दों में हर बिंदु अलग है)
- अगर $M_1, M_2 \subseteq M$ ऐसे हैं $M_1 \sqcup M_2 = M$ (यानी वे एक विभाजन बनाते हैं) तब $M_1 \simeq M$ या $M_2 \simeq M$ (कैमरन इस संपत्ति को कबूतर सिद्धांत कहते हैं)
अब मुझे इस कथन को सिद्ध करने में कुछ समस्याएँ हैं। मैंने कैमरन द्वारा लेख ( लिंक ) का पता लगाया, जिसमें यह प्रस्ताव दिखाई देता है (प्रस्ताव 4 पृष्ठ 5) लेकिन मुझे प्रस्तुत प्रमाण की समझ बनाने में कठिन समय आ रहा है। विशेष रूप से मुझे समझ नहीं आया कि हम ऐसा कैसे कह सकते हैं$X$ तथा $Y$(लेख के प्रमाण में परिभाषित) एक विभाजन बनाते हैं। कोई उपाय?
धन्यवाद
जवाब
हम दो अप्रसन्न गैर-खाली उपसमूह के साथ शुरू करते हैं $A$ तथा $B$ ऐसा है कि $A\cup B$ में एक "समान रूप से शामिल" वर्टेक्स नहीं है $\Gamma$। फिर हम बढ़ाते हैं$A$ जांच $X$: उन शीर्षकों का एक सबसेट जो अंदर नहीं है $B$ यह सही ढंग से शामिल नहीं हैं $A$। चूंकि हम स्पष्ट रूप से शामिल नहीं थे$B$ इस परिभाषा में कोने, $X$ तथा $B$साथ ही असंतुष्ट हैं। अब हम बढ़ाते हैं$B$ अंदर नहीं के साथ $X$ यह सही ढंग से शामिल नहीं हैं $B$, और एक सबसेट प्राप्त करें $Y$। इस परिभाषा के द्वारा,$X$ तथा $Y$असहमति है। इसके अलावा, अगर हमें लगता है कि वहाँ एक है$z\in\Gamma$ जिसमें से किसी में भी जाने से बचा गया $X$ तथा $Y$, तो यह दोनों के साथ सही ढंग से जुड़ा हुआ है $A$ तथा $B$, जो की प्रारंभिक पसंद का खंडन करता है $A\cup B$। इस प्रकार$X\cup Y=\Gamma$, जैसी ज़रूरत।
अब, कबूतर सिद्धांत द्वारा, $X$ या $Y$ isomorphic है $\Gamma$। समसामयिकता लेते हुए, कहते हैं,$f\colon X\to \Gamma$, हम इसे प्राप्त करते हैं $f(A)$ कम है (से) $A\cup B$) में सब्मिट करें $\Gamma$इसके पास "ठीक से शामिल" शीर्ष के अनुरूप नहीं है। अगर हमने लिया$A\cup B$ कम से कम इस तरह के सबसेट होने के लिए, हमें एक विरोधाभास मिलता है: इससे बचने का एकमात्र तरीका यह मान लेना है कि न्यूनतम ऐसा सबसेट 1 आकार का है और इसे गैर-खाली में विभाजित नहीं किया जा सकता है $A$ तथा $B$, जिसे लेख प्रमाण में ऊपर संभाला गया है।