Papers for

software architecture designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Graph theory links clusters of cycles to small hitting sets

The coarse Erdős-Pósa theorem

Abstract: We prove the coarse Erdős-Pósa conjecture of Georgakopoulos and Papasoglu. Informally, any graph either contains many fat cycles that are pairwise far apart, or there is a small number of bounded radius balls that together hit all of them. To be more precise, if $G$ is a graph with no $q$-fat model of $k \cdot K_3$ for some $q, k \in \mathbb{N}$, then there is a set $X\subseteq V(G)$ of $\mathcal{O}(k\log k)$ vertices such that every $q$-fat model of $K_3$ in $G$ has distance $\mathcal{O}(q)$ from $X$. In another form more closely resembling Manning's theorem that characterises quasi-trees: if $G$ is a graph with no $q$-fat model of $k \cdot K_3$ for some $q, k \in \mathbb{N}$, then $G$ is $\mathcal{O}(q)$-quasi-isometric to a graph $H$ that contains a set $X\subseteq V(H)$ of $\mathcal{O}(k\log k)$ vertices such that $H-X$ is a forest. Bootstrapping this result, we further prove that every graph with no $q$-fat model of $k \cdot K_3$ is quasi-isometric to a graph with no $k \cdot K_3$ minor, where the quasi-isometry can be chosen to only have additive distortion. This result also holds for $k = \infty$. We also obtain an Erdős-Pósa theorem for long induced cycles that are far apart.

Thu 24 SeptDiscrete Mathematics
The gist
Graphs can have many cycles spread out, or a small group of points that touch all such cycles. The authors prove that if a graph does not have many well-separated 'fat' triangles, then a small set of vertices can be found so every fat triangle is near one of those vertices. They also show these graphs are close to simpler tree-like graphs after removing a few vertices. This work confirms a conjecture and connects cycle structures in graphs to their overall shape.
Open → 2609.29414v1