פעילויות השבוע

אחת מן הבעיות המסתוריות ביותר בתורת הגרפים היא בעיית המותן. בגרף d רגולרי בעל n קדקודים כמה גדול יכול להיות המותן? כלומר אורך המעגל הקצר ביותר. בניגוד לבעיות רבות אחרות בתורת הגרפים בניה מפורשת נותנת תוצאות טובות הרבה יותר מבניה מקרית. הגרפים האמורים נבנו על ידי Lubotzky, Phillips, Sarnak בשנות השמונים והם מצטיינים גם בכך שהם גרפים מרחיבים מאוד טובים. (גרפי רמנוז‘ן).

Let $X$ denote the number of triangles in the random graph $G(n,p)$. The problem of determining the asymptotic of the rate of the lower tail of $X$, that is, the function $f_c(n,p) = log Pr(X ≤ c E[X])$ for a given $c ∈ [0,1)$, has attracted considerable attention of both the combinatorics and the probability communities. We shall present a proof of the fact that whenever $p >> n^{-1/2}$, then $f_c(n,p)$ can be expressed as a solution to a natural combinatorial optimisation problem that generalises Mantel’s / Turan‘s theorem. This is joint work with Gady Kozma.