C3

Spectral methods offer a tractable, global framework for clustering in graphs via eigenvector computations on graph matrices. Hypergraph data, in which entities interact on edges of arbitrary size, poses challenges for matrix representations and therefore for spectral clustering. We study spectral clustering for arbitrary hypergraphs based on the hypergraph nonbacktracking operator. After reviewing the definition of this operator and its basic properties, we prove a theorem of Ihara-Bass type which allows eigenpair computations to take place on a smaller matrix, often enabling faster computation. We then propose an alternating algorithm for inference in a hypergraph stochastic blockmodel via linearized belief-propagation which involves a spectral clustering step, again using nonbacktracking operators. We provide proofs related to this algorithm that both formalize and extend several previous results. We pose several conjectures about the limits of spectral methods and detectability in hypergraph stochastic blockmodels in general, supporting these with in-expectation analysis of the eigeinpairs of our studied operators. We perform experiments with real and synthetic data that demonstrate the benefits of hypergraph methods over graph-based ones when interactions of different sizes carry different information about cluster structure.

Joint work with Nicole Eikmeier (Grinnell) and Jamie Haddock (Harvey Mudd).

Many networks exhibit some community structure. There exists a wide variety of approaches to detect communities in networks, each offering different interpretations and associated algorithms. For large networks, there is the additional requirement of speed. In this context, the so-called label propagation algorithm (LPA) was proposed, which runs in near linear time. In partitions uncovered by LPA, each node is ensured to have most links to its assigned community. We here propose a fast variant of LPA (FLPA) that is based on processing a queue of nodes whose neighbourhood recently changed. We test FLPA exhaustively on benchmark networks and empirical networks, finding that it runs up to 700 times faster than LPA. In partitions found by FLPA, we prove that each node is again guaranteed to have most links to its assigned community. Our results show that FLPA is generally preferable to LPA.

Waldspurger proved maximality and minimality results for certain generalised Springer representations of $\text{Sp}(2n,\mathbb{C})$. We will discuss analogous results for $G = \text{SO}(N,\mathbb{C})$ and sketch their proofs.

Let $C$ be a unipotent class of $G$ and $E$ an irreducible $G$-equivariant local system on $C$. Let $\rho$ be the generalised Springer representation corresponding to $(C,E)$. We call $C$ the support of $\rho$. It is well-known that $\rho$ appears in the top cohomology of a certain variety. Let $\bar\rho$ be the representation obtained by summing the cohomology groups of this variety.

We show that if $C$ is parametrised by an orthogonal partition consisting of only odd parts, then $\bar\rho$ has a unique irreducible subrepresentation $\rho^{\text{max}}$ whose support is maximal among the supports of the irreducible subrepresentations of $\rho^{\text{max}}$. We also show that $\text{sgn}\otimes\rho^{\text{max}}$ is the unique subrepresentation of $\text{sgn}\otimes\bar\rho$ with minimal support. We will also present an algorithm to compute $\rho^{\text{max}}$.

Identifying the hidden organizational principles and relevant structures of complex networks is fundamental to understand their properties. To this end, uncovering the structures involving the prominent nodes in a network is an effective approach. In temporal networks, the simultaneity of connections is crucial for temporally stable structures to arise. In this work, we propose a measure to quantitatively investigate the tendency of well-connected nodes to form simultaneous and stable structures in a temporal network. We refer to this tendency as the temporal rich club phenomenon, characterized by a coefficient defined as the maximal value of the density of links between nodes with a minimal required degree, which remain stable for a certain duration. We illustrate the use of this concept by analysing diverse data sets and their temporal properties, from the role of cohesive structures in relation to processes unfolding on top of the network to the study of specific moments of interest in the evolution of the network.

Article link: https://www.nature.com/articles/s41567-022-01634-8

The aim is introducing the Bieri-Neumann-Strebel invariants and showing some computations. These are geometric invariants of abstract groups that capture information about the finite generation of kernels of abelian quotients.

Free-by-cyclic groups are easy to define – all you need is an automorphism of F_n. Their properties (for example hyperbolicity, or relative hyperbolicity) depend on this defining automorphism, but not always transparently. I will introduce these groups and some of their properties, and connect some to properties of the defining automorphism. I'll then discuss some ideas and techniques we can use to understand their automorphisms, including finding useful actions on trees and relationships with certain subgroups of Out(F_n). (This is joint work with Armando Martino.)

The Gromov boundary of a hyperbolic group is a useful topological invariant, the properties of which can encode all sorts of algebraic information. It has found application to some algorithmic questions, such as finding finite splittings (Dahmani-Groves) and, more recently, computing JSJ-decompositions (Barrett). In this talk we will introduce the boundary of a hyperbolic group. We'll outline how one can approximate the boundary with "large spheres" in the Cayley graph, in order to search for topological features. Finally, we will also discuss how this idea is applied in the aforementioned results. 

In this talk, we describe some recent work on applying tools from category theory in finite model theory, descriptive complexity, constraint satisfaction, and combinatorics.

The motivations for this work come from Computer Science, but there may be something of interest for model theorists and other logicians.

The basic setting involves studying the category of relational structures via a resource-indexed family of adjunctions with some process category - which unfolds relational structures into treelike forms, allowing natural resource parameters to be assigned to these unfoldings.

One basic instance of this scheme allows us to recover, in a purely structural, syntax-free way:

- the Ehrenfeucht-Fraisse game

- the quantifier rank fragments of first-order logic

- the equivalences on structures induced by (i) the quantifier rank fragments, (ii) the restriction to the existential-positive part, and (iii) the extension with counting quantifiers

- the combinatorial parameter of tree-depth (Nesetril and Ossona de Mendez).

Another instance recovers the k-pebble game, the finite-variable fragments, the corresponding equivalences, and the combinatorial parameter of treewidth.

Other instances cover modal, guarded and hybrid fragments, generalized quantifiers, and a wide range of combinatorial parameters.

This whole scheme has been axiomatized in a very general setting, of arboreal categories and arboreal covers.

Beyond this basic level, a landscape is beginning to emerge, in which structural features of the resource categories, adjunctions and comonads are reflected in degrees of logical and computational tractability of the corresponding languages.

Examples include semantic characterisation and preservation theorems, Lovasz-type results on  isomorphisms, and classification of constraint satisfaction problems.

Let $K$ be an algebraically closed field. Given three elements of some Lie algebra over $K$, we say that these elements form an $sl_2$-triple if they generate a subalgebra which is a homomorphic image of $sl_2(K).$ In characteristic 0, the Jacobson-Morozov theorem provides a bijection between the orbits of nilpotent elements of the Lie algebra and the orbits of $sl_2$-triples. In this talk I will discuss the progress made in extending this result to fields of characteristic $p$. In particular, I will focus on the results in classical Lie algebras, which can be found as subsets of $gl_n(K)$.