कुछ रंग खोजने
चलो $a\geq 2$ तथा $n\geq a.$ चलो $K_n = (V,E)$ पर पूरा ग्राफ हो $n$कोने। का एक रंग$E$ एक समारोह है $f : E\to \{green, orange\}.$ इन-ए-सब्मिट के लिए $S$ का $V$, कहते हैं कि एक रंग के लिए गरीब है $S$ अगर दोनों किनारों के साथ सभी छोर अंदर हैं $S$एक ही रंग सौंपा गया है। दिखाओ कि अगर$n\leq \sqrt{2}^{a-1},$ का एक रंग है $E$ यह किसी के लिए भी गरीब नहीं है $S$, पहले के लिए colorings की संख्या को खोजने के द्वारा $E$ और रंगों की संख्या के लिए एक ऊपरी बाध्य $E$ कुछ के लिए गरीब हैं $a$-समस्त उपसमुदाय।
के लिए रंग की संख्या $E$ होना चाहिए $2^{{n\choose 2}}$। लेकिन यह भी रंग की संख्या के लिए एक ऊपरी बाध्य नहीं है$E$ कुछ के लिए गरीब हैं $S$? मुझे लगता है कि मुझे एक बेहतर ऊपरी सीमा खोजने और इस तथ्य का उपयोग करने की आवश्यकता है कि${n\choose a} < \dfrac{n^a}{a!} \leq \dfrac{n^a}2.$ अगर मैं दिखा सकता हूं कि ऊपरी रंग की संख्या के लिए बाध्य है $E$ कुछ के लिए गरीब हैं $S$ से कड़ाई से कम है $2^{{n\choose 2}},$ तो स्पष्ट रूप से वहाँ के कुछ रंग होना चाहिए $E$ यह किसी के लिए भी गरीब नहीं है $S$।
जवाब
एक निश्चित के लिए $a$-सेमेंट सेट $S$ कि हम गरीब होना चाहते हैं, हैं $2$ दोनों छोरों से किनारों को रंगने के तरीके $S$ तथा $2^{\binom n2 - \binom a2}$अन्य किनारों को रंग देने के तरीके। इससे गुणा करें$\binom na$ और हमें मिलता है $$ \binom na 2^{\binom n2 - \binom a2 + 1} $$ एक ऊपरी सीमा के रूप में।
अगर हम चाहते हैं कि यह इससे कम हो $2^{\binom n2}$, तो हम चाहते हैं $2\binom na < 2^{\binom a2}$। हमें कठिन प्रयास करने की आवश्यकता नहीं है: धारणा$a \ge 2$,
- $2\binom na < \frac{2n^a}{a!} \le n^a$।
- $2^{\binom a2} = (\sqrt2^{a-1})^a$।
तो अगर $n \le \sqrt2^{a-1}$, फिर $n^a \le 2^{\binom a2}$जिससे हम निष्कर्ष निकालते हैं $2 \binom na < 2^{\binom a2}$; इसलिए एक रंग मौजूद है जो किसी के लिए भी खराब नहीं है$S$।