Algebra, Combinatorics, Measure
Seminar is on Mondays. This year we will have a mix of a reading seminar and a limited number of external speakers.
Topics covered might include, but are by no means limited to, group rings of infinite groups, -invariants, appoximations of infinite groups (for example sofic groups), asymptotic and measured group theory, Borel and measurable combinatorics, graph limits, interactions between algebra/combinatorics and operator algebras, probability, etc.
We have a mailing list: . In order to participate either to sign you up, or send a plain text email to , containing only the two words
subscribe acmseminar in the body (you can leave the subject empty).
This talk is devoted to the problem of characterizing the family of factorial classes of graphs, i.e., hereditary classes in which the number of n-vertex graphs grows as a factorial type function. First, we will discuss background and motivation of the problem. Then we will consider a special case of characterizing the family of factorial classes of bipartite graphs. I will present a recent result showing that the class of P_7-free bipartite graphs is factorial. The result completes the description of monogenic factorial classes of bipartite graphs. The proof is based on a new decomposition scheme of bipartite graphs, which is of independent interest. Finally, we will discuss some open problems.
Based on joint work with Vadim Lozin.
The curve enclosing the greatest area for its length is a circle; this is the first example of an isoperimetric theorem. We can look for similar results whenever we have a notion of size and boundary: for example, in graphs. The general problem is NP-hard, but we can sometimes obtain good results in graphs with a lot of structure. I'll describe a very general result that solves the isoperimetric problem for all lattice like graphs. This is joint work with Joshua Erde.
I will describe my joint work with Sageev on properties of groups acting on CAT(0) cube complexes, like property P_naive and uniform exponential growth. I will not assume any specialist knowledge and explain how one exploits the geometry of CAT(0) cube complexes to extract group theoretic properties.
I will talk about L1 full groups of ergodic measure-preserving transformation, which are measurable analogues of topological full groups of minimal homeomorphisms of the Cantor space. As in the topological world, these groups completely remember the transformation up to flip conjugacy. I will describe basic properties of these Polish groups an then present some results on their topological rank.
We are interested in certain spectral properties of a randomly chosen d-regular graph on n vertices. More precisely, we consider an arbitrary eigenvector of the adjacency matrix, and examine its empirical distribution. Analogous problems have been studied in the case of dense random matrices. To deal with these sparse matrices (bounded degree graphs), we used the theory of graph limits. We could prove that the empirical distibutions of the eigenvectors is close to an appropriate Gaussian distribution (maybe with 0 variance) with high probability if the number of vertices is large enough. In the talk we present this result together with the main tools of the proof. Joint work with Balazs Szegedy.
In 1941 Rademacher (unpublished) asked for the minimum number of triangles in a graph of given order n and size m. This problem was revived by Erdos in the 1950-60s who in particular solved in the case when m=n^2/4+o(n), just above the threshold when at least one triangle is guaranteed. This problem has garnered much attention since then and, in a major breakthrough, was solved asymptotically by Razborov in 2008. I will discuss an exact solution (joint work with Hong Liu and Katherine Staden) for all large graphs whose edge density is bounded away from one.