Automata, Semigroups and Symbolic Dynamics
Remembering Avraham Trakhtman
|
|
ABSTRACTS
Grigory Mashevitzky
In his last years Avraham Trakhtman worked in Automata Theory. In my talk I'll give a review on his earlier results in Semigroup Theory. He obtained significant results in different branches of Semigroup Theory and I'll speak on a few of them: the existence of an infinite irreducuble basis of identities; the existence of covers in the lattice of semigroup varieties; identities of small semigroups; semigroups whose subsemigroups all belong to a certain variety. All these topics are connected to each other and, for example, his very interesting problem about the interreletions of the existence of an irreducible basis of identities and the existence of covers for a variety published by Avraham in 1978 to the best of my knowledge is open till now.
Mikhail Volkov
Over the years, many of my papers were closely related
to some of Trakhtman’s papers, and this concerns both semigroup
papers and papers on automata theory. I present an analysis of
such connections, with an emphasis on the impact of Trakhtman’s
research in these areas.
Nathan Keller
In this talk we describe two seemingly unrelated results on the symmetric group Sn.
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>n0(t), the maximal size of a t-intersecting subfamily of Sn 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 Sn whose square A2 contains (="covers") the alternating group An. We show that if A is a union of conjugacy classes of density at least exp(-n2/5-ε) then An \subset A2. 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 Lifshitz, Minzer, and Sheinfeld.
Benjamin Steinberg
We use topological means to compute the global dimension of the complex algebra of the monoid of affine transformations of a vector space over a finite field. A key role is played by the matroid of affine subspaces and the action of the affine general linear group on the corresponding order complex, which is a wedge of spheres.
|