Dr. Anna Margarethe Limbach

Dr. Anna Margarethe Limbach

I'm a reasearch mathematician working in the field of combinatorics.

Publications

You can also find my articles on my Google Scholar profile.

Graphon branching processes and frational isomorphism

Published in Arxiv, 2024

In their study of the giant component in inhomogeneous random graphs, Bollobás, Janson, and Riordan introduced a class of branching processes parametrized by a possibly unbounded graphon. We prove that two such branching processes have the same distribution if and only if the corresponding graphons are fractionally isomorphic, a notion introduced by Grebík and Rocha. A different class of branching processes was introduced by Hladký, Nachmias, and Tran in relation to uniform spanning trees in finite graphs approximating a given connected graphon. We prove that two such branching processes have the same distribution if and only if the corresponding graphons are fractionally isomorphic up to scalar multiple. Combined with a recent result of Archer and Shalev, this implies that if uniform spanning trees of two dense graphs have a similar local structure, they have a similar scaling limit. As a side result we give a characterization of fractional isomorphism for graphs as well as graphons in terms of their connected components.

Recommended citation: Hladký, J., Hng, E.K., Limbach, A.M. Graphon branching processes and frational isomorphism. http://dx.doi.org/10.48550/arXiv.2408.02528
Download Paper

Characterising clique convergence for locally cyclic graphs of minimum degree δ ≥ 6

Published in Discrete Mathematics, 2024

The clique graph \(kG\) of a graph \(G\) has as its vertices the cliques (maximal complete subgraphs) of \(G\), two of which are adjacent in \(kG\) if they have non-empty intersection in \(G\). We say that \(G\) is clique convergent if \(k^nG\not\cong k^mG\) for some \(n\neq m\), and that \(G\) is clique divergent otherwise. We completely characterise the clique convergent graphs in the class of (not necessarily finite) locally cyclic graphs of minimum degree \(\delta\geq 6\), showing that for such graphs clique divergence is a global phenomenon, dependent on the existence of large substructures. More precisely, we establish that such a graph is clique divergent if and only if its universal triangular cover contains arbitrarily large members from the family of so-called &quot triangular-shaped graphs &quot.

Recommended citation: Limbach, A.M., Winter, M. Characterising clique convergence for locally cyclic graphs of minimum degree δ ≥ 6. Discrete Mathematics 347 (11), 114144. https://doi.org/10.1016/j.disc.2024.114144
Download Paper

Clique dynamics of locally cyclic graphs with δ ≥ 6

Published in Discrete Mathematics, 2022

We prove that the clique graph operator \(k\) is divergent on a locally cyclic graph \(G\) (i.e. \(N_G(v)\) is a circle) with minimum degree \(\delta(G)=6\) if and only if \(G\) is \(6\)-regular. The clique graph \(kG\) of a graph \(G\) has the maximal complete subgraphs of G as vertices, and the edges are given by non-empty intersections. If all iterated clique graphs of \(G\) are pairwise non-isomorphic, the graph \(G\) is \(k\)-divergent; otherwise, it is \(k\)-convergent. To prove our claim, we explicitly construct the iterated clique graphs of those infinite locally cyclic graphs with \(\delta\geq 6\) which induce simply connected simplicial surfaces. These graphs are \(k\)-convergent if the size of triangular-shaped subgraphs of a specific type is bounded from above. We apply this criterion by using the universal cover of the triangular complex of an arbitrary finite locally cyclic graph with \(\delta=6\), which shows our divergence characterisation.

Recommended citation: Baumeister, M., Limbach, A.M. Clique dynamics of locally cyclic graphs with δ≥ 6. Discrete Mathematics 345.7 (2022): 112873. https://doi.org/10.1016/j.disc.2022.112873
Download Paper

A Note on Edge Weightings Inducing Proper Vertex Colorings

Published in Graphs and Combinatorics, 2018

An edge k-weighting of a graph \(G=(V,E)\) is a function \(l\colon E\to \{1,\ldots,k\}.\) For \(v\in V\) we denote by \(S(v)\) the multiset of weights on edges incident to \(v\). We say that a weighting \(l\) induces a vertex coloring via a function \(f\) if \(f(S(v))\neq f(S(u))\) for all adjacent vertices \(u,v\in V\). One corresponding coloring parameter is \(\chi_f(G)\), the \(f\)-neighbor-distinguishing index. It is the smallest value \(k\) such that a \(k\)-weighting induces a vertex coloring of \(G\) via \(f\). In literature, several functions \(f\), e.g., sums and products, and different additional constraints for the colorings have been studied. Thereby a lot of related coloring parameters arise. In this note, we introduce a class of functions, so-called dispersing functions. We prove bounds for three classes of coloring parameters, which are induced by edge weightings via arbitrary dispersing functions.

Recommended citation: Limbach, A.M., Scheidweiler, R. A Note on Edge Weightings Inducing Proper Vertex Colorings. Graphs and Combinatorics 34, 1269–1277 (2018). https://doi.org/10.1007/s00373-018-1933-5
Download Paper