Publications

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

Hypercube drawings with no long plane paths

Published in Arxiv, 2026

We study the existence of plane substructures in drawings of the d-dimensional hypercube graph \(Q_d\). We construct drawings of \(Q_d\) which contain no plane subgraph with more than \(2d−2\) edges, no plane path with more than \(2d−3\) edges, and no plane matching of size more than \(2d−4\). On the other hand, we prove that every rectilinear drawing of Qd with vertices in convex position contains a plane path of length \(d\) (if \(d\) is odd) or \(d−1\) (if \(d\) is even). We also prove that if a graph \(G\) is a plane subgraph of every drawing of \(Q_d\) for a sufficiently large \(d\), then \(G\) is necessarily a forest of caterpillars. Lastly, we give a short proof of a generalization of a result by Alpert et al. [Cong. Numerantium, 2009] on the maximum rectilinear crossing number of \(Q_d\).

Recommended citation: Antić, T., Fuladi, N., Limbach, A.M., Valtr, P. Hypercube drawings with no long plane paths. Arxiv (2026).
Download Paper

When Do Graph Covers Preserve the Clique Dynamics of Infinite Graphs?

Published in Matemática Contemporânea , 2025

We investigate for which classes of (potentially infinite) graphs the clique dynamics is cover stable, i. e., when clique convergence/divergence is preserved under triangular covering maps. We first present an instructive counterexample: a clique convergent graph, which covers a clique divergent graph and which is covered by a clique divergent graph. Based on this, we then focus on local conditions (i. e., conditions on the neighbourhoods of vertices) and show that the following are sufficient to imply cover stability for connected graphs: local girth \(\geq 7\) and local minimum degree \(\geq 2\); being locally cyclic and of minimum degree \(\geq 6\).

Recommended citation: Limbach, A.M., Winter, M. When Do Graph Covers Preserve the Clique Dynamics of Infinite Graphs?. Mat. Contemp. (2025). https://doi.org/10.1007/s44425-025-00021-8
Download Paper

Effective Khovanskii, Ehrhart Polytopes, and the Erdős Multiplication Table Problem

Published in Eurocomb, 2025

Let P(k,n) be the set of products of k factors from the set \(\{1,\ldots , n\}\). In 1955, Erdös posed the problem of determining the order of magnitude of \(\lvert P (2, n)\rvert\) and proved that \(\lvert P (2, n)\rvert = o(n^2 )\) for \(n \to\infty\). In 2015, Darda and Hujdurović asked whether, for each fixed \(n\), \(\lvert P (k, n)\rvert\) is a polynomial in \(k\) of degree \(\pi(n)\) - the number of primes not larger than \(n\). Recently, Granville, Smith and Walker published an effective version of Khovanskii s Theorem. We apply this new result to show, that for each integer \(n\), there is a polynomial \(q_n\) of degree \(\pi(n)\) such that \(\lvert P (k, n)\rvert=q_n(k)\) for each \(k\geq n^2\cdot\left(\prod_{m=1}^{\pi(n)} \log_{p_m}(n)\right)-n+1.\) Moreover, we give an upper estimate of the leading coefficient of \(q_n\).

Recommended citation: Limbach, A.M., Scheidweiler, R., Triesch, E. Effective Khovanskii, Ehrhart Polytopes, and the Erdős Multiplication Table Problem. Eurocomb (2025).
Download Paper

Graphon branching processes and fractional 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

Dr. Anna Margarethe Limbach