Virtual

In this talk, I will give a brief introduction to level-set methods for image analysis. I will then describe an application of level-sets to the construction of filtrations for persistent homology computations. I will present several case studies with various spatial data sets using this construction, including applications to voting, analyzing urban street patterns, and spiderwebs. I will conclude by discussing the types of data which I might imagine such methods to be suitable for analyzing and suggesting a few potential future applications of level-set based computations.

In this talk, I will present the theory of combinatorial multivector fields for finite topological spaces, the main subject of my thesis. The idea of combinatorial vector fields came from Forman and emerged naturally from discrete Morse theory. Lately, Mrozek generalized it to the multivector fields theory for Lefschetz complexes. In our work, we simplified and extended it to the finite topological spaces settings. We developed a combinatorial counterpart for dynamical objects, such as isolated invariant sets, isolating neighbourhoods, Conley index, limit sets, and Morse decomposition. We proved the additivity property of the Conley index and the Morse inequalities. Furthermore, we applied persistence homology to study the evolution and the stability of Morse decomposition. In the last part of the talk, I will show numerical results and potential future directions from a data-analysis perspective. 

Systems with lattice geometry can be renormalized exploiting their embedding in metric space, which naturally defines the coarse-grained nodes. By contrast, complex networks defy the usual techniques because of their small-world character and lack of explicit metric embedding. Current network renormalization approaches require strong assumptions (e.g. community structure, hyperbolicity, scale-free topology), thus remaining incompatible with generic graphs and ordinary lattices. Here we introduce a graph renormalization scheme valid for any hierarchy of coarse-grainings, thereby allowing for the definition of block-nodes across multiple scales. This approach reveals a necessary and specific dependence of network topology on an additive hidden variable attached to nodes, plus optional dyadic factors. Renormalizable networks turn out to be consistent with a unique specification of the fitness model, while they are incompatible with preferential attachment, the configuration model or the stochastic blockmodel. These results highlight a deep conceptual distinction between scale-free and scale-invariant networks, and provide a geometry-free route to renormalization. If the hidden variables are annealed, the model spontaneously leads to realistic scale-free networks with cut-off. If they are quenched, the model can be used to renormalize real-world networks with node attributes and distance-dependence or communities. As an example we derive an accurate multiscale model of the International Trade Network applicable across arbitrary geographic resolutions.

https://arxiv.org/abs/2009.11024 (23 sept.)

Modular and hierarchical structures are pervasive in real-world complex systems. A great deal of effort has gone into trying to detect and study these structures. Important theoretical advances in the detection of modular, or "community", structures have included identifying fundamental limits of detectability by formally defining community structure using probabilistic generative models. Detecting hierarchical community structure introduces additional challenges alongside those inherited from community detection. Here we present a theoretical study on hierarchical community structure in networks, which has thus far not received the same rigorous attention. We address the following questions: 1) How should we define a valid hierarchy of communities? 2) How should we determine if a hierarchical structure exists in a network? and 3) how can we detect hierarchical structure efficiently? We approach these questions by introducing a definition of hierarchy based on the concept of stochastic externally equitable partitions and their relation to probabilistic models, such as the popular stochastic block model. We enumerate the challenges involved in detecting hierarchies and, by studying the spectral properties of hierarchical structure, present an efficient and principled method for detecting them.

https://arxiv.org/abs/2009.07196 (15 sept.)

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please send email to @email.

Preconditioning techniques are widely used for speeding up the iterative solution of systems of linear equations, often by transforming the system into one with lower condition number. Even though the condition number also serves as the determining constant in simple bounds for the numerical error of the solution, simple experiments and bounds show that such preconditioning on the matrix level is not guaranteed to reduce this error. Transformations on the operator level, on the other hand, improve both accuracy and speed of iterative methods as predicted by the change of the condition number. We propose to investigate such methods under a common framework, which we call full operator preconditioning, and show practical examples.

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please send an email to @email.

This talk will focus on the following two related problems:
    (1) What is the minimum number of edges in a graph containing all $n$-vertex planar graphs as subgraphs? A simple construction of Babai, Erdos, Chung, Graham, and Spencer (1982) has $O(n^{3/2})$ edges, which is the best known upper bound.
    (2) What is the minimum number of *vertices* in a graph containing all $n$-vertex planar graphs as *induced* subgraphs? Here steady progress has been achieved over the years, culminating in a $O(n^{4/3})$ bound due to Bonamy, Gavoille, and Pilipczuk (2019).
    As it turns out, a bound of $n^{1+o(1)}$ can be achieved for each of these two problems. The two constructions are somewhat different but are based on a common technique. In this talk I will first give a gentle introduction to the area and then sketch these constructions. The talk is based on joint works with Vida Dujmović, Louis Esperet, Cyril Gavoille, Piotr Micek, and Pat Morin.

What is fairness, and to what extent is it practically achievable? I'll talk about a simple mathematical model under which one might hope to understand such questions. Red and blue points occur as independent homogeneous Poisson processes of equal intensity in Euclidean space, and we try to match them to each other. We would like to minimize the sum of a some function (say, a power, $\gamma$) of the distances between matched pairs. This does not make sense, because the sum is infinite, so instead we satisfy ourselves with minimizing *locally*. If the points are interpreted as agents who would like to be matched as close as possible, the parameter $\gamma$ encodes a measure of fairness - large $\gamma$ means that we try to avoid occasional very bad outcomes (long edges), even if that means inconvenience to others - small $\gamma$ means everyone is in it for themselves.
    In dimension 1 we have a reasonably complete picture, with a phase transition at $\gamma=1$. For $\gamma<1$ there is a unique minimal matching, while for $\gamma>1$ there are multiple matchings but no stationary solution. In higher dimensions, even existence is not clear in all cases.

A spanning tree of $G$ is a subgraph of $G$ with the same vertex set as $G$ that is a tree. In 1981, McKay proved an asymptotic result regarding the number of spanning trees in random $k$-regular graphs, showing that the number of spanning trees $\kappa_1(G_n)$ in a random $k$-regular graph on $n$ vertices satisfies $\lim_{n \to \infty} (\kappa_1(G_n))^{1/n} = c_{1,k}$ in probability, where $c_{1,k} = (k-1)^{k-1} (k^2-2k)^{-(k-2)/2}$.

In this talk we will discuss a high-dimensional of the matching model for simplicial complexes, known as random Steiner complexes. In particular, we will prove a high-dimensional counterpart of McKay's result and discuss the local limit of such random complexes. 
Based on a joint work with Lior Tenenbaum. 

We study the minimum total weight of a disk triangulation using any number of vertices out of $\{1,..,n\}$ where the boundary is fixed and the $n \choose 3$ triangles have independent rate-1 exponential weights. We show that, with high probability, the minimum weight is equal to $(c+o(1))n-1/2\log n$ for an explicit constant $c$. Further, we prove that, with high probability, the minimum weights of a homological filling and a homotopical filling of the cycle $(123)$ are both attained by the minimum weight disk triangulation. We will discuss a related open problem concerning simple-connectivity of random simplicial complexes, where a similar phenomenon is conjectured to hold. Based on joint works with Itai Benjamini, Eyal Lubetzky, and Zur Luria.