Random matrix theory is a quickly evolving area of probability theory, which has interesting connections to other fields of mathematics and physics as well. In this work we consider non-symmetric random matrices with independent, zero mean, plus-minus $n^{-1/2}$ entries. It is well known that the eigenvalues of such a matrix are distributed approximately uniformly on the unit disk of the complex plane; however, less is known about the eigenvectors. In the talk we present a result stating that the empirical distribution of the delocalized eigenvectors are in some sense close to a Gaussian distribution. We will summarize the concentration result for random matrices with respect to a metric coming from graph limit theory, which is an important element in the proofs - together with other tools from probability theory and information theory. Joint work with Balázs Szegedy.
The theory of graph limits studies the convergence of sequences of graphs with a diverging number of vertices. From an applied perspective, it aims to represent very large networks conveniently. However, until recently, particular cases for graph limits have been investigated separately. The theory of hypergraph limits is even less developed. In this talk I will give a brief introduction to a recent unified approach to graph limits called action convergence. Moreover, I will present some work in progress on the extension of action convergence to hypergraphs.
Applying topological data analysis to neural networks (in the sense of brains, not machine learning) has evolved into a field that has come to be known as topological neuroscience. For topological toolbox we first need to build a topological space on the directed graph representing our network. One convenient construction is the directed flag complex built out of directed cliques. However, when making topological measurements, like computing simplicial homology, the directionality information of the network is lost to some extent. I will show how to build new spaces out of directed cliques, that are more sensitive to the directionality, by employing so called q-connectivity of Atkin's. I will then outline another, algebraic, homology that can be computed for directed graphs, the Hochschild homology of the path algebra, and how that can be enhanced with the new spaces just built out of directed cliques. I will aim to give an accessible talk by introducing the possibly unfamiliar topological notions.
Reaction networks (RN) comprise a set $X$ of species and a set $R$ of reactions $Y\to Y'$, each converting a multiset of educts into a a multiset of products. RNs are equivalent to directed hypergraphs. However, not all RNs necessarily admit a chemical interpretation. Instead, they might contradict fundamental principles of physics such as the conservation of energy and mass or the reversibility of chemical reactions. Chemically plausible RNs allow neither a perpetuum mobile, i.e., a "futile cycle" of reactions with non-vanishing energy production, nor the creation or annihilation of mass. Such RNs are said to be thermodynamically sound and conservative. For finite RNs, both conditions can be expressed equivalently as properties of the stoichiometric matrix. These conditions are also sufficient for the existence of a realization in terms of sum formulas, obeying conservation of "atoms". In particular, these realizations can be chosen such that any two species have distinct sum formulas, unless the RN implies that they are "obligatory isomers", in which case they always have the same sum formula. In terms of structural formulas, every compound is a labeled multigraph, in essence a Lewis formula, and reactions comprise only a rearrangement of bonds such that the total bond order is preserved. In particular, for every conservative RN, there exists a Lewis realization, in which any two compounds are realized by pairwisely distinct multigraphs. Autocatalysis is a deceptively simple concept, referring to the situation that a chemical species $X$ catalyzes its own formation. Given a RN it is not at all straightforward to identify species that are autocatalytic in the sense that there is a sub-network that takes $X$ as input and produces more than one copy of $X$ as output. The difficulty arises from the need to distinguish autocatalysis e.g. from the superposition of a cycle that consumes and produces equal amounts of $X$ and a pathway that produces $X$. A number of competing notions, such as exclusive autocatalysis and autocatalytic cycles, have been introduced and studied to some extent. However, many questions remain open for future research.
In this paper, we consider a randomized greedy algorithm for independent sets in $r$-uniform $d$-regular hypergraphs $G$ on $n$ vertices with girth $g$. By analyzing the expected size of the independent sets generated by this algorithm, we show that $\alpha(G)\geq (f(d,r)-\epsilon(g,d,r))n$, where $\epsilon(g,d,r)$ converges to $0$ as $g\rightarrow\infty$ for fixed $d$ and $r$, and $f(d,r)$ is determined by a differential equation. This extends earlier results of Gamarnik and Goldberg for graphs~\cite{GG}. We also prove that when applying this algorithm to uniform linear hypergraphs with bounded degree, the size of the independent sets generated by this algorithm concentrate around the mean asymptotically almost surely.
The Kuramoto model provides a prototypical framework to study the dynamics interacting particle systems. The classical heterogeneous Kuramoto model exhibits two main dynamically important states - desynchronization and partial synchronization. Depending on the parameters of the system, the long term behavior always tends to either of these states. However, when considering identical oscillators on a nearest-neighbor graph, the Kuramoto model exhibits more interesting states such as uniformly twisted states. It was discovered by Wiley, Strogatz and Girvan in 2006 that the stability of these twisted stated depends on the coupling range of the nearest-neighbor graph. Since this original analysis was published, many generalizations and variants were developed. In this talk, we will analyze the bifurcation in which these twisted states loose their stability upon varying parameters, such as the coupling range, of the system. We investigate the existence and shape of bifurcating equilibria in the infinite particle limit. Moreover, we add higher-order interactions and show how these change the stability of twisted states and influence the bifurcation at which stability is lost or gained.
Directed hypergraphs give rise to many different notions of connectedness, in this talk I will briefly talk of some notions, focusing on the connectivity definition based on the simplest, least restrictive, construction of hyperpaths. Besides that, I will talk about a generalized version of Whitney's inequalities, which relates vertex connectivity under strong removal, hyperedge connectivity under weak removal, and a degree parameter analogous to those defined in the Whitney inequalities for digraphs. Finally, I will speak of the relation between the connectivity indices of the directed hypergraphs with those of their bipartite representation or König representation.
Contagion on higher-order networks provides a natural basis for the study of social reinforcement effects through group interactions. In this presentation, I will introduce group-based approximate master equations for hypergraph contagion. Compared to a standard heterogeneous mean-field theory, this compartmental approach preserves the dynamical correlations within groups of arbitrary size. Consequently, it provides extremely accurate predictions for contagions on random heterogeneous hypergraphs, while still being analytically tractable.
This approach helps us to better understand the important role of group interactions in two ways: (1) Dynamical correlations can induce localization of the contagion in the largest groups, which significantly affects the critical properties of the system. (2) When trying to maximize the early spread, if the contagion is sufficiently nonlinear (strong social reinforcement) it is more effective to engineer the initial configuration of groups than to infect the most central nodes. This is interpreted as influential groups being more important than influential spreaders for highly nonlinear contagion processes.
Network scientists have shown that there is great value in studying pairwise interactions between components in a system. Recently, however, there has been increased interest in the idea of accounting directly for higher-order interactions, notably through a simplicial complex or a hypergraph representation, where each edge (or simplex) may involve multiple nodes.
In this talk we present a nonlinear eigenvalue framework for incorporating higher-order interactions into network centrality measures. The proposed framework covers classical network coefficients such as matrix and tensor eigenvector centralities, but further allows for many interesting extensions. In particular, we show how this can be used to detect core and periphery structures in hypergraphs.
The underlying object of study is a constrained nonlinear eigenvalue or singular value problem. By exploiting recent developments in nonlinear Perron-Frobenius theory, we can provide guarantees of existence and uniqueness for the network measures, which we can also efficiently compute via a nonlinear power method. We illustrate the results on several example datasets.
At the intersection of Topological Data Analysis and machine learning, the field of cellular signal processing has advanced rapidly in recent years. In this context, each signal on the cells of a complex is processed using the combinatorial Laplacian and the resulting Hodge decomposition. Meanwhile, discrete Morse theory has been widely used to speed up computations by reducing the size of complexes while preserving their global topological properties. In this talk, we introduce an approach to signal compression and reconstruction on complexes that leverages the tools of discrete Morse theory. The main goal is to reduce and reconstruct a cell complex together with a set of signals on its cells while preserving their global topological structure as much as possible.
We study a natural model of random 2-dimensional cubical complexes which are subcomplexes of an n-dimensional cube, and where every possible square (2-face) is included independently with probability p. Our main result exhibits a sharp threshold p=1/2 for homology vanishing as the dimension n goes to infinity. This is a 2-dimensional analogue of the Burtin and Erdős-Spencer theorems characterizing the connectivity threshold for random graphs on the 1-skeleton of the n-dimensional cube. Our main result can also be seen as a cubical counterpart to the Linial-Meshulam theorem for random 2-dimensional simplicial complexes. However, the models exhibit strikingly different behaviors. We show that if p > 1 - sqrt(1/2) (approx 0.2929), then with high probability the fundamental group is a free group with one generator for every maximal 1-dimensional face. As a corollary, homology vanishing and simple connectivity have the same threshold. This is joint work with Matthew Kahle and Elliot Paquette.
The concept of strict deformation quantization provides a mathematical formalism that describes the transition from a classical theory to a quantum theory in terms of deformations of (commutative) Poisson algebras (representing the classical theory) into non-commutative C*-algebras (characterizing the quantum theory). This theory is particularly suitable to model quantum spin systems in the ' classical' limit. In this seminar we introduce the basic ideas, provide several examples and finally propose possible generalizations to hypergraph theory.
Spectral hypergraph theory studies the qualitative properties of a hypergraph that can be inferred from the eigenvalues and the eigenvectors of either square matrices or tensors associated with it. It generalizes the spectral theory of graphs, which has a long history and is widely used in applications. In this talk we will recall some key results in spectral graph theory before discussing spectral hypergraph theory, both via matrices and via tensors. We will also compare these two different techniques, and we will see some applications to dynamical systems and data analysis.
