קומבינטוריקה אדיטיבית

קומבינטוריקה אדיטיבית היא ענף חדש יחסית בקומבינטוריקה, העוסק בקבוצות בעלות מבנה אלגברי מקורב.

התחום החל להתפתח סביב שנת 2000, כאשר טימותי גוארס (Timothy Gowers) מצא הוכחה חדשה למשפט זמרדי.

מבנה אלגברי מקורב

לקבוצה, נאמר של אברים בחבורה אבלית, יש מבנה של חבורה, אם היא סגורה תחת הפעולה: לכל $\ x,y\in S$, הסכום $\ x+y\in S$. במקרה כזה, לאוסף הסכומים $\ S+S$ אותו גודל כמו לקבוצה המקורית. לעומת זאת, אם הקבוצה S "אקראית", חסרת מבנה, מספר הסכומים יהיה קרוב למספר הזוגות של אברים, כלומר לריבוע $\ |S|^{2}$. היחס בין גודלה של קבוצת הסכומים לגודלה של S מודד, אם כך, עד כמה הקבוצה קרובה להיות אלגברית.

משפט גרין-טאו מאפיין קבוצות בעלות מבנה אלגברי מקורב, ככאלו שאינן רחוקות מלהיות אלגבריות בעצמן: אם S קבוצת וקטורים במרחב וקטורי מעל השדה הסופי $\ \mathbb {F} _{2}$ ו- $\ |S+S|\leq k|S|$, אז $\ |\operatorname {span} (S)|\leq 2^{2k(1+o(1))}|S|$.