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

I will demonstrate how careful analysis of group relations yields unexpected constructions, addressing several central questions in group theory. These include a question by Elliott, Jonusas, Mesyan, Mitchell, Morayne, and Peresse regarding Zariski topologies on groups and semigroups, a series of questions by Amir, Blachar, Gerasimova, and Kozma concerning algebraic group laws, and a longstanding question by Wiegold on invariably generated groups.

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). באשנב זה נראה כיצד מגיעים לנוסחאות אלו, בודקים את יעילותם, וכמה נוסחאות כאלו יש בכלל. אשנב זה מבוסס על פרויקט שעבדתי עליו במשך הקיץ,