किन्हीं तीन सेटों में खाली प्रतिच्छेदन है - कितने सेट हो सकते हैं?

मान लीजिए $\mathcal F$ $X=\{1,2,\ldots, N\}$ के गैर-रिक्त उपसमुच्चय का एक परिवार है, जैसे कि किन्हीं तीन अलग $A,B,C \in \mathcal F$ के लिए हमारे पास है $A \cap B \cap C = \varnothing$. $\mathcal F$ की अधिकतम कार्डिनैलिटी क्या है?

मुझे संदेह है कि उत्तर लगभग $3N/2$ है और इसे उदाहरण के लिए $$\mathcal F = \{\{1\} से प्राप्त किया जा सकता है। \{2\},\ldots , \{N\}, \{1,2\}, \{3,4\},\ldots, \{N-1,N\}\} \text{ सम मानते हुए } N.$$

लेकिन अभी तक मैं केवल $2N-1$ की ऊपरी सीमा ही सिद्ध कर सका हूँ। यह उस फ़ंक्शन पर विचार करके प्राप्त किया जाता है जो प्रत्येक सेट को $\mathcal F$ में उसके न्यूनतम तत्व पर ले जाता है। $1,2,\ldots, N-1$ से अधिक के फाइबर में प्रत्येक में अधिकतम दो सेट हो सकते हैं, अन्यथा हमें एक साझा तत्व के साथ तीन सेट मिलेंगे, जिसकी अनुमति नहीं है। $N$ से अधिक के फ़ाइबर में अधिकतम सेट $\{N\}$ हो सकता है। इसलिए हमें बाउंड $2(N-1)+1=2N-1$ मिलता है।

हां, $\newcommand\F{\mathcal F}\F$ का अधिकतम संभव आकार $\lfloor 3n है /2\rfloor$.

इस सेट परिवार के लिए $n\times |\F|$ घटना मैट्रिक्स पर विचार करें। प्रत्येक पंक्ति $\{1,\dots,n\}$ में एक संख्या से मेल खाती है, और प्रत्येक कॉलम $\F$ में एक उपसमुच्चय से मेल खाती है। यदि उपसमुच्चय में वह संख्या है तो प्रविष्टि $1$ है, और अन्यथा $0$ है।

आइए इस मैट्रिक्स में इकाइयों की संख्या को दो तरीकों से गिनें। प्रत्येक $k\in \{1,\dots,n\}$ के लिए, मान लीजिए कि $f_k$ कार्डिनैलिटी $k$ के साथ $\F$ में उपसमुच्चय की संख्या है। एक ओर, मैट्रिक्स में बिल्कुल $f_1+2f_2+3f_3+\dots+nf_n$ हैं, जिनकी गणना कॉलम के आधार पर की जाती है। दूसरी ओर, शर्त यह है कि $A\cap B\cap C=0$ का अर्थ है कि प्रत्येक पंक्ति में अधिकतम दो हैं, इसलिए कुल मिलाकर अधिकतम $2n$ हैं। ये साबित होता है $$ f_1+2f_2+\dots+nf_n\le 2n $$ इस प्रकार निष्कर्ष निकालें: $$ \शुरू करें{संरेखित करें} |\F| &=f_1+f_2+\dots+f_n \\&= \frac12f_1+ \frac12(f_1+2f_2+2f_3+\dots+2f_n) \\&\le \frac12f_1+\frac12(f_1+2f_2+\color{blue}3f_3+\dots+\color{blue}nf_n) \\&\le \frac12\cdot n+\frac12\cdot 2n \अंत{संरेखित करें} $$ यह असमानता, इस तथ्य के साथ मिलकर कि $|\F|$ एक पूर्णांक है, इसका अर्थ है $|\F|\le \lfloor 3n/2\rfloor$. आपके पोस्ट में निर्माण उपलब्धि हासिल करता है