Activities This Week

Random processes have played a central role in combinatorics since Paul Erdos’s “probabilistic revolution” eight decades ago. Traditionally, such processes are used to define a probability space in which an object with desired properties is sampled with positive probability, thereby proving its existence. Drawing on three case studies, I will explore how recent advances extend the utility of random processes beyond existence proofs, enabling us also to count and understand the structure of combinatorial objects.

To begin, I will discuss the construction of high-girth Steiner triple systems, which proved a 1973 conjecture of Erdos. This builds on Keevash’s breakthrough proof — combining probability and algebra — of the existence of designs, but uses random processes to overcome limitations of the algebraic component.

Next, I will consider triangle-free graphs. The basic problem is to estimate the number of triangle-free graphs with a specified number of vertices and edges. This prototypical forbidden substructure problem motivated the development of key tools in probabilistic combinatorics, essentially solving the problem for graphs that are somewhat sparse or somewhat dense. However, the intermediate-density regime, in which triangle-free graphs undergo a phase transition, remained elusive. I will present the first formula for the number of triangle-free graphs in this regime. Crucial to the proof is a random process to sample these graphs.

Finally, I will discuss the $n$-queens problem: In how many ways can $n$ queens be placed on an $n \times n$ chessboard so that no two threaten each other? It turns out that random processes can be used to reduce the combinatorial question to an infinite-dimensional convex optimization problem. This also sheds light on the typical structure of $n$-queens configurations.

בשנת 1706, ג’ון מייצ’ין (Machin) הגיע לנוסחה המבטאת את פאי כסכום של שני גורמי ארקטנגנס, ובעזרתה הגיע לקירוב של פאי הנכון ל100 ספרות עשרוניות. בשנים שחלפו, מתמטיקאים מצאו נוסחאות דומות עם יותר גורמים. נוסחאות אלו נקראות נוסחאות כמו-מייצ’ין (Machin-like). באשנב זה נראה כיצד מגיעים לנוסחאות אלו, בודקים את יעילותם, וכמה נוסחאות כאלו יש בכלל. אשנב זה מבוסס על פרויקט שעבדתי עליו במשך הקיץ,

I’ll talk about a class of functions called Log-Noetherian that I recently introduced. They are holomorphic solutions of “regular-singular” systems of non-linear algebraic differential equations. They extend an earlier notion of “Noetherian functions” considered by Khovanskii and Tougeron, but enjoy better algebraic properties.

The main theorem is that these functions generate an “effectively o-minimal structure”, meaning that one can give effective upper bounds for the complexity of sets defined by (first-order) formulas involving them - something akin to a Bezout theorem. In particular this proves Khovanskii’s conjecture from the early eighties on counting solutions for systems of Noetherian equations. This o-minimal structure contains the universal covering maps of Shimura varieties and period maps for variations of Hodge structures, and essentially shows that all applications of o-minimality to these areas are effective. The theory is (currently) archimedean but I’ll try to stress why I think a p-adic analog should be pursued.