Research
////////////////////////////////////////////

My research interests include:

stochastic topology (various models of random cell complexes)

topological statistical mechanics (configuration spaces of particles, homological percolation)

geometric group theory (random groups, especially hyperbolicity and Kazhdan's Property (T))

random graphs (topological and geometric properties, spectral expansion)

graph coloring and graph homomorphisms (obstructions to graph maps from statistical physics and topology)

discrete geometry (unit-distance graphs, disk packing)

My research is supported in part by the National Science Foundation (NSF). I am currently the PI on an NSF-DMS grant on "Stochastic topology and topological statistical mechanics" (2020–2023), and an RTG grant on "Algebraic Topology and its Applications" (2016–2023).

Most of my papers are available in preprint form on the arXiv.

Preprints

Benjamin Braun, Kaitlin Bruegge, Matthew Kahle. "Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering." (submitted). arXiv:2204.07239.

+–

Abstract
Symmetric edge polytopes are lattice polytopes associated with finite simple graphs that are of interest in both theory and applications. We investigate the facet structure of symmetric edge polytopes for various models of random graphs. For an Erdős-Renyi random graph, we identify a threshold probability at which with high probability the symmetric edge polytope shares many facet-supporting hyperplanes with that of a complete graph. We also investigate the relationship between the Watts-Strogatz clustering coefficient and the number of facets for a graph with either a fixed number of edges or a fixed degree sequence. We use well-known Markov Chain Monte Carlo sampling methods to generate empirical evidence that for a fixed degree sequence, higher Watts-Strogatz clustering in a connected graph corresponds to higher facet numbers in the associated symmetric edge polytope. arXiv:2204.07239.

Paul Duncan, Matthew Kahle, Benjamin Schweinhart. "Homological percolation on a torus: plaquettes and permutohedra." (submitted). arXiv:2011.11903.

+–

Abstract
We study higher-dimensional homological analogues of bond percolation on a square lattice and site percolation on a triangular lattice.

By taking a quotient of certain infinite cell complexes by growing sublattices, we obtain finite cell complexes with a high degree of symmetry and with the topology of the torus $\T^d$. When random subcomplexes induce nontrivial $i$-dimensional cycles in the homology of the ambient torus, we call such cycles \emph{giant}. We show that for every $i$ and $d$ there is a sharp transition from nonexistence of giant cycles to giant cycles spanning the homology of the torus.

We also prove convergence of the threshold function to a constant in certain cases. In particular, we prove that $p_c=1/2$ in the case of middle dimension $i=d/2$ for both models. This gives finite-volume high-dimensional analogues of Kesten's theorems that $p_c=1/2$ for bond percolation on a square lattice and site percolation on a triangular lattice. arXiv:2011.11903.

Sukhada Fadnavis, Matthew Kahle, Francisco Martinez-Figueroa. "Warmth and mobility of random graphs." (revised in 2021 and submitted). arXiv:1009.0792.

+–

Abstract
A graph homomorphism from the rooted $d$-branching tree $\phi: T^d \to H$ is said to be cold if the values of $\phi$ for vertices arbitrarily far away from the root can restrict the value of $\phi$ at the root. Warmth is a graph parameter that measures the non-existence of cold maps. We study warmth of random graphs $G(n,p)$, and for every $d \ge 1$, we exhibit a nearly-sharp threshold for the existence of cold maps. As a corollary, for $p=O(n^{-\alpha})$ warmth of $G(n,p)$ is concentrated on at most two values. As another corollary, a conjecture of Lovász relating mobility to chromatic number holds for ``almost all'' graphs. Finally, our results suggest new conjectures relating graph parameters from statistical physics with graph parameters from equivariant topology. arXiv:1009.0792.

Papers

Hannah Alpert, Matthew Kahle, Robert MacPherson. "Asymptotic Betti numbers for hard squares in the homological liquid regime." to appear in International Mathematics Research Notices (IMRN). arXiv:2207.13139.

+–

Abstract
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 $\left( \frac{n}{pq}, \frac{j}{pq} \right)$ 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 identified in \cite{ABKMS20}, 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. arXiv:2207.13139.

Hannah Alpert, Ulrich Bauer, Matthew Kahle, Robert MacPherson, Kelly Spendlove. "Homology of configuration spaces of hard squares in a rectangle." to appear in Algebraic & Geometric Topology. arXiv:2010.14480.

+–

Abstract
We study the configuration spaces $C(n,p,q)$ of $n$ labeled hard squares in a $p \times q$ rectangle, a generalization of the well-known ``15 Puzzle''. Our main interest is in the topology of these spaces. Our first result is to describe a cubical cell complex and prove that is homotopy equivalent to the configuration space. We then focus on determining for which $n$, $j$, $p$, and $q$ the homology group $H_j [ C(n,p.q) ]$ is nontrivial. We prove three homology-vanishing theorems, based on discrete Morse theory on the cell complex. Then we describe several explicit families of nontrivial cycles, and a method for interpolating between parameters to fill in most of the picture for ``large-scale'' nontrivial homology. arXiv:2010.14480.

Matthew Kahle, Andrew Newman. "Topology and geometry of random 2-dimensional hypertrees." Discrete & Computational Geometry. Jan 2022. arXiv:2004.13572.

+–

Abstract
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 aspherical, i.e.\ that it has a contractible universal cover. We also show that with high probability the fundamental group $\pi_1(T)$ is hyperbolic and has cohomological dimension $2$.
arXiv:2004.13572.

Download:

.pdf of near final version

Matthew Kahle, Elliot Paquette, Érika Roldán. "Topology of random 2-dimensional cubical complexes." Forum of Mathematics, Sigma. Nov 2021. arxiv:2001.07812.

+–

Abstract
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 exhibits a sharp threshold $p=1/2$ for homology vanishing as $n \to \infty$. This is a $2$-dimensional analogue of the Burtin and Erd\H{o}s--Spencer theorems characterizing the connectivity threshold for random graphs on the $1$-skeleton of the $n$-dimensional cube.

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.
arxiv:2001.07812.

Hannah Alpert, Matthew Kahle, Robert MacPherson. "Configuration spaces of disks in an infinite strip." Journal of Applied and Computational Topology. May 2021. arXiv:1908.04241.

+–

Abstract
We study the topology of the configuration space $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 inclusion $i$ into the configuration space of $n$ points in the plane $C(n,\mathbb{R}^2)$ induces an isomorphism on homology $i_{*} : H_j [C(n,w) ] \to 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, if $w$ and $j$ are fixed then $\beta_j[C(n,w)]$ is a polynomial of degree $2j$ in $n$.

On the other hand, we show that $w$ and $j$ are fixed and $2 \le w \le j+1$, then $\beta_j [ C(n,w) ]$ grows exponentially fast with $n$. Most of our work is in carefully estimating $\beta_j [ C(n,w) ]$ in this regime.

We also illustrate for every $n$ the "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. arXiv:1908.04241.

Download:

AKM.pdf

Matthew Kahle, Francisco Martinez-Figueroa. "The chromatic number of random Borsuk graphs." Random Structures & Algorithms. Nov 2019. arXiv:1901.08488.

+–

Abstract
We study a model of random graph, where vertices are $n$ i.i.d.\ uniform random points on the unit sphere $S^d$ in $\mathbb{R}^{d+1}$, and a pair of vertices is connected if the distance between them is at least $2- \epsilon$. We are mostly interested in the chromatic number of this graph as $n$ tends to infinity.

It is not too hard to see that if $\epsilon > 0$ is small and fixed, then the chromatic number is $d+2$ with high probability. We show that this holds even if $\epsilon \to 0$ slowly enough. We quantify the rate at which $\epsilon$ can tend to zero and still have the same chromatic number, up to a constant factor. The proof depends on combining topological methods (namely the Lyusternik--Schnirelman--Borsuk theorem) with geometric probability arguments. The rate we obtain is best possible, up to a constant factor --- if $\epsilon \to 0$ faster than this, we show that the graph is $(d+1)$-colorable with high probability. arXiv:1901.08488.

Matthew Kahle, Érika Roldán. "Polyominoes with maximally many holes." Geombinatorics. Aug 2019. arXiv:1807.10231.

+–

Abstract
What is the maximum number of holes that a polyomino with $n$ tiles can enclose? Call this number $f(n)$. We show that if $n_k = \left( 2^{2k+1} + 3 \cdot 2^{k+1}+4 \right) / 3$ and $h_k = \left( 2^{2k}-1 \right) /3$, then $f(n_k) = h_k$ for $k \ge 1$. We also give nearly matching upper and lower bounds for all large $n$, showing as a corollary that $f(n) = \left(1/2- o(1) \right) n/2 $.
arXiv:1807.10231.

Download:

.pdf

Matthew Kahle, Minghao Tian, Yusu Wang. "Local Cliques in ER-Perturbed Random Geometric Graphs." 30th International Symposium on Algorithms and Computation (ISAAC 2019). Jun 2019. arXiv:1810.08383.

+–

Abstract
We study a random graph model where one adds Erdős–Rényi (ER) type perturbation to a random geometric graph. More precisely, assume that $G^*&_{\chi}$ is a random geometric graph sampled from a nice measure on a metrix space $\chi=(X,d)$. An ER-perturbed random geometric graph $\hat{G}(p,q)$ is generated by removing each existing edge from $G^*_{\chi}$ with probability $p$, while inserting each non-existent edge to $G^*_{\chi}$ with probability $q$. We consider a localized version of clique number for $\hat{G}(p,q)$. Specifically, we study the edge clique number for each edge in a graph, defined as the size of the largest clique in the graph containing that edge. We show that the edge clique number presents two fundamentally different types of behaviors in $\hat{G}(p,q)$, depending on which type of randomness it is generated from.

As an application of the above results, we show that by a simple filtering process based on the edge clique number, we can recover the shortest-path metric of the random geometric graph $G^*_{\chi}$ within a multiplicative factor of $3$ from the ER-perturbed observed graph $\hat{G}(p,q)$ with high probability, for a significantly wider range of insertion probability $q$ than in previous work. arXiv:1810.08383.

Download:

LIPIcs-ISAAC-2019-29.pdf

Christopher Hoffman, Matthew Kahle, Elliot Paquette. "Spectral gaps of random graphs and applications." International Mathematics Research Notices (IMRN). May 2019. arXiv:1201.0425.

+–

Abstract
We study the spectral gap of the Erdős–Rényi random graph through the connectivity threshold. In particular, we show that for any fixed $\delta > 0$, if $$p \ge \frac{(1/2 + \delta) \log n}{n},$$
then the normalized graph Laplacian of an \ER graph has all of its nonzero eigenvalues tightly concentrated around $1$. This is a strong expander property.

We estimate both the decay rate of the spectral gap to $1$ and the failure probability, up to a constant factor. We also show that the $1/2$ in the above is optimal, and that if $p = \frac{c \log n}{n}$ for $c < 1/2,$ then there are eigenvalues of the Laplacian restricted to the giant component that are separated from $1.$

We then describe several applications of our spectral gap results to stochastic topology and geometric group theory. These all depend on Garland's method \cite{Garland}, a kind of spectral geometry for simplicial complexes. The following can all be considered to be higher-dimensional expander properties.

First, we exhibit a sharp threshold for the fundamental group of the Bernoulli random $2$-complex to have Kazhdan's property (T). We also obtain slightly more information and can describe the large-scale structure of the group just before the (T) threshold. In this regime, the random fundamental group is with high probability the free product of a (T) group with a free group, where the free group has one generator for every isolated edge. The (T) group plays a role analogous to that of a ``giant component'' in percolation theory.

Next, we give a new, short, self-contained proof of the Linial--Meshulam--Wallach theorem \cite{LM06,MW09}, identifying the cohomology-vanishing threshold of Bernoulli random $d$-complexes. Since we use spectral techniques, it only holds for $\Q$ or $\R$ coefficients rather than finite field coefficients, as in \cite{LM06} and \cite{MW09}. But it is sharp from a probabilistic point of view, providing for example, hitting time type results and limiting Poisson distributions inside the critical window. It is also a new method of proof, circumventing the combinatorial complications of cocycle counting. Similarly, results in an earlier preprint version of this article were already applied in \cite{flag} to obtain sharp cohomology-vanishing thresholds in every dimension for the random flag complex model.
arXiv:1201.0425.

Download:

spectral gaps.pdf

Matthew Kahle. "Branko Grünbaum in many dimensions." Geombinatorics. Jan 2019. arXiv:1901.08622.

+–

Abstract
This survey article collects a few of my favorite open problems of Branko Grünbaum.
arXiv:1901.08622.

Matthew Kahle, Frank Lutz, Andrew Newman, Kyle Parsons. "Cohen–Lenstra heuristics for torsion in homology of random complexes." Experimental Mathematics. Jun 2018. arXiv:1710.05683.

+–

Abstract
We study torsion in homology of the random $d$-complex $Y \sim Y_d(n,p)$ experimentally. Our experiments suggest that there is almost always a moment in the process where there is an enormous burst of torsion in homology $H_{d-1}(Y)$. This moment seems to coincide with the phase transition identified by Linial and Peled, where cycles in $H_d(Y)$ first appear with high probability.

Our main study is the limiting distribution on the $q$-part of the torsion subgroup of $H_{d-1}(Y)$ for small primes $q$. We find strong evidence for a limiting Cohen–Lenstra distribution, where the probability that the $q$-part is isomorphic to a given $q$-group $H$ is inversely proportional to the order of the automorphism group $|\mbox{Aut}(H)|$.

We also study the torsion in homology of the uniform random $\mathbb{Q}$-acyclic $2$-complex. This model is analogous to a uniform spanning tree on a complete graph, but more complicated topologically since Kalai showed that the expected order of the torsion group is exponentially large in $n^2$. We give experimental evidence that in this model also, the torsion is Cohen–Lenstra distributed in the limit.
arXiv:1710.05683.

Omer Bobrowski, Matthew Kahle. "Topology of random geometric complexes: a survey." Journal of Applied and Computational Topology. Jun 2018. arXiv:1409.4734.

+–

Abstract
In this expository article, we survey the rapidly emerging area of random geometric simplicial complexes.
arXiv:1409.4734.

Dominic Dotterrer, Larry Guth, Matthew Kahle. "2-complexes with large 2-girth." Discrete & Computational Geometry. Apr 2018. arxiv:1509.03871.

+–

Abstract
The 2-girth of a 2-dimensional simplicial complex X is the minimum size of a non-zero 2-cycle in $H_2(X,\mathbb{ℤ}/2)$. We consider the maximum possible girth of a complex with $n$ vertices and $m$ 2-faces. If $m=n^{2+\alpha}$ for $\alpha<1/2,$ then we show that the $$2-girth is at most $n^{2−2 \alpha}$ and we prove the existence of complexes with $2$-girth at least c_{\alpha, \epsilon} n^{2−2 \alpha - \epsilon}$. On the other hand, if $\alpha >1/2$, the $2$-girth is at most $C_{\alpha}$. So there is a phase transition as $\alpha$ passes $1/2$.
Our results depend on a new upper bound for the number of combinatorial types of triangulated surfaces with $v$ vertices and $f$ faces. arxiv:1509.03871.

Matthew Kahle. "Random simplicial complexes." Book chapter for Handbook of Discrete & Computational Geometry (3rd edition). Nov 2017. arXiv:1607.07069.

+–

Abstract
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. arXiv:1607.07069.

Omer Bobrowski, Matthew Kahle, Primoz Skraba. "Maximally Persistent Cycles in Random Geometric Complexes." Annals of Applied Probability. Oct 2017. arXiv:1509.04347.

+–

Abstract
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 Čech 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 persistence of order $$ \Theta \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 Čech filtration.
arXiv:1509.04347.

Matthew Kahle, Minghao Tian, Yusu Wang. "On the clique number of noisy random geometric graphs." Random Structures & Algorithms. Feb 2023. arXiv:2208.10558.

+–

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

Christopher Hoffman, Matthew Kahle, Elliot Paquette. "The threshold for integer homology in random d-complexes." Discrete & Computational Geometry. May 2017. arXiv:1308.6232.

+–

Abstract
Let $Y \sim 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; \mathbb{Z})$ is less than $80d \log n / n$. This bound is tight, up to a constant factor. arXiv:1308.6232.

Matthew Kahle, Elizabeth Meckes. "Erratum: Limit theorems for Betti numbers of random simplicial complexes." Homology, Homotopy and Applications. Jan 2016. arXiv:1501.03759.

+–

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

Matthew Kahle, Boris Pittel. "Inside the critical window for cohomology of random k-complexes." Random Structures & Algorithms . Jan 2016. arXiv:1301.1324.

+–

Abstract
We prove sharper versions of theorems of Linial--Meshulam and Meshulam--Wallach which describe the behavior for $(\mathbb{Z}/2)$-cohomology of a random $k$-dimensional simplicial complex within a narrow transition window. In particular, we show that within this window the Betti number $\beta^{k-1}$ 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. arXiv:1301.1324.

Matthew Kahle, Birra Taha. "New lower bounds on $\chi(R^d)$ for $d=8 \dots 12$." Geombinatorics . Jul 2015. arXiv 1409:1278.

+–

Abstract
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.
arXiv 1409:1278.

Download:

newlower-20140817.pdf

Matthew Kahle. "Topology of random simplicial complexes: a survey." AMS Contemporary Volumes in Mathematics, Algebraic Topology: Applications and New Directions. Nov 2014. arXiv:1301.7165.

+–

Abstract
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. arXiv:1301.7165.

Matthew Kahle. "Sharp vanishing thresholds for cohomology of random flag complexes." Annals of Mathematics. Aug 2014. arXiv:1207.0149.

+–

Abstract
We exhibit a sharp threshold for vanishing of rational cohomology in random flag complexes, providing a generalization of the Erdős–Rényi theorem. As a corollary, almost all $d$-dimensional flag complexes have nontrivial (rational, reduced) homology only in middle degree $\lfloor d/2 \rfloor$.
arXiv:1207.0149.

Download:

(journal version)

Ayat Ababneh, Matthew Kahle. "Maximal persistence in random clique complexes." Journal of Applied and Computational Topology. Jul 2023. arXiv:2209.05713.

+–

Abstract
We study the persistent homology of an Erd\H{o}s--R\'enyi 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 $\sigma$ 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 \v{C}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}$.
arXiv:2209.05713.

Michael Davis, Matthew Kahle. "Random graph products of finite groups are rational duality groups." Journal of Topology. Feb 2014. arXiv:1210.4577.

+–

Abstract
Given a Bernoulli random graph $G \sim G(n,p)$, we determine various facts about the cohomology of graph products of groups for the graph $G$. In particular, the random graph product of a sequence of finite groups is a rational duality group with probability tending to $1$ as $n \to \infty$. This includes random right angled Coxeter groups as a special case.
arXiv:1210.4577.

Download:

DK12.pdf

Matthew Kahle, Elizabeth Meckes. "Limit theorems for Betti numbers of random simplicial complexes." Homology, Homotopy and Applications. May 2013. arXiv:1009.4130.

+–

Abstract
There have been several recent articles studying homology of various types of random simplicial complexes. Some theorems have concerned thresholds for vanishing of homology, and in others estimates for the expectations of the Betti numbers. However little seems known so far about limiting distributions.

In this article we establish Poisson and normal approximation theorems for Betti numbers of different kinds of random simplicial complex: Erdos-Renyi random clique complexes, random Vietoris-Rips complexes, and random Cech complexes. These results may be of practical interest in topological data analysis. arXiv:1009.4130.

Yuliy Baryshnikov, Peter Bubenik, Matthew Kahle. "Min-type Morse theory for configuration spaces of hard spheres." International Mathematics Research Notices (IMRN). Feb 2013. arxiv:1108.3061.

+–

Abstract
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. arxiv:1108.3061.

Dominic Dotterrer, Matthew Kahle. "Coboundary expanders." Journal of Topology and Analysis. Nov 2012. arXiv:1012.5316.

+–

Abstract
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. arXiv:1012.5316.

Matthew Kahle. "Sparse locally-jammed disk packings." Annals of Combinatorics. Oct 2012.

+–

Abstract
We construct arbitrarily sparse locally-jammed packings of non- overlapping congruent disks in various finite area regions — in particular, we give constructions for the square, hexagon, and for certain flat tori.

Download:

.pdf (updated 2/2012)

Gunnar Carlsson, Jackson Gorham, Matthew Kahle, Jeremy Mason. "Computational topology for configuration spaces of hard disks." Physical Review E. Jan 2012. arXiv:1108.5719.

+–

Abstract
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. arXiv:1108.5719.

Download:

(final version)

Matthew Kahle. "Random geometric complexes." Discrete & Computational Geometry. Jan 2011. arXiv:0910.1649.

+–

Abstract
We study the expected topological properties of Cech and Vietoris-Rips complexes built on i.i.d. random points in $\mathbb{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. arXiv:0910.1649.

Download:

rgc-dcg.pdf

Eric Babson, Christopher Hoffman, Matthew Kahle. "The fundamental group of random 2-complexes." Journal of the American Mathematical Society. Jan 2011. arXiv:0711.2704.

+–

Abstract
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 roughly $p = n^{-1/2}$. (The exponent is sharp.) 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 -\epsilon})$ 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. arXiv:0711.2704.

Download:

journal version

Matthew Kahle. "Points in a triangle forcing small triangles." Geombinatorics. Oct 2009. arXiv:0811.2449.

+–

Abstract
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 \to \infty$.

[NOTE: Conjecture 2.6 fails --- the optimal value is $3 - 2 \sqrt{2}$ not $1/6$.] arXiv:0811.2449.

Download:

points_in_a_triangle.pdf

Matthew Kahle. "Topology of random clique complexes." Discrete Math. Aug 2009. arXiv:0605536.

+–

Abstract
In a seminal paper, Erdős and Rényi identified the threshold for connectivity of the random graph $G(n,p)$. In particular, they showed that if $p \gg \log n / n$ then $G(n,p)$ is almost always connected, and if $p \ll \log n /n$ then $G(n,p)$ is almost always disconnected, as $n \to \infty$.
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 Erdős–Rényi 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 $k$th 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. arXiv:0605536.

Download:

journal version

Matthew Kahle. "The neighborhood complex of a random graph." Journal of Combinatorial Theory, Series A. Sep 2007. arXiv:math/0512077.

+–

Abstract
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 Lovász that if $N[G]$ is $k$-connected, then the chromatic number of $\chi(G) \ge 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. arXiv:math/0512077.

Download:

neighborhood.pdf

Matthew Kahle. "Scatters, unavoidable shapes, and crystallization." Geombinatorics. Oct 2005.

+–

Abstract
We study $(n,k)$-scatters, which are regular $n$-gon tiles arranged so that each tile shares edges with at least $k$ others. To measure how much freedom there is in arranging scatters, we ask which shapes are unavoidable. It turns out that for a few choices of $(n,k)$ there are infinite unavoidable shapes, but otherwise they are finite. We discuss the infinite case as an analogue of crystallization.

The main result here is that besides the trivial situations when there’s a unique scatter, there are only four instances of this. Scatters crystallize nontrivially just when $(n, k) = (5, 3)$, $(7, 3)$, $(10, 4)$, or $(14, 4)$.

Download:

scatters.pdf

Research////////////////////////////////////////////

Preprints

Papers

Research
////////////////////////////////////////////