הסמינר מתכנס בימי שלישי, בשעות 14:30-15:30, באולם -101

השבוע


Zur Luria (ETH )

Latin squares, designs, and high-dimensional expanders

Expander graphs have many wonderful properties: They are highly connected, pseudorandom, and random walks on expanders are rapidly mixing. The study of these objects has been immensely useful and fruitful for both applicative and theoretical fields. Recently, there has been a lot of interest in the study of generalizations of expander graphs to d-uniform hypergraphs. Several competing definitions have been proposed, each corresponding to a different property of expander graphs. Understanding these definitions, their applications, and the relations between them is the goal of this emerging field.

In a joint work with Alexander Lubotzky and Ron Rosenthal, we proved the existence of bounded degree coboundary expanders, a concept that generalizes high connectivity in graphs. Our work makes use of Peter Keevash’s recent construction of designs: We show that the union of a constant number of designs constructed according to Keevash’s random construction is with high probability a good coboundary expander.

The expander mixing lemma quantifies the extent to which an expander graph is pseudorandom. In a joint work with Nati Linial, we asked if there exist pseudorandom designs. In particular, we conjectured that a typical Latin square design is pseudorandom. This has implications for the Algebraic concept of quasirandom groups, introduced by Gowers. Our conjecture implies that there exist maximally quasirandom quasigroups, and we prove this fact.

There remain many promising directions for further research.


מפגשים בסמסטר סתיו 2016

המפגשים הבאים

תאריך
כותרת
מרצה
תקציר
24 בינו Latin squares, designs, and high-dimensional expanders Zur Luria (ETH )

Expander graphs have many wonderful properties: They are highly connected, pseudorandom, and random walks on expanders are rapidly mixing. The study of these objects has been immensely useful and fruitful for both applicative and theoretical fields. Recently, there has been a lot of interest in the study of generalizations of expander graphs to d-uniform hypergraphs. Several competing definitions have been proposed, each corresponding to a different property of expander graphs. Understanding these definitions, their applications, and the relations between them is the goal of this emerging field.

In a joint work with Alexander Lubotzky and Ron Rosenthal, we proved the existence of bounded degree coboundary expanders, a concept that generalizes high connectivity in graphs. Our work makes use of Peter Keevash’s recent construction of designs: We show that the union of a constant number of designs constructed according to Keevash’s random construction is with high probability a good coboundary expander.

The expander mixing lemma quantifies the extent to which an expander graph is pseudorandom. In a joint work with Nati Linial, we asked if there exist pseudorandom designs. In particular, we conjectured that a typical Latin square design is pseudorandom. This has implications for the Algebraic concept of quasirandom groups, introduced by Gowers. Our conjecture implies that there exist maximally quasirandom quasigroups, and we prove this fact.

There remain many promising directions for further research.

המפגשים הקודמים

תאריך
כותרת
מרצה
תקציר
8 בנוב VISUALIZING AND SOME NEW DUALITIES Alfred Inselberg (San Diego Supercomputing Center and Tel Aviv University)
15 בנוב Combinatorial Hodge theory Karim Adiprasito (Hebrew University of Jerusalem)

I will discuss how Hodge theory, and positivity phenomena from algebraic geometry in general, can be used to resolve fundamental conjectures in combinatorics, including Rotas conjecture for log-concavity of Whitney numbers and beyond. I will also discuss how combinatorics can in turn be used to explain and prove such phenomena, such as the Hodge-Riemann relations for matroids.

22 בנוב Could the Lorenz flow be hyperbolic? Tali Pinsky (TIFR, India)

I will describe the theory of hyperbolic flows on three manifolds, and then describe a new approach to chaotic flows using knot theory, allowing for topological analysis of singular flows. I’ll use this to show that, surprisingly, the famous Lorenz flow on R^3 can be related to the geodesic flow on the modular surface. When changing the parameters, we also find a new type of topological phases in the Lorenz system. This will be an introductory talk.

29 בנוב Random Matrices, Graphs on Surfaces and Mapping Class Group Doron Puder (Tel Aviv University)

This is joint work with Michael Magee. Since the 1970’s, Physicists and Mathematicians who study random matrices in the standard models of GUE or GOE, are aware of intriguing connections between integrals of such random matrices and the enumeration of graphs on surfaces. We establish a new aspect of this theory: for random matrices sampled from the group U(n) of Unitary matrices. The group structure of these matrices allows us to go further and find surprising algebraic quantities hidden in the values of these integrals. The talk will be aimed at graduate students, and all notions will be explained.

6 בדצמ First-order logic on the free group and geometry Chloé Perin (Hebrew University of Jerusalem)

We will give an overview of questions one might ask about the first-order theory of free groups and related groups: how much information can first-order formulas convey about these groups or their elements, what algebraic interpretation can be given for model theoretic notions such as forking independence, etc. It turns out that techniques from geometric group theory are very useful to tackle such problems. Some of these questions have been answered, others are still open - our aim is to give a feel for the techniques and directions of this field. We will assume no special knowledge of model theory.

13 בדצמ A geometric semantics of algebraic quantum mechanics Boris Zilber (Oxford)

We approach the formalism of quantum mechanics from the logician point of view and treat the canonical commutation relations and the conventional calculus based on it as an algebraic syntax of quantum mechanics. We then aim to establish a geometric semantics of this syntax. This leads us to a geometric model, the space of states with the action of time evolution operators, which is a limit of finite models. The finitary nature of the space allows us to give a precise meaning and calculate various classical quantum mechanical quantities. This talk is based on my paper “The semantics of the canonical commutation relation” arxiv.org/abs/1604.07745

20 בדצמ Geometric Incidences and the Polynomial Method Adam Sheffer (California Institute of Technology (Caltech))

While the topic of geometric incidences has existed for several decades, in recent years it has been experiencing a renaissance due to the introduction of new polynomial methods. This progress involves a variety of new results and techniques, and also interactions with fields such as algebraic geometry and harmonic analysis.

A simple example of an incidences problem: Given a set of n points and set of n lines, both in R^2, what is the maximum number of point-line pairs such that the point is on the line. Studying incidence problems often involves the uncovering of hidden structure and symmetries.

In this talk we introduce and survey the topic of geometric incidences, focusing on the recent polynomial techniques and results (some by the speaker). We will see how various algebraic and analysis tools can be used to solve such combinatorial problems.

27 בדצמ Gaussian complex zeros and eigenvalues - Rare events and the emergence of the ‘forbidden’ region Alon Nishry (University of Michigan)

The zeros of the Gaussian Entire Function and the infinite Ginibre ensemble are two natural examples of two-dimensional random point configurations whose distribution is invariant under rigid motions of the plane. Due to non-trivial correlations, the features of these two processes are quite different from the ones of the homogeneous Poisson point process. For this reason, these processes are of interest to analysts, probabilists, and mathematical physicists.

I will describe some of the things that we know about the structure and the statistics of these processes. Of particular interest are rare events, when the number of points in a certain domain is very different from its ‘typical’ value. An important example is the ‘hole’ event, when there are no zeros in a large disk. Conditioned on the hole event, the zeros exhibit a large forbidden region, outside the hole, where there are very few zeros asymptotically. This is a new phenomenon, which is in stark contrast to the corresponding result known to hold for the Ginibre ensemble.

Based on a joint work with S. Ghosh (arXiv:1609.00084).

10 בינו Universality in numerical computations with random data. Case studies Percy Deift (NYU)

This is joint work with Govind Menon, Sheehan Olver and Thomas Trogdon. The speaker will present evidence for universality in numerical computations with random data. Given a (possibly stochastic) numerical algorithm

with random input data, the time (or number of iterations) to convergence (within a given tolerance) is a random variable, called the halting time. Two-component universality is observed for the fluctuations of the halting time, i.e., the

histogram for the halting times, centered by the sample average and scaled by the sample variance, collapses to a universal curve, independent of the input data distribution, as the dimension increases. Thus, up to two components,

the sample average and the sample variance, the statistics for the halting time are universally prescribed. The case studies include six standard numerical algorithms, as well as a model of neural computation and decision making.

17 בינו New directions in Ramanujan graphs and complexes Ori Parzanchevski (Hebrew University of Jerusalem)

A Ramanujan graph is a finite graph which behaves, in terms of expansion, like its universal cover (which is an infinite tree). In recent years a parallel theory has emerged for simplicial complexes of higher dimension, where the role of the tree is taken by Bruhat-Tits buildings. I will recall briefly the story of Ramanujan graphs, and then explain what are “Ramanujan complexes”, and survey some of the new results regarding their construction and their properties.

סמינר מאורגן על-ידי פרופ' תם מאירוביץ