Mar 25
|
Recovering tree models via spectral graph theory
|
Yariv Aisenbud (TAU)
|
Modeling data by latent tree models is a powerful approach in multiple applications. A canonical example of this setting is the “tree of life”, where the evolutionary history of a set of organisms is inferred by their DNA. Generally, in latent tree models, the main task is to infer the structure of the tree, given only observations of its terminal nodes. While inferring a tree structure is a common task, in many applications, a robust algorithm for the recovery of large trees is still missing.
In this talk, we will see a new method for the recovery of latent tree models, which is based on spectral graph theory. We show that the hidden tree structure is strongly related to the spectral properties of a graph, defined over the terminal nodes of the tree. Finally, we see that while in terms of accuracy the method performs similarly to state-of-the-art methods, it is significantly more computationally efficient.
|
Apr 22
|
Demushkin groups of infinite rank in Galois theory
|
Tamar Bar-On (BGU)
|
One of the most interesting open questions in Galois theory these days is: Which profinite groups can be realized as absolute Galois groups of fields?
Restricting our focus to the one-prime case, we begin with a simpler question: which pro-p groups can be realized as maximal pro-p Galois groups of fields?
For the finitely generated case over fields that contain a primitive root of unity of order p, we have a comprehensive conjecture, known as the Elementary Type Conjecture by Ido Efrat, which claims that every finitely generated pro-p group which can be realized as a maximal pro-p Galois group of a field containing a primitive root of unity of order p, can be constructed from free pro-p groups and finitely generated Demushkin groups, using free pro-p products and a certain semi-direct product.
The main objective of the presented work is to investigate the class of infinitely-ranked pro-p groups which can be realized as maximal pro-p Galois groups. Inspired by the Elementary Type Conjecture, we start our research with 2 main directions:
1. Generalizing the definition of Demushkin groups to arbitrary rank and studying their realization as absolute/ maximal pro-p Galois groups.
2. Investigating the possible realization of a free (pro-p) product of infinitely many absolute Galois groups.
In this talk we focus mainly on the second direction. In particular, we give a necessary and sufficient condition for a restricted free product of countably many Demushkin groups of infinite countable rank, to be realized as an absolute Galois group.
|
Apr 29
|
TBA
|
Department meeting
|
|
May 20
|
Phenomenology of noncommutative polynomials
|
Eli Shamovich (BGU)
|
Given a commuting $d$-tuple of matrices or operators, we immediately get a homomorphism from the polynomial ring in $d$ variables. An extension of such a homomorphism is called a “functional calculus.” On the other hand, viewing a commutative algebra as functions on its character space is a fruitful approach that goes back at least to Gelfand. However, matrices and polynomials tend not to commute. Hence, the natural object of study in this case is the free algebra $\mathbb{C}\langle z_1,\ldots, z_d \rangle$. By the first analogy, we will call the elements of the free algebra noncommutative polynomials. The second analogy tells us to treat them as functions. The natural analog of the affine space is the collection of all $d$-tuples of matrices of all sizes. We want to understand algebraic relations between noncommutative polynomials through their values. For example, given $f,g \in \mathbb{C}\langle z_1,\ldots, z_d \rangle$, what can we say about $f$ and $g$, if for every $d$-tuples of matrices $X = (X_1,\ldots,X_d)$, $f(X)$ has the same spectrum as $g(X)$. What if $f(X)$ is always similar to $g(X)$? We will answer these questions and others.
|
May 27
|
Intersection theorems and improved covering results for the symmetric group, via hypercontractivity
|
Nathan Keller (BIU)
|
In this talk we describe two seemingly unrelated results on the symmetric group $S_n$.
A family F of permutations is called t-intersecting if any two permutations in F agree on at least t values. In 1977, Deza and Frankl conjectured that for all $n>n_0(t)$, the maximal size of a t-intersecting subfamily of $S_n$ is $(n-t)!$. Ellis, Friedgut and Pilpel (JAMS, 2011) proved the conjecture for all $n>exp(exp(t))$ and conjectured that it holds for all $n>2t$. We prove that the conjecture holds for all $n>ct$ for some constant c.
A well-known problem asks for characterizing subsets A of $S_n$ whose square $A^2$ contains (=”covers”) the alternating group $A_n$. We show that if A is a union of conjugacy classes of density
at least $exp(-n^{2/5-\epsilon})$ then $A_n \subset A^2$. This improves a seminal result of Larsen and Shalev (Inventiones Math., 2008) who obtained the same with 1/4 in the double exponent.
The common feature of the two results is the main tool we use in the proofs, which is (perhaps surprisingly) analytic - hypercontractive inequalities for global functions. We shall discuss the new tool (introduced recently by Keevash, Lifshitz, Long and Minzer, JAMS 2024) and other directions in which it may be applied.
Based on joint works with Noam Lifshitz, Dor Minzer, and Ohad Sheinfeld
|
Jun 10
|
Sharp cutoff for walks on graphs and groups
|
Ori Parzanchevski (HUJI)
|
In the `80 Diaconis and others have observed that some naturally occurring Markov chains exhibit a cutoff phenomenon: the distance from the stationary distribution drops from almost maximal to almost zero over a short period of time. It is conjectured that all transitive expander graphs exhibit this phenomenon, but so far very few examples are known. I will survey and explain some results on cutoff for walks on Ramanujan graphs and complexes, and their relation to expansion in groups.
|