April 28-May 2, 2014
The Poisson and Martin Boundaries of a planar graph will be discussed, and shown to be equivalent to the geometric boundary when the planar embedding is sufficiently nice. Based on joint work with Barlow, Gurel-Gurevich and Nachmias.
Keywords of the presentation: cop and robber game, dismantlable graphs, Gromov hyperbolicity
In the talk, after an introduction of the cop and robber game and Gromov hyperbolicity, we will outline the proof that all cop-win graphs G in the game in which the robber and the cop move at different speeds s and s' with s'0, this establishes a new --game-theoretical-- characterization of Gromov hyperbolicity. Using these results, we describe a simple constant-factor approximation of hyperbolicity of a graph on n vertices running in O(n^2log n) time. Joint work with J. Chalopin, P. Papasoglu, and T. Pecatte.Read More...
The persistent/zig-zag persistent intervals provide a
meaningful topological summary of a given filtration/sequence of
spaces. However, there often arises the need to compute sparse
generators for these intervals which serve to "track" the features
corresponding to the intervals. We will address this problem on two
aspects: 1) simplification of the data in order to reduce the
computational complexity while preserving the desired topological
features , and 2) computing a specific summand decomposition of the
given persistent/zig-zag module where the summands result in the
desired generators. Further, given a choice of a set of filtrations, we
will present meaningful ways to choose the right filtration where the
resulting bar-code reflects some underlying geometric features.
Keywords of the presentation: Persistence, (co)homology, simplicial map, Rips filtration, sparsification
Recent data sparsification strategies in topological data analysis such as Graph Induced Complex and sparsified Rips complex give rise to a sequence of simplicial complexes connected by simplicial maps rather than inclusions. As a result, the need for computing topological persistence under such maps arises. We propose a practical algorithm for computing such persistence in Z2-homology.Read More...
A simplicial map can be decomposed into a set of elementary inclusions and vertex collapses--two atomic operations that can be supported efficiently with the notion of simplex annotations for computing persistent homology. A consistent annotation through these atomic operations implies the maintenance of a consistent cohomology basis, hence a homology basis by duality. While the idea of maintaining a cohomology basis through an inclusion is not new, maintaining them through a vertex collapse is new, which constitutes an important atomic operation for simulating simplicial maps. Annotations support the vertex collapse in addition to the usual inclusion quite naturally. We exhibit an application of this new tool in which we approximate the persistence diagram of a filtration of Rips complexes where vertex collapses are used to tame the blow-up in size.
Keywords of the presentation: Energy of surface deformations
There are a variety of ways to measure the stretching that occurs when one surface is deformed onto another. Various energies can be defined to quantify such distortions, and the magnitude of these energies can be used to compare the difference between two shapes.
We will discuss some applications of these ideas to mathematics and to biology. In topology, these ideas lead to new results on the space of triangulations of a surface. In biology, we will discuss computations used to compare brain cortices and proteins.
Keywords of the presentation: Ollivier-Ricci curvature, wireless networks, capacity region, tree-width, quantum adiabatic computations
Ollivier-Ricci curvature appeared in the context of Riemannian geometry as a coarse notion of the ordinary Ricci curvature. It then migrated to graphs, where its interpretation as a transportation cost (formalized under the first Wasserstein distance) clearly makes it relevant to networking problems. The first occurrence of the Ollivier-Ricci curvature is in the context of wireless networking under a protocol inspired, but different in many respects, from the Back-Pressure and referred to as Heat-Diffusion. Equipped with a concept of heat diffusion on a directed, interference network, it will be shown that the Heat-Diffusion protocol has the unique property of throughput optimality in addition to Pareto optimality relative to average queue length and routing cost. As major result, it will be shown that average queue length and routing cost both increase as the Ollivier-Ricci curvature decreases (becomes more negative). In addition, as the Ollivier-Ricci curvature decreases (becomes more negative), the capacity region shrinks. In a sense, the Ollivier-Ricci curvature plays the same role as the Gromov curvature of wireline networks. It should be noted, however, that the protocol for wireless and wireline networks are different and hence call for different curvature concept to deal with the "congestion" problem. This already gives the hint that the two curvatures cannot be related to each other. This fact is best confirmed by the tree-width problem, instrumental in mapping--and solving--a QUBO problem on a quantum adiabatic architecture. Simulation results on a variety of graphs show a simple linear interpolation relation between tree-width and Ollivier-Ricci curvature, while Gromov curvature, related to tree-length, can be demonstrated to be incomparable with tree-width.Read More...
(This is work in progress with Dominic Dotterrer and Larry Guth.)
In a graph, the girth is the length of the smallest cycle. How large
the girth can be for a graph on n vertices and m edges is a very well
studied problem in combinatorics. More generally, in a d-dimensional
simplicial complex, we define the d-systole to be the smallest
nonempty collection of closed d-dimensional faces whose union has no
boundary, and we measure the size of a systole in terms of volume,
i.e. the number of faces. It is natural to ask what is the largest
possible d-systole for a simplicial complex on n vertices with m
We show the existence of simplicial complexes with large systoles
using random simplicial complexes with modifications, and we also
require some new results on estimating the number of triangulated
surfaces on a given number of vertices. On the other hand, we show
that the systoles can not be much larger than this, so these results
are essentially optimal. In the higher-dimensional setting, there are
surprising contrasts with the classical graph theoretic picture, and
in particular the systoles can be quite large.
Keywords of the presentation: Lorentzian geometry, de Sitter spaces, complex networks
Random geometric graphs in Lorentzian spaces of constant positive curvature---de Sitter spaces---are shown to model well the structure and dynamics of some complex networks, such as the Internet, social and biological networks. Random geometric graphs on Lorentzian manifolds are known as causal sets in quantum gravity where they represent discretizations of the global causal structure of spacetime. If the expansion of a universe is accelerating, its spacetime is asymptotically de Sitter spacetime. Several connections between random de Sitter graphs, and Apollonian circle packings, Farey trees, divisibility network of natural numbers, and the Riemann hypothesis are also discussed.Read More...
Keywords of the presentation: Internet, dimension, ASN graph, persistent homology
The large-scale structure of the Internet (or, rather of the graph of the Autonomous System Nodes) has been attracting a lot of attention by the researchers for decades. One family of attractive models for this graph stipulates that it "looks like" is if sampled from a hyperbolic plane. We discuss possible tests for the dimension of samples from manifolds, and apply them to the ANS graph.
We state some results on Cheeger Inequalities for the combinatorial
Laplacian and random walks on simplicial complexes.
Specifically, for the combinatorial Laplacian we prove that a Cheeger
type inequality holds on the highest dimension, or for the boundary
operator with Dirichlet boundary conditions. We also show that
coboundary expanders do not satisfy natural Buser or Cheeger
inequalities. We provide some statements about middle dimensions.
We also introduce random walks with absorbing states on simplicial
complexes. Given a simplicial complex of dimension d, a random walk
with an absorbing state is defined which relates to the spectrum of
the k-dimensional Laplacian. We also examine an application of random
walks on simplicial complexes to a semi-supervised learning problem.
Specifically, we consider a label propagation algorithm on oriented
edges, which applies to a generalization of the partially labelled
classification problem on graphs.
Joint work with: John Steenbergen, Caroline Klivans, Anil Hirani, and
Keywords of the presentation: Random walks, simplicial complexes, spectrum, homology
There are well known connections between the random walk on a graph, and its topological and spectral properties. In this talk we will define a new stochastic process on higher dimensional simplicial complexes, which reflects their homological and spectral properties in a parallel way. This leads to high dimensional analogues (not all of which hold!) of classical theorems of Kesten, Alon-Boppana, and others. Based on a joint work with Ori Parzanchevski.
Keywords of the presentation: graph Laplacian eigenvectors, eigenfunction localization, wavelet packets and basis dictionaries on graphs
I will start describing some basics of the graph Laplacian eigenvectors of a given graph and their properties. In particular, I will describe the peculiar phase transition/localization phenomena of such eigenvectors observed on a certain type of graphs (e.g., dendritic trees of neurons). Then, I will describe how to construct wavelet packets on a given graph including the Haar-Walsh basis dictionary using the graph Laplacian eigenvectors. As an application of such basis dictionaries, I will discuss efficient approximation of functions given on graphs. This is a joint work with Jeff Irion, Yuji Nakatsukasa, and Ernest Woei.
Keywords of the presentation: real-life networks, large-scale curvature, delta-hyperbolic graphs, shortest path distance approximation, hyperbolic core
We provide evidence that networks representing social interactions, as measured and archived by electronic communication systems, such as friendship, collaboration, co-authorship, web, peer-to-peer and other kindred networks, exhibit strong hyperbolicity in the sense of Gromov (4-point delta being much smaller than the graph diameter). We outline how one may exploit hyperbolicity to reduce computations on such graphs massively. As an example, we show that all-pair distances on a (mobile call) graph with E=100s of millions of edges may be approximated in O(E) time (i.e., in tens of minutes) with small average error (well below 10% additive error), far smaller than anticipated by theory. We speculate that this result is likely due to the uncharacteristically small hyperbolic cores of these networks (i.e., the set of nodes whose betweenness centrality scales like k*N^2 with k~0.5 as N = the node size of the graph goes to infinity).Read More...
Keywords of the presentation: edge-triangle exponential random graphs, graph limits, asymptotic quantization, jump discontinuity
The edge-triangle exponential random graph model has been a topic of continued research interest. We review recent developments in the study of this classic model and concentrate on the phenomenon of phase transitions. We first describe the asymptotic feature of the model along general straight lines. We show that as we continuously vary the slopes of these lines, a typical graph exhibits quantized behavior, jumping from one complete multipartite structure to another, and the jumps happen precisely at the normal lines of a polyhedral set with infinitely many facets. We then turn to exponential models where certain constraints are imposed and capture another interesting type of jump discontinuity. Based on recent joint work with Alessandro Rinaldo and Sukhada Fadnavis and current joint work in progress with Richard Kenyon.