Algebra, Combinatorics, Measure

Organizers: Gabor Elek, Łukasz Grabowski
Contact:

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, l2-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.

next seminar
The next seminar is today
Seminar called off

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).

2016-17

Apr 24 13:00 B35
Viktor Zamaraev (Warwick University) - On factorial classes of bipartite graphs
May 01
Early May bank holiday
May 08 13:00 B35
Ben Barber (Bristol) - Isoperimetry in integer lattices
May 15
Seminar called off
May 22 13:00 B35
Aditi Kar (Royal Holloway) - Ping Pong on CAT(0) cube complexes
May 29
Spring bank holiday
Jun 05 13:00 B35
François Le Maître (Université Paris Diderot) - L1 full groups
Jun 12 13:00 B35
Agnes Backhausz (Eötvös Loránd University) - On the eigenvectors of random regular graphs
Jun 19 12:45 B35
Jun 26
Seminar called off

Abstracts

Apr 24 13:00 B35
Viktor Zamaraev (Warwick University) - On factorial classes of bipartite graphs

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.

May 08 13:00 B35
Ben Barber (Bristol) - Isoperimetry in integer lattices

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.

May 22 13:00 B35
Aditi Kar (Royal Holloway) - Ping Pong on CAT(0) cube complexes

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.

Jun 05 13:00 B35
François Le Maître (Université Paris Diderot) - L1 full groups

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.

Jun 12 13:00 B35
Agnes Backhausz (Eötvös Loránd University) - On the eigenvectors of random regular graphs

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.

Jun 19 12:45 B35
Oleg Pikhurko (Warwick University) - The minimum number of triangles in graphs of given order and size

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.