גישה חדשה בפתרון בעיות בתורת הגרפים

פרופ' נתן קלר מהמחלקה למתמטיקה באוניברסיטת בר-אילן, זכה יחד עם ד"ר נועם ליפשיץ בפרס דלברט ריי פולקרסון (Delbert Ray Fulkerson Prize) של החברה המתמטית האמריקאית AMS לשנת 2024 על מאמרם המשותף The Junta Method for Hypergraphs and the Erdős-Chvátal Simplex Conjecture.

פרס פולקרסון הוא מהיוקרתיים ביותר בתחום המתמטיקה הדיסקרטית (מתמטיקה בדידה), העוסק בתורת הקבוצות הסופיות, בקומבינטוריקה ובתורת הגרפים. הפרס מוענק אחת לשלוש שנים, לכל היותר לשלושה מאמרים פורצי דרך. המאמר המדובר נכתב כשד"ר ליפשיץ, שמכהן היום כמרצה בכיר באוניברסיטה העברית, עבד כחוקר תחת הנחייתו של פרופ' קלר באוניברסיטת בר-אילן. בעבר זכו בפרס רק שני ישראלים (פרופ' גיל קלעי מהאוניברסיטה העברית ופרופ' מריה צ'ודנובסקי מפרינסטון). ועדת הפרס ציינה שמחברי המאמר מציגים גישה חדשה לפתרון "בעיות מסוג טוראן" בתחום תורת הגרפים הקרויות על שם המתמטיקאי ההונגרי-יהודי פול טוראן, ושבאמצעותה הם פתרו מספר בעיות שהיו פתוחות במשך למעלה מ-30 שנה.

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

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

לתוכניות הלימוד במחלקה למתמטיקה