השערת Frankl על משפחות סגורות לאיחוד

 
הבעיה הקומבינטורית עליה אכתוב כאן היא קלה לניסוח והבנה, אך ככל הנראה קשה מאוד לפתרון. היא ידועה בשם
“Union-closed conjecture”, ונוסחה ע”י המתמטיקאי Peter Frankl בשנת 1979 (אם כי, לפי עדויות מסוימות, היתה ידועה עוד קודם).

אנחנו מתבוננים בקבוצה בת \({n}\) איברים, למשל קבוצת המספרים \({\{1,2,\ldots,n\}}\) שתסומן להלן ע”י \({[n]}\). תהי \({\mathcal{A} = \{A_1, A_2, \ldots, A_m\}}\) משפחה של \({m}\) תת-קבוצות של \({[n]}\). האיחוד \({A \cup B}\) של שתי קבוצות הוא הקבוצה המכילה אותם איברים שנמצאים לפחות באחת משתי הקבוצות \({A,B}\).אנחנו אומרים שהמשפחה \({\mathcal{A}}\) סגורה לאיחוד אם לכל שתי קבוצות בה, גם האיחוד שלהן נמצא בה. הנה מספר דוגמאות ל- \({\mathcal{A}}\) כזאת:

  • 1. \({\mathcal{A} = \mathcal{P} ([n])}\), כלומר משפחת כל התת-קבוצות של \({[n]}\).
  • 2. \({\mathcal{A}}\) כלשהי הסגורה כלפי מעלה (כלומר, מקיימת \({A \in \mathcal{A}, \, A \subseteq B \,\, \Rightarrow \,\, B \in \mathcal{A}}\)).
  • 3. הדוגמה הבאה עבור \({\mathcal{A} = \{\emptyset , \{1\}, \{2\}, \{1,2\}, \{1,2,3\}\}\quad : \, n=3, m=5}\)
  • השערת Frankl: תהי \({\mathcal{A}}\) משפחה סגורה לאיחוד, שאיננה המשפחה הטריביאלית \({\mathcal{A} = \{ \emptyset \}}\). אזי קיים איבר שנמצא לפחות במחצית מהקבוצות ב- \({\mathcal{A}}\).

    להשערה זו לא ידועה הוכחה, אם כי היא נבדקה ונמצאה נכונה בדוגמאות רבות. למשל, נעבור על שלוש הדוגמאות דלעיל:

  • 1. \({\mathcal{A} = \mathcal{P}([n])}\) \({-}\) כאן כל איבר נמצא בדיוק במחצית מהקבוצות.
  • 2. \({\mathcal{A}}\) סגורה כלפי מעלה \({-}\) לכל איבר \({i \in [n]}\), כנגד כל קבוצה \({A \in \mathcal{A}}\) שאינה מכילה אותו, ישנה הקבוצה \({A \cup \{i\} \in \mathcal{A}}\) שמכילה אותו, ולכן כל איבר נמצא לפחות במחצית מהקבוצות ב- \({\mathcal{A}}\).
  • 3. \({\mathcal{A} = \{ \emptyset , \{1\}, \{2\}, \{1,2\}, \{1,2,3\}\}}\) \({-}\) כאן כבר לא כל איבר מתאים: האיבר \({3}\) נמצא רק בקבוצה אחת. אבל האיבר \({1}\) (וכמוהו גם \({2}\)) נמצא ב- \({3}\) מבין \({5}\) הקבוצות ב- \({\mathcal{A}}\).
  • נכניס את הסימון \({\mathcal{A}_i}\) עבור אוסף הקבוצות ב- \({\mathcal{A}}\) שמכילות את האיבר \({i}\). כמו-כן, \({|A|}\) יסמן את מספר איברי \({A}\). קל לבדוק, ע”י ספירה בשתי דרכים, כי

    \(\displaystyle \sum_{i=1}^n |\mathcal{A}_i| = \sum_{A \in \mathcal{A}} |A|\)

    אילו היינו יודעים שהסכום הנ”ל הוא לפחות \({\frac{mn}{2}}\), אז הגודל הממוצע של \({\mathcal{A}_i}\) היה לפחות \({\frac{m}{2}}\), והיינו יכולים להסיק שקיים \({i}\) כנדרש בהשערה. לפיכך, די להראות כי הגודל הממוצע של \({A \in \mathcal{A}}\) הוא לפחות \({\frac{n}{2}}\). בהסתכלות שטחית, נראה שזה אמור להיות נכון, כי הסגירות לאיחוד מחייבת שכנגד קבוצות קטנות ב- \({\mathcal{A}}\) יהיו גם קבוצות גדולות. אבל זה לא תמיד נכון: למשל, בדוגמה 3 הגודל הממוצע של הקבוצות ב- \({\mathcal{A}}\) הוא \({\frac{7}{5}}\), שקטן מ- \({\frac{3}{2}}\).

    לפיכך, לא ניתן באופן כללי לחזק את השערת Frankl כך שבממוצע איבר יימצא לפחות במחצית מהקבוצות ב- \({\mathcal{A}}\). יחד עם זאת, Balla, Bollobás & Eccles הוכיחו כי גרסת הממוצע נכונה במקרה ש- \({m \ge \frac{2}{3} \cdot 2^n}\), ובכך הם הוכיחו שהשערת Frankl מתקיימת במקרה זה. ראוי לשים לב, שבדוגמה 3 לעיל שבה גרסת הממוצע נכשלת, מספר הקבוצות \({m=5}\) הוא רק מעט יותר נמוך מ- \({\frac{2}{3} \cdot 2^n = \frac{16}{3}}\). ניתן להכליל דוגמה זו, כך שתראה שהדרישה שהמשפחה תכיל לפחות שני שלישים מכל התת-קבוצות אכן חיונית לקיום גרסת הממוצע.

    כדי לקבל תחושה לגבי נכונות ההשערה, טבעי לבדוק תחילה את המקרים שבהם \({\mathcal{A}}\) מכילה קבוצה בעלת מעט איברים. אם \({\{i\} \in \mathcal{A}}\) אז קל לראות (באותה דרך כמו בדוגמה 2 לעיל) ש- \({i}\) נמצא לפחות במחצית מהקבוצות. אם \({\{i,j\} \in \mathcal{A}}\) אפשר להראות שלפחות אחד מבין \({i,j}\) נמצא לפחות במחצית מהקבוצות. אבל גישה זאת נכשלת עבור \({\{i,j,k\} \in \mathcal{A}}\): יש דוגמאות כאלו, שבהן אף אחד מבין \({i,j,k}\) איננו נמצא לפחות במחצית מהקבוצות. למרות זאת, ע”י שימוש בקבוצות קטנות וניתוח של מקרים אפשר לבדוק את קיום השערת Frankl עבור ערכים קטנים למדי של \({n}\) ושל \({m}\). נכון למועד הכתיבה, התוצאות הטובות ביותר מסוג זה מאמתות את ההשערה כאשר מספר האיברים \({n \le 12}\) או כאשר מספר הקבוצות \({m \le 50}\). בכיוון המחקר הזה היו שיפורים מעת לעת, וייתכן שעוד יהיו, אבל ספק רב אם הוא יוביל להוכחת ההשערה.

    מה ידוע עבור \({n}\) ו- \({m}\) גדולים? ידועים שלושה חסמים, שטיבם היחסי תלוי בצפיפות של המשפחה (כלומר, כמה גדול הוא מספר הקבוצות \({m}\) ביחס למספר האיברים \({n}\)):

    • א. (Wójcik) קיים איבר שנמצא לפחות ב- \({\frac{24}{5\log_2m} \cdot \frac{m}{2}}\) קבוצות ב- \({\mathcal{A}}\).
    • ב. (Balla) קיים איבר שנמצא לפחות ב- \({\sqrt{\frac{\log_2n}{n}} \cdot \frac{m}{2}}\) קבוצות ב- \({\mathcal{A}}\).
    • ג. (Reimer) קיים איבר שנמצא לפחות ב- \({\frac{\log_2m}{n} \cdot \frac{m}{2}}\) קבוצות ב- \({\mathcal{A}}\).

    בכל החסמים האלה, הגורם הכופל את \({\frac{m}{2}}\) עלול להיות קטן. עד היום, לא ידוע אף חסם מהצורה \({c \cdot m}\), כאשר \({c>0}\) הוא קבוע כלשהו. הוכחה שתמיד קיים איבר שנמצא לפחות ב- \({1 \%}\) מהקבוצות ב- \({\mathcal{A}}\) תיחשב לפריצת דרך משמעותית.

    ביבליוגרפיה:

    • I. Balla, Minimum densities of union-closed families, arXiv:1106.0369v1[math.CO], 2011.
    • I. Balla, B. Bollobás & T. Eccles, Union-closed families of sets, J. Combin. Theory (Ser. A) 120 (2013), 531-544.
    • D. Reimer, An average set size theorem, Comb. Probab. Comput. 12 (2003), 89-93.
    • P. Wójcik, Union-closed families of sets, Discrete Math. 199 (1999), 173-182.

    2 תגובות על השערת Frankl על משפחות סגורות לאיחוד

    • מאת אסף‏:

      מעניין. ומה בנוגע למקרה האינסופי? האם במשפחה אינסופית סגורה לאיחוד יש לפחות איבר אחד כך שעוצמת הקבוצות שמכילות אותו גדולה שווה מעוצמת הקבוצות שאינן מכילות אותו?

    • מאת רון‏:

      במקרה האינסופי זה לא נכון באופן כללי. דוגמה נגדית היא משפחת התת-קבוצות של המספרים הטבעיים מהצורה: כל המספרים הגדולים ממספר נתון.