Source author record

Anna Gundert

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

ResearcherUnclaimed source record

Discrete Mathematics math.CO math.AT math.SP

Catalog footprint

Research overview

4works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Higher Dimensional Discrete Cheeger Inequalities

For graphs there exists a strong connection between spectral and combinatorial expansion properties. This is expressed, e.g., by the discrete Cheeger inequality, the lower bound of which states that $λ(G) \leq h(G)$ , where $λ(G)$ is the second smallest eigenvalue of the Laplacian of a graph $G$ and $h(G)$ is the Cheeger constant measuring the edge expansion of $G$ . We are interested in generalizations of expansion properties to finite simplicial complexes of higher dimension (or uniform hypergraphs). Whereas higher dimensional Laplacians were introduced already in 1945 by Eckmann, the generalization of edge expansion to simplicial complexes is not straightforward. Recently, a topologically motivated notion analogous to edge expansion that is based on $\mathbb{Z}_2$ -cohomology was introduced by Gromov and independently by Linial, Meshulam and Wallach. It is known that for this generalization there is no higher dimensional analogue of the lower bound of the Cheeger inequality. A different, combinatorially motivated generalization of the Cheeger constant, denoted by $h(X)$ , was studied by Parzanchevski, Rosenthal and Tessler. They showed that indeed $λ(X) \leq h(X)$ , where $λ(X)$ is the smallest non-trivial eigenvalue of the ( $(k-1)$ -dimensional upper) Laplacian, for the case of $k$ -dimensional simplicial complexes $X$ with complete $(k-1)$ -skeleton. Whether this inequality also holds for $k$ -dimensional complexes with non-complete $(k-1)$ -skeleton has been an open question. We give two proofs of the inequality for arbitrary complexes. The proofs differ strongly in the methods and structures employed, and each allows for a different kind of additional strengthening of the original result.

preprint2015arXiv

On Eigenvalues of Random Complexes

We consider higher-dimensional generalizations of the normalized Laplacian and the adjacency matrix of graphs and study their eigenvalues for the Linial-Meshulam model $X^k(n,p)$ of random $k$ -dimensional simplicial complexes on $n$ vertices. We show that for $p=Ω(\log n/n)$ , the eigenvalues of these matrices are a.a.s. concentrated around two values. The main tool, which goes back to the work of Garland, are arguments that relate the eigenvalues of these matrices to those of graphs that arise as links of $(k-2)$ -dimensional faces. Garland's result concerns the Laplacian; we develop an analogous result for the adjacency matrix. The same arguments apply to other models of random complexes which allow for dependencies between the choices of $k$ -dimensional simplices. In the second part of the paper, we apply this to the question of possible higher-dimensional analogues of the discrete Cheeger inequality, which in the classical case of graphs relates the eigenvalues of a graph and its edge expansion. It is very natural to ask whether this generalizes to higher dimensions and, in particular, whether the higher-dimensional Laplacian spectra capture the notion of coboundary expansion - a generalization of edge expansion that arose in recent work of Linial and Meshulam and of Gromov. We show that this most straightforward version of a higher-dimensional discrete Cheeger inequality fails, in quite a strong way: For every $k\geq 2$ and $n\in \mathbb{N}$ , there is a $k$ -dimensional complex $Y^k_n$ on $n$ vertices that has strong spectral expansion properties (all nontrivial eigenvalues of the normalised $k$ -dimensional Laplacian lie in the interval $[1-O(1/\sqrt{n}),1+O(1/\sqrt{n})]$ ) but whose coboundary expansion is bounded from above by $O(\log n/n)$ and so tends to zero as $n\rightarrow \infty$ ; moreover, $Y^k_n$ can be taken to have vanishing integer homology in dimension less than $k$ .

preprint2015arXiv

On Topological Minors in Random Simplicial Complexes

For random graphs, the containment problem considers the probability that a binomial random graph $G(n,p)$ contains a given graph as a substructure. When asking for the graph as a topological minor, i.e., for a copy of a subdivision of the given graph, it is well-known that the (sharp) threshold is at $p=1/n$ . We consider a natural analogue of this question for higher-dimensional random complexes $X^k(n,p)$ , first studied by Cohen, Costa, Farber and Kappeler for $k=2$ . Improving previous results, we show that $p=Θ(1/\sqrt{n})$ is the (coarse) threshold for containing a subdivision of any fixed complete $2$ -complex. For higher dimensions $k>2$ , we get that $p=O(n^{-1/k})$ is an upper bound for the threshold probability of containing a subdivision of a fixed $k$ -dimensional complex.

preprint2011arXiv

Not All Saturated 3-Forests Are Tight

A basic statement in graph theory is that every inclusion-maximal forest is connected, i.e. a tree. Using a definiton for higher dimensional forests by Graham and Lovasz and the connectivity-related notion of tightness for hypergraphs introduced by Arocha, Bracho and Neumann-Lara in, we provide an example of a saturated, i.e. inclusion-maximal 3-forest that is not tight. This resolves an open problem posed by Strausz.

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.

Anna Gundert

Research overview

Is this your work?

4 publications

Higher Dimensional Discrete Cheeger Inequalities

On Eigenvalues of Random Complexes

On Topological Minors in Random Simplicial Complexes

Not All Saturated 3-Forests Are Tight

See the researcher in context

Building this map preview