# Poster Session

Tuesday, April 29, 2014 - 4:05pm - 6:00pm

Lind 400

**One Graph to Rule Them All**

Francesco Vaccarino (Politecnico di Torino)

Let P be a finite poset. We will show that for any P-persistent

object X in the category of finite topological spaces there is a P-

weighted graph, whose weighted clique complex has the same P-persistent

homology as X

(Joint work with G.Petri (ISI Found - IMA long term visitors), A.Patania

(ISI found and Politecnico di Torino) and M.Scolamiero (KTH))**Persistent Homology with Clique Filtration for Digraphs**

Irene Donato (ISI Foundation)

Extracting synthetic and meaningful features from a

network is extremely hard due to the intricate influence

patterns, displayed at all the scales, and often also to

its huge size. A novel topological way to approach this

problem is to adapt persistent homology theory to

networks. This can be naturally done for non-directed

graph using clique complex construction.

Our aim is to extend the persistent homology approach

to directed graphs. For these graphs the main problem is

the identification of clique complexes due to the presence

of double links and loops. In our work we have developed

a mapping that allows to build an undirected graph in a

consistent way i.e., such that the information about the

directivity of the original graph is preserved. While this

procedure implies a proliferation of the nodes it provides

the basic object, the undirected graph, on which the

clique complexes identification is possible and the

machinery of persistent homology can be applied. While

this construction is fairly general we have discussed its

applicability to a specific kind of directed graphs i.e.,

those describing Markov processes.

Joint work with G. Petri, F. Vaccarino and R. Lima**The Persistent Homology of the Vietoris-Rips Complex of the Circle is**

Nontrivial in Every Odd Dimension

Henry Adams (University of Minnesota, Twin Cities)

Consider the Vietoris-Rips complex of the circle of unit circumference equipped with the geodesic metric. Its persistent homology diagram contains an interval of positive length in every odd dimension. In particular, the persistence diagram for (2k+1)-dimensional homology consists of the open interval with birth time k/(2k+1) and death time (k+1)/(2k+3), and over this interval the Vietoris-Rips complex is homotopy equivalent to the (2k+1)-dimensional sphere.

Joint work-in-progress with Michal Adamaszek,Christopher Peterson, and Corrine Previte.**Injectivity and Cubical Clustering**

Dan Guralnik (University of Pennsylvania)

This is joint work with Jared Culbertson (AFRL) and Peter Stiller (Texas A&M). Extending the work of Carlsson--Memoli, we aim to construct a method for non-nested hierarchical clustering that is based on Isbell's theory of injective spaces. Every metric space isometrically embeds in a unique (up to isometry) injective envelope that highlights canonical features of the original metric space. Inspired by the work of Bandelt--Dress on split decompositions, we seek to exploit the structure of the injective envelope to determine a non-nested clustering program which replaces tree-based dendrograms with cubical complexes. Towards this end, we present results on the injectivity of cubical complexes and discuss some of the limitations of related work.**Non Total-Unimodularity Neutralized Simplicial Complexes**

Bala Krishnamoorthy (Washington State University)

Given a simplicial complex K with weights on its simplices and a chain on it, the Optimal Homologous Chain Problem(OHCP) is to find a chain with minimal weight that is homologous to the given chain. The OHCP is NP-complete, but if the boundary matrix of K is totally unimodular (TU), it becomes solvable in polynomial time when modeled as a linear program (LP). We define a condition on K called non total-unimodularity neutralized (NTUN), which ensures that even when the boundary matrix is not TU, the OHCP LP must contain an integral optimal vertex for every input chain. This is joint work with Gavin Smith. A preprint is available at http://www.arXiv.org/abs/1304.4985.**Minimal Crystallizations of 3-Manifolds**

Biplab Basak (Indian Institute of Science)

We have introduced the weight of a group which has a presentation with number of relations is at most the number of generators. We have shown that the number of vertices in any crystallization of a connected closed 3-manifold $M$ is at least the weight of the fundamental group of $M$. This lower bound is sharp for the 3-manifolds $mathbb{R P}^3$, $L(3,1)$, $L(5,2)$, $S^1times S^1 times S^1$, $S^{hspace{.2mm}2} times S^1$, $S^{hspace{.2mm}2}

mbox{$times hspace{-5mm}_{-}$} , S^{hspace{.1mm}1}$ and $S^{hspace{.2mm}3}/Q_8$, where $Q_8$ is the quaternion group.

Moreover, there is a unique such facet minimal crystallization in each of these seven cases. We have also constructed crystallizations of $L(kq-1,q)$ with $4(q+k-1)$ facets for $q, k geq 2$ and $L(kq+1,q)$ with $4(q+k)$ facets for $q, kgeq 1$. By a recent result of Swartz, our crystallizations of $L(kq+1, q)$ are facet minimal when $kq+1$ are even. Our construction of a crystallization of a 3-manifold $M$ is based on a presentation of the fundamental group of $M$.**Hierarchical Quasi-Clustering Methods for Asymmetric Networks**

Santiago Segarra (University of Pennsylvania)

We introduce hierarchical quasi-clustering methods, a generalization of hierarchical clustering for asymmetric networks where the output structure preserves the asymmetry of the input data. We show that this output structure is equivalent to a finite quasi-ultrametric space and study admissibility with respect to two desirable properties. We prove that a modified version of single linkage is the only admissible quasi-clustering method. Moreover, we show stability of the proposed method and we establish invariance properties fulfilled by it. Algorithms are further developed and the value of quasi-clustering analysis is illustrated with a study of internal migration within United States.**Towards a Discrete Isoperimetric Inequality for Embedded Complexes**

Eran Nevo (Ben Gurion University of the Negev)

Descartes showed that a planar graph with n vertices, n at least 3, has at most 3n-6 edges; this follows easily from Euler's formula. We seek an analog in higher dimensions. Kalai and Sarkaria conjectured that for d-dimensional simplicial complexes embeddable in the 2d-sphere, the ratio between the number of d-faces and (d-1)-faces is bounded by a constant depending on d.

We present a new approach towards this problem, by suggesting a rigidity theory for balanced complexes, analogous to the classical framework rigidity.

Based on a joint work with Gil Kalai and Isabella Novik, arXiv:1312.0209.**The Ordered Switching Method; Uniform Sampling for Random Directed**

Acyclic Networks

Corrie Jacobien Carstens (RMIT University)

Random graph models are commonly used as a null-hypothesis in the study of

real-world networks. The random graphs generated by such models are used to

deduce the significance of properties of real networks. As such, it is

important that they sample uniformly from a set of networks that resemble

the real network under study. For instance, it is common to sample from a

specific network class, such as the class of simple undirected networks. It

is also common to fix the degree sequence of the random networks, since the

degree distribution has a big impact on other network properties.

Directed acyclic networks are an important class of networks, they appear

in biology, computer science, engineering, pure mathematics and statistics.

The defining property of a directed acyclic network is that its vertices

can be ordered such that all edges are directed from new to old. Such

an ordering on the vertices is called a topological ordering.

Existing random graph models introduce unnatural features when used to

randomize this class of networks, such as directed cycles and multiple

edges. We propose the ordered switching method to overcome the shortcomings

of existing models. As its name suggests, it is a type of switching method.

We prove that this method samples uniformly from all directed acyclic

networks with fixed in-degree and out-degree sequence and fixed topological

ordering.

Since directed acyclic networks are an important class of networks and

random graph models are widely used to find significant properties of real

networks, there are many applications for this new random network model.**Ricci Curvature of the Internet Topology**

Jie Gao (State University of New York, Stony Brook (SUNY))

Analysis of Internet topologies at both the router and AS level has shown that the Internet topology has negative curvature, measured by Gromov’s “thin triangle condition”. Negative curvature property is tightly related to structural properties of the network, such as core congestion and route reliability. In this work we analyze the discrete Ricci curvature, defined and studied by Ollivier, Lin & Yau, etc, of the Internet topologies. Ricci curvature measures whether local distances diverge or converge and is a local measure that can be quickly computed. It is a more refined measure which allows us to understand the network structure at various resolutions. We show by various Internet data sets a few universal observations — 1) the network uses negatively curved edges to connect clusters of nodes, within which edges are mostly positively curved; 2) negative Ricci curvature is closely correlated to network congestion; 3) geodesics through negatively curved edges are more stable, under node/link perturbations. We also show that the configuration model using power law degree distribution generates networks of similar curvature distribution while G(n, p) model does not.

This is joint work with Chien Chun Ni and Xianfeng David Gu from Stony Brook University.**A-infinity Persistence**

Aniceto Murillo (University of Málaga)

We introduce A-infinity persistence of a given homology filtration of topological spaces. This is a family

homological invariants which provide information not readily available by the persistent Betti numbers of the given filtration. This may help to detect noise, not just in the simplicial structure of the filtration

but in further geometrical properties in which the higher diagonals of the A-infinity structure are translated. For instance, persistence of the second diagonal translates into persistence of indecomposability of cup products. In the same way, persistence of the third diagonal translates into persistence of indecomposability of Massey products.

Joint work with Francisco Belchi**Intrinsic Volumes of Random Cubes**

Michael Werman (Hebrew University)Matthew Wright (University of Minnesota, Twin Cities)

The intrinsic volumes generalize both Euler characteristic and Lebesgue

volume, quantifying the size of a set in various ways. A random cubical

complex is a union of (possibly high-dimensional) unit cubes selected from

a lattice according to some probability model. We analyze the intrinsic

volumes of various types of random cubical complexes, obtaining polynomial

formulae for the expected value and variance of these intrinsic volumes. We

then prove an interleaving theorem about the roots of the expected

intrinsic volumes -- that is, the values of the probability parameter at

which an expected value is zero. Furthermore, we present a central limit

theorem, showing that the distribution of each intrinsic volume tends

toward a normal distribution as the size of the lattice increases towards

infinity. This work is motivated by the study of noise in digital images

and has applications in image processing.**Topological Data Analysis Through Directed Filtrations**

Greg Bell (University of North Carolina, Greensboro)

Given a finite point set X, one constructs the Cech complex at scale r by

taking the nerve of the subset covered by r-balls centered at the points of

X.

Given a direction vector u and a scale 0 ellipsoids with major axis parallel to u and length r. The normal

directions to u have length cr. We then compute the homology of the complex

obtained as the nerve of this cover. This additional structure defines a

generalized persistence module, yields a correspondence between rotations

and interleavings of persistence modules and suggests an approach to detect

directed homological features.

This is joint work with Athanasios Gentimis at NC State.**Higher-dimensional Discrete Cheeger Inequalities**

Anna Gundert (Universität zu Köln)

For graphs, expansion is a useful concept that has found applications in various areas. The success of this concept has inspired the search for a corresponding notion in higher-dimensions.

Expansion for graphs can be expressed combinatorially or via the spectrum of the Laplacian. The close connection of these two notions is expressed, e.g., by the discrete Cheeger inequality.

We describe several possible notions of expansion for simplicial complexes of higher dimension as well as results exploring connections between these properties.**Complex Contagion on Noisy Geometric Networks**

Dane Taylor (Statistical and Applied Mathematical Sciences Institute (SAMSI))

The study of contagion on networks is central to our understanding of collective social processes and epidemiology. However, for networks arising from an underlying manifold such as the Earth’s surface, it remains unclear the extent to which the dynamics will reflect this inherent structure, especially when long-range, “noisy” edges are present. We study the Watts threshold model (WTM) for complex contagion on noisy geometric networks – a generalization of small world networks in which nodes are embedded on a manifold. To study the extent to which contagion adheres to the manifold versus the network, which can greatly disagree on notions such as node-to-node distance, we present WTM-maps that embed the network nodes as a point cloud for which we study the topology, dimensionality, and geometry.