Source author record

Matthew Kahle

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.AT math.PR math.MG math-ph math.GR math.GT math.MP Robotics

Catalog footprint

Research overview

26works

9topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Asymptotic Betti numbers for hard squares in the homological liquid regime

We study configuration spaces $C(n; p, q)$ of $n$ ordered unit squares in a $p$ by $q$ rectangle. Our goal is to estimate the Betti numbers for large $n$ , $j$ , $p$ , and $q$ . We consider sequences of area-normalized coordinates, where $(\frac{n}{pq}, \frac{j}{pq})$ converges as $n$ , $j$ , $p$ , and $q$ approach infinity. For every sequence that converges to a point in the "feasible region" in the $(x,y)$ -plane, we show that the factorial growth rate of the Betti numbers is the same as the factorial growth rate of $n!$ . This implies that (1) the Betti numbers are vastly larger than for the configuration space of $n$ ordered points in the plane, which have the factorial growth rate of $j!$ , and (2) every point in the feasible region is eventually in the homological liquid regime.

preprint2022arXiv

Maximal persistence in random clique complexes

We study the persistent homology of an Erdős--Rényi random clique complex filtration on $n$ vertices. Here, each edge $e$ appears at a time $p_e \in [0,1]$ chosen uniform randomly in the interval, and the \emph{persistence} of a cycle $σ$ is defined as $p_2 / p_1$ , where $p_1$ and $p_2$ are the birth and death times of the cycle respectively. We show that for fixed $k \ge 1$ , with high probability the maximal persistence of a $k$ -cycle is of order roughly $n^{1/k(k+1)}$ . These results are in sharp contrast with the random geometric setting where earlier work by Bobrowski, Kahle, and Skraba shows that for random Čech and Vietoris--Rips filtrations, the maximal persistence of a $k$ -cycle is much smaller, of order $\left(\log n / \log \log n \right)^{1/k}$ .

preprint2022arXiv

On the clique number of noisy random geometric graphs

Let $G_n$ be a random geometric graph, and then for $q,p \in [0,1)$ we construct a " $(q,p)$ -perturbed noisy random geometric graph" $G_n^{q,p}$ where each existing edge in $G_n$ is removed with probability $q$ , while and each non-existent edge in $G_n$ is inserted with probability $p$ . We give asymptotically tight bounds on the clique number $ω\left(G_n^{q,p}\right)$ for several regimes of parameter.

preprint2020arXiv

A square-grid coloring problem

Suppose that $n \ge 2$ , and we wish to plant $k$ different types of trees in the squares of an $n \times n$ square grid. We can have as many of each type as we want. The only rule is that every pair of types must occur in an adjacent pair of squares somewhere in the grid. The question is: given $n$ , what is the largest that $k$ can be? Denote this number by $Γ(n)$ , and call this the *complete coloring number* of the $n \times n$ grid. A little thought shows that $Γ(n) \le 2n-1$ . The main question we are interested in is whether $Γ(n) = 2n-1$ for every $n \ge 2$ .

preprint2020arXiv

Configuration spaces of disks in an infinite strip

We study the topology of the configuration spaces $C(n,w)$ of $n$ hard disks of unit diameter in an infinite strip of width $w$ . We describe ranges of parameter or "regimes", where homology $H_j [C(n,w)]$ behaves in qualitatively different ways. We show that if $w \ge j+2$ , then the homology $H_j[C(n, w)]$ is isomorphic to the homology of the configuration space of points in the plane, $H_j[C(n, \mathbb{R}^2)]$ . The Betti numbers of $C(n, \mathbb{R}^2)$ were computed by Arnold, and so as a corollary of the isomorphism, $β_j[C(n,w)]$ is a polynomial in $n$ of degree $2j$ . On the other hand, we show that if $2 \le w \le j+1$ , then $β_j [ C(n,w) ]$ grows exponentially with $n$ . Most of our work is in carefully estimating $β_j [ C(n,w) ]$ in this regime. We also illustrate, for every $n$ , the homological "phase portrait" in the $(w,j)$ -plane--- the parameter values where homology $H_j [C(n,w)]$ is trivial, nontrivial, and isomorphic with $H_j [C(n, \mathbb{R}^2)]$ . Motivated by the notion of phase transitions for hard-spheres systems, we discuss these as the "homological solid, liquid, and gas" regimes.

preprint2020arXiv

Topology and geometry of random 2-dimensional hypertrees

A hypertree, or $\mathbb{Q}$ -acyclic complex, is a higher-dimensional analogue of a tree. We study random $2$ -dimensional hypertrees according to the determinantal measure suggested by Lyons. We are especially interested in their topological and geometric properties. We show that with high probability, a random $2$ -dimensional hypertree $T$ is apsherical, i.e. that it has a contractible universal cover. We also show that with high probability the fundamental group $π_1(T)$ is hyperbolic and has cohomological dimension $2$ .

preprint2020arXiv

Topology of random 2-dimensional cubical complexes

We study a natural model of random 2-dimensional cubical complex which is a subcomplex of an n-dimensional cube, and where every possible square $2$ -face is included independently with probability p. Our main result is to exhibit a sharp threshold p=1/2 for homology vanishing as $n \to \infty$ . This is a 2-dimensional analogue of the Burtin and Erdős-Spencer theorems characterizing the connectivity threshold for random cubical graphs. 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, even in the strong "hitting time" sense. This is in contrast with the simplicial case, where the thresholds are far apart. The proof depends on an iterative algorithm for contracting cycles -- we show that with high probability the algorithm rapidly and dramatically simplifies the fundamental group, converging after only a few steps.

preprint2016arXiv

Maximally Persistent Cycles in Random Geometric Complexes

We initiate the study of persistent homology of random geometric simplicial complexes. Our main interest is in maximally persistent cycles of degree- $k$ in persistent homology, for a either the \cech or the Vietoris--Rips filtration built on a uniform Poisson process of intensity $n$ in the unit cube $[0,1]^d$ . This is a natural way of measuring the largest " $k$ -dimensional hole" in a random point set. This problem is in the intersection of geometric probability and algebraic topology, and is naturally motivated by a probabilistic view of topological inference. We show that for all $d \ge 2$ and $1 \le k \le d-1$ the maximally persistent cycle has (multiplicative) persistence of order $Θ\left(\left(\frac{\log n}{\log \log n} \right)^{1/k} \right),$ with high probability, characterizing its rate of growth as $n \to \infty$ . The implied constants depend on $k$ , $d$ , and on whether we consider the Vietoris--Rips or \cech filtration.

preprint2016arXiv

Random simplicial complexes

Random shapes arise naturally in many contexts. The topological and geometric structure of such objects is interesting for its own sake, and also for applications. In physics, for example, such objects arise naturally in quantum gravity, in material science, and in other settings. Stochastic topology may also be considered as a null hypothesis for topological data analysis. In this chapter we overview combinatorial aspects of stochastic topology. We focus on the topological and geometric properties of random simplicial complexes. We introduce a few of the fundamental models in Section 23.1. We review high-dimensional expander-like properties of random complexes in Section 23.2. We discuss threshold behavior and phase transitions in Section 23.3, and Betti numbers and persistent homology in Section 23.4.

preprint2015arXiv

Erratum: Limit theorems for Betti numbers of random simplicial complexes

We correct the proofs of the main theorems in our paper "Limit theorems for Betti numbers of random simplicial complexes".

preprint2014arXiv

New lower bounds on $χ(R^d)$ for $d=8 \dots 12$

We improve the best lower bounds on the chromatic number of Euclidean space in small dimensions. The new results depend on extensive computations in Sage.

preprint2014arXiv

The threshold for integer homology in random d-complexes

Let Y ~ Y_d(n,p) denote the Bernoulli random d-dimensional simplicial complex. We answer a question of Linial and Meshulam from 2003, showing that the threshold for vanishing of homology H_{d-1}(Y; Z) is less than 80d log n / n. This bound is tight, up to a constant factor.

preprint2013arXiv

Inside the critical window for cohomology of random k-complexes

We prove sharper versions of theorems of Linial-Meshulam and Meshulam-Wallach which describe the behavior for (Z/2)-cohomology of a random k-dimensional simplicial complex within a narrow transition window. In particular, we show that within this window the (k-1)st Betti number is in the limit Poisson distributed. For k=2 we also prove that in an accompanying growth process, with high probability, first cohomology vanishes exactly at the moment when the last isolated (k-1)-simplex gets covered by a k-simplex.

preprint2013arXiv

Sharp vanishing thresholds for cohomology of random flag complexes

For every $k \ge 1$ , the $k$ th cohomology group $H^k(X, \Q)$ of the random flag complex $X \sim X(n,p)$ passes through two phase transitions: one where it appears, and one where it vanishes. We describe the vanishing threshold and show that it is sharp. Using the same spectral methods, we also find a sharp threshold for the fundamental group $π_1(X)$ to have Kazhdan's property (T). Combining with earlier results, we obtain as a corollary that for every $k \ge 3$ there is a regime in which the random flag complex is rationally homotopy equivalent to a bouquet of $k$ -dimensional spheres.

preprint2013arXiv

Topology of random simplicial complexes: a survey

This expository article is based on a lecture from the Stanford Symposium on Algebraic Topology: Application and New Directions, held in honor of Gunnar Carlsson, Ralph Cohen, and Ib Madsen.

preprint2011arXiv

Coboundary expanders

We describe a natural topological generalization of edge expansion for graphs to regular CW complexes and prove that this property holds with high probability for certain random complexes.

preprint2011arXiv

Computational topology for configuration spaces of hard disks

We explore the topology of configuration spaces of hard disks experimentally, and show that several changes in the topology can already be observed with a small number of particles. The results illustrate a theorem of Baryshnikov, Bubenik, and Kahle that critical points correspond to configurations of disks with balanced mechanical stresses, and suggest conjectures about the asymptotic topology as the number of disks tends to infinity.

preprint2011arXiv

Limit theorems for Betti numbers of random simplicial complexes

There have been several recent articles studying homology of various types of random simplicial complexes. Several theorems have concerned thresholds for vanishing of homology, and in some cases expectations of the Betti numbers. However little seems known so far about limiting distributions of random Betti numbers. In this article we establish Poisson and normal approximation theorems for Betti numbers of different kinds of random simplicial complex: Erdős-Rényi random clique complexes, random Vietoris-Rips complexes, and random Čech complexes. These results may be of practical interest in topological data analysis.

preprint2011arXiv

Min-type Morse theory for configuration spaces of hard spheres

We study configuration spaces of hard spheres in a bounded region. We develop a general Morse-theoretic framework, and show that mechanically balanced configurations play the role of critical points. As an application, we find the precise threshold radius for a configuration space to be homotopy equivalent to the configuration space of points.

preprint2011arXiv

The fundamental group of random 2-complexes

We study Linial-Meshulam random 2-complexes, which are two-dimensional analogues of Erdős-Rényi random graphs. We find the threshold for simple connectivity to be p = n^{-1/2}. This is in contrast to the threshold for vanishing of the first homology group, which was shown earlier by Linial and Meshulam to be p = 2 log(n)/n. We use a variant of Gromov's local-to-global theorem for linear isoperimetric inequalities to show that when p = O(n^{-1/2 -ε}) the fundamental group is word hyperbolic. Along the way we classify the homotopy types of sparse 2-dimensional simplicial complexes and establish isoperimetric inequalities for such complexes. These intermediate results do not involve randomness and may be of independent interest.

preprint2011arXiv

The fundamental group of random 2-complexes

preprint2010arXiv

Random geometric complexes

We study the expected topological properties of Cech and Vietoris-Rips complexes built on i.i.d. random points in R^d. We find higher dimensional analogues of known results for connectivity and component counts for random geometric graphs. However, higher homology H_k is not monotone when k > 0. In particular for every k > 0 we exhibit two thresholds, one where homology passes from vanishing to nonvanishing, and another where it passes back to vanishing. We give asymptotic formulas for the expectation of the Betti numbers in the sparser regimes, and bounds in the denser regimes. The main technical contribution of the article is in the application of discrete Morse theory in geometric probability.

preprint2010arXiv

Sparse stable configurations of hard discs in a box

We construct stable configurations of n overlapping discs of radius r in a unit square, with r = O(1/n). By a result of Diaconis, Lebeau, and Michel, this result is best possible, up to a constant factor. A consequence is that the Metropolis algorithm, a well-studied Markov chain on the hardcore model, is not irreducible in this range of parameters.

preprint2008arXiv

Points in a triangle forcing small triangles

An old theorem of Alexander Soifer's is the following: Given five points in a triangle of unit area, there must exist some three of them which form a triangle of area 1/4 or less. It is easy to check that this is not true if "five" is replaced by "four", but can the theorem be improved in any other way? We discuss in this article two different extensions of the original result. First, we allow the value of "small", 1/4, to vary. In particular, our main result is to show that given five points in a triangle of unit area, then there must exist some three of them determining a triangle of area 6/25 or less. Second, we put bounds on the minimum number of small triangles determined by n points in a triangle, and make a conjecture about the asymptotic right answer as n tends to infinity.

preprint2008arXiv

Topology of random clique complexes

In a seminal paper, Erdos and Renyi identified the threshold for connectivity of the random graph G(n,p). In particular, they showed that if p >> log(n)/n then G(n,p) is almost always connected, and if p << log(n)/n then G(n,p) is almost always disconnected, as n goes to infinity. The clique complex X(H) of a graph H is the simplicial complex with all complete subgraphs of H as its faces. In contrast to the zeroth homology group of X(H), which measures the number of connected components of H, the higher dimensional homology groups of X(H) do not correspond to monotone graph properties. There are nevertheless higher dimensional analogues of the Erdos-Renyi Theorem. We study here the higher homology groups of X(G(n,p)). For k > 0 we show the following. If p = n^alpha, with alpha < -1/k or alpha > - 1/(2k+1), then the kth homology group of X(G(n,p)) is almost always vanishing, and if -1/k < alpha < -1/(k+1), then it is almost always nonvanishing. We also give estimates for the expected rank of homology, and exhibit explicit nontrivial classes in the nonvanishing regime. These estimates suggest that almost all d-dimensional clique complexes have only one nonvanishing dimension of homology, and we cannot rule out the possibility that they are homotopy equivalent to wedges of spheres.

preprint2006arXiv

The neighborhood complex of a random graph

For a graph G, the neighborhood complex N[G] is the simplicial complex having all subsets of vertices with a common neighbor as its faces. It is a well known result of Lovasz that if N[G] is k-connected, then the chromatic number of G is at least k + 3. We prove that the connectivity of the neighborhood complex of a random graph is tightly concentrated, almost always between 1/2 and 2/3 of the expected clique number. We also show that the number of dimensions of nontrivial homology is almost always small, O(log d), compared to the expected dimension d of the complex itself.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Matthew Kahle

Research overview

Is this your work?

26 publications

Asymptotic Betti numbers for hard squares in the homological liquid regime

Maximal persistence in random clique complexes

On the clique number of noisy random geometric graphs

A square-grid coloring problem

Configuration spaces of disks in an infinite strip

Topology and geometry of random 2-dimensional hypertrees

Topology of random 2-dimensional cubical complexes

Maximally Persistent Cycles in Random Geometric Complexes

Random simplicial complexes

Erratum: Limit theorems for Betti numbers of random simplicial complexes

New lower bounds on $χ(R^d)$ for $d=8 \dots 12$

The threshold for integer homology in random d-complexes

Inside the critical window for cohomology of random k-complexes

Sharp vanishing thresholds for cohomology of random flag complexes

Topology of random simplicial complexes: a survey

Coboundary expanders

Computational topology for configuration spaces of hard disks

Limit theorems for Betti numbers of random simplicial complexes

Min-type Morse theory for configuration spaces of hard spheres

The fundamental group of random 2-complexes

The fundamental group of random 2-complexes

Random geometric complexes

Sparse stable configurations of hard discs in a box

Points in a triangle forcing small triangles

Topology of random clique complexes

The neighborhood complex of a random graph

See the researcher in context

Building this map preview

Matthew Kahle

Research overview

Is this your work?

26 publications

Asymptotic Betti numbers for hard squares in the homological liquid regime

Maximal persistence in random clique complexes

On the clique number of noisy random geometric graphs

A square-grid coloring problem

Configuration spaces of disks in an infinite strip

Topology and geometry of random 2-dimensional hypertrees

Topology of random 2-dimensional cubical complexes

Maximally Persistent Cycles in Random Geometric Complexes

Random simplicial complexes

Erratum: Limit theorems for Betti numbers of random simplicial complexes

New lower bounds on χ(Rd)χ(R^d)χ(Rd) for d=8…12d=8 \dots 12d=8…12

The threshold for integer homology in random d-complexes

Inside the critical window for cohomology of random k-complexes

Sharp vanishing thresholds for cohomology of random flag complexes

Topology of random simplicial complexes: a survey

Coboundary expanders

Computational topology for configuration spaces of hard disks

Limit theorems for Betti numbers of random simplicial complexes

Min-type Morse theory for configuration spaces of hard spheres

The fundamental group of random 2-complexes

The fundamental group of random 2-complexes

Random geometric complexes

Sparse stable configurations of hard discs in a box

Points in a triangle forcing small triangles

Topology of random clique complexes

The neighborhood complex of a random graph

See the researcher in context

Building this map preview

New lower bounds on $χ(R^d)$ for $d=8 \dots 12$