We study Vietoris-Rips and Cech complexes of metric wedge sums and metric gluings. We show that the Vietoris-Rips (resp. Cech) complex of a wedge sum, equipped with a natural metric, is homotopy equivalent to the wedge sum of the Vietoris-Rips (resp. Cech) complexes. We also provide generalizations for certain metric gluings, i.e. when two metric spaces are glued together along a common isometric subset. As our main example, we deduce the homotopy type of the Vietoris-Rips complex of two metric graphs glued together along a sufficiently short path. As a result, we can describe the persistent homology, in all homological dimensions, of the Vietoris-Rips complexes of a wide class of metric graphs.

A cross-cycle in a flag simplicial complex K is an induced subcomplex that is isomorphic to the boundary of a cross-polytope and that contains a maximal face of K. A cross-cycle is an efficient way to define a non-zero class in the homology of K. For an independence complex of a graph G, a cross-cycle is equivalent to a combinatorial object: induced matching containing a maximal independent set. We study the complexity of finding cross-cycles in independence complexes. We show that in general this problem is NP-complete when input is a graph whose independence complex we consider. We then focus on the class of chordal graphs, where, as we show, cross-cycles detect all of homology of the independence complex. As our main result, we present a polynomial time algorithm for detecting a cross-cycle in the independence complex of a chordal graph. Our algorithm is based on the geometric intersection representation of chordal graphs and has an efficient implementation.

We study the task of testing properties of probability distributions. We consider a scenario in which we have access to independent samples of an unknown distribution with infinite (perhaps even uncountable) support. Our goal is to test whether has a given property or it is ε-far from it (in the statistical distance, with the L1-distance measure). It is not difficult to see that for many natural distributions on infinite or uncountable domains, no testing algorithm can exist and the central objective of our study is to understand if there are any nontrivial distributions that can be efficiently tested. For example, it is easy to see that there is no testing algorithm that tests if a given probability distribution on [0, 1] is uniform. We show however, that if some additional information about the input distribution is known, testing uniform distribution is possible. We extend the recent result about testing uniformity for monotone distributions on Boolean n-dimensional cubes by Rubinfeld and Servedio (STOC'2005) to the case of continuous [0, l]n cubes. We show that if a distribution on [0, l]n is monotone, then one can test if is uniform with the sample complexity (n/ε2). This result is optimal up to a polylogarithmic factor.

We study the problem of recognizing graph powers and computing roots of graphs. We provide a polynomial time recognition algorithm for $r$-th powers of graphs of girth at least $2r+3$, thus improving a bound conjectured by Farzad et al. (STACS 2009). Our algorithm also finds all $r$-th roots of a given graph that have girth at least $2r+3$ and no degree one vertices, which is a step towards a recent conjecture of Levenshtein that such root should be unique. On the negative side, we prove that recognition becomes an NP-complete problem when the bound on girth is about twice smaller. Similar results have so far only been attempted for $r=2,3$.

We study the problem of recognizing graph powers and computing roots of graphs. Our focus is on classes of graphs with no short cycles. We provide a polynomial time recognition algorithm for r-th powers of graphs of girth at least $2r+3$, thus improving a recently conjectured bound. Our algorithm also finds all r-th roots of a given graph that have girth at least $2r+3$ and no degree one vertices, which is a step toward a recent conjecture of Levenshtein [Discrete Math., 308 (2008), pp. 993–998] that such roots should be unique. Similar algorithms have so far been designed only for $r=2,3$. On the negative side, we prove that recognition of graph powers becomes an NP-complete problem when the bound on girth is about twice smaller. (Anna Adamaszek's correct affiliation is Department of Computer Science and Centre for Discrete Mathematics and Its Applications (DIMAP), University of Warwick, Coventry, CV4 7AL, UK.)