15 May 2024 | James Davies, Robert Hickingbotham, Freddie Illingworth, Rose McCarty
The paper disproves a conjecture by Georgakopoulos and Papasoglu, which posits that a graph with no K-fat H minor is quasi-isometric to a graph with no H minor. The authors construct a counterexample showing that this is not true, and further demonstrate that even graphs with no 2-fat H minor or no H minor cannot be quasi-isometric to graphs with no K-fat H minor. They also show that a weaker version of the conjecture holds: any graph with no K-fat H minor is quasi-isometric to a graph with no 3-fat H minor.
The construction involves a graph $ G_q $ that does not contain a specific graph H as a 3-fat minor and is not q-quasi-isometric to any graph with no 2-fat H minor. The authors also show that $ G_q $ is not q-quasi-isometric to any length space with no $ (2^{-13q^2}) $-fat H minor. These results imply that the conjecture is false even in the case of planar graphs.
The paper also discusses the implications of these results for coarse geometry and graph theory, and proposes weaker versions of the conjecture that might still hold. The authors conclude that while the original conjecture is false, there are natural weaker statements that could allow some results from graph minor theory to be extended to the coarse setting.The paper disproves a conjecture by Georgakopoulos and Papasoglu, which posits that a graph with no K-fat H minor is quasi-isometric to a graph with no H minor. The authors construct a counterexample showing that this is not true, and further demonstrate that even graphs with no 2-fat H minor or no H minor cannot be quasi-isometric to graphs with no K-fat H minor. They also show that a weaker version of the conjecture holds: any graph with no K-fat H minor is quasi-isometric to a graph with no 3-fat H minor.
The construction involves a graph $ G_q $ that does not contain a specific graph H as a 3-fat minor and is not q-quasi-isometric to any graph with no 2-fat H minor. The authors also show that $ G_q $ is not q-quasi-isometric to any length space with no $ (2^{-13q^2}) $-fat H minor. These results imply that the conjecture is false even in the case of planar graphs.
The paper also discusses the implications of these results for coarse geometry and graph theory, and proposes weaker versions of the conjecture that might still hold. The authors conclude that while the original conjecture is false, there are natural weaker statements that could allow some results from graph minor theory to be extended to the coarse setting.