CS Paper Radar

Linking invariants of spatial graphs

E. Alkin, Yu. Khromin, A. Skopenkov

cs.CG math.GTmath.COmath.HO ·submitted 2026-08-16 17:03 UTC · v1
theory

Abstract

We recall definitions of linking numbers and Wu--Simon numbers for spatial graphs. We expose a `converse' to the Conway--Gordon--Sachs theorem (i.e. description of linking functions for embeddings $K_6\to\mathbb{R}^3$), and some results on Wu--Simon numbers. We conjecture and discuss a generalization of the Conway--Gordon--Sachs theorem to multiple linking. The exposition is based on plane diagrams, so no knowledge of spatial geometry is required.

Comment
17 pages (English) + 14 pages (Russian); many figures. The paper belongs to math.GT because the most closely related papers are arXiv:2006.07342 [math.GT], arXiv:2001.01472 [math.GT], arXiv:2410.09860 [math.GT], arXiv:1805.10237 [math.GT], arXiv:2205.01013 [math.GT]

Closest papers

Nearest neighbours by meaning across the whole index.

Counterexamples to the Strong Roberson Conjecture

cs.DM math.COcs.LO ·2026-10-02 ·Arnar Á. Kristjánsson
similarity 0.53
Abstract · 24 pages. v2: expanded introduction, related work and conclusion; improved exposition throughout; smaller explicit counterexamples obtained

We refute the Strong Roberson Conjecture, which asserts that adding any graph outside a graph class closed under minors and disjoint unions strictly increases the distinguishing power of homomorphism counts from that class. More precisely, we construct connected graphs $H$ for which homomorphism counts from graphs excluding $H$ as a minor determine the number of homomorphisms from $H$ to any target graph. We also refute the analogous conjecture with immersions in place of minors. The proof introduces a method for deriving exact homomorphism count dependence from modular equivalences. We obtain these modular equivalences for infinitely many primes using prime-order automorphisms and the corresponding orbit quotients. We complete the refutations by proving that suitable circulant graphs with two jump lengths and related cubic bipartite graphs exclude their corresponding orbit quotients as minors and immersions, respectively.

0.44

An approximate cactus-decomposition for vertex-connectivity

cs.DM math.CO ·2026-11-01 ·Romain Bourneuf, Johannes Carmesin, Jan Kurkofka, Tim Planken
theory similarity 0.51
Abstract

The classical cactus theorem of Dinitz, Karzanov and Lomonosov from 1976 states that the minimum edge-cuts of a connected graph are displayed by a cactus. For vertex-separations, Tutte's theorem gives an exact cactus-decomposition for connectivity $2$, but exact cactus-decompositions fail for higher connectivity. Extending earlier approximate cactus-decomposition results for connectivities $3$ and $4$ by Carmesin and Kurkofka [FOCS 2023] and Kurkofka and Planken [SODA 2026] to all connectivities, we prove that for every $k\in\mathbb{N}$ there is a constant $d=d(k)$ such that every $k$-connected graph $G$ admits a cactus-decomposition displaying $k$-separations such that every $k$-separation of $G$ has edit-distance at most $d$ to a displayed separation. Our proof develops tools that may be useful beyond this result. The first is a three-dimensional version of the classical corner-diagram method, which we use to show that triples of crossing $k$-separations have a controlled two-dimensional behaviour. The second is a covering-space approach for studying local crossing patterns from a global perspective. Third, we advance the theory of flowers, which originated in matroid theory.

0.30

KnottedGraph: Scalable knotted-graph topology for scientific and mathematical discovery

cs.MS cs.CGcs.SCmath.GT+1 ·2026-09-25 ·Hakan Akgün, Xianquan Yan, Kehan Liu, Zhaoyun Chen, Ching Hua Lee
code/data similarity 0.51
Abstract · 40 pages, 15 figures, 4 tables; includes Supplementary Information. Source code, documentation, workflows and data are available at https://…

Scientific data span heterogeneous structures, including coordinates, networks, surfaces, volumes and fields, yet their topology can be quantified within a common framework through graph connectivity, cycle structure, genus and spatial embedding. Graph- and homology-based summaries do not determine spatial embedding, while standard knot and link polynomials require extensions to accommodate branching graphs. Here, we introduce KnottedGraph, a computational framework that converts such scientific representations to knotted graphs that retain graph connectivity and spatial embedding together. It constructs projected diagrams and PD codes, enabling various topological analyses, including Yamada-polynomial evaluation for topological classification. For scalable exact evaluation, it combines partial resolutions that leave the same unresolved connections and optimizes their processing order; the resulting algorithm is verified against published topological invariants of knotted graphs with up to 500 crossings. This scalability enables us to introduce an LLM-assisted mathematical-discovery methodology, in which computational topological data generated across knotted-graph families are used to identify candidate closed-form formulas. With this approach, we identify analytical Yamada-polynomials for generic graph motif families exhibiting Abelian and non-Abelian word sequences. Together, these scalable capabilities make knotted-graph topology computationally accessible across scientific domains, enabling large-scale classification and introducing a route from topological data to LLM-assisted AI4Math discovery.

0.38

Fixed-Radius Neighbourhoods in Three-Dimensional Unit-Cube Graphs

cs.CG math.CO ·2026-11-04 ·Guangjian Zhang
theory similarity 0.50
Abstract · 30 pages

We prove Conjecture 4 of Chan, Chang, Gao, Kisfaludi-Bak, Le, and Zheng (SoCG 2026): for every fixed integer $r\ge0$, the radius-$r$ neighbourhoods of a unit-cube graph in $\mathbb{R}^3$ have bounded VC-dimension. Our bound is $2^{2^{O(r)}}$, independent of the number of vertices. The main ingredient is a VC-dimension bound for reachability through arbitrary fixed-length sequences of three-dimensional generalized dominance relations. Its proof uses groups ordered in two coordinates, with neighbouring groups acting as barriers that preserve this invariant when one layer is removed. Combining these bounds with the existing interval-representation framework, we obtain a Las Vegas algorithm that, for every fixed integer $Δ\ge1$, decides whether a graph given by $n$ cube centres has diameter at most $Δ$ in expected $O_Δ(n^{2-\varepsilon_Δ})$ time, for an explicit constant $\varepsilon_Δ>0$. Finally, for every integer $r\ge7$, we construct unit-cube graphs with rational centres whose radius-$r$ neighbourhoods have VC-dimension $Ω(r^3)$.

0.27

Realizing graph automorphisms as geometric symmetries of straight line drawings

cs.CG math.COmath.GR ·2026-10-26 ·Saul D. Freedman, Melissa Lee, Dragan Marušič, Tomaž Pisanski
similarity 0.50
Abstract · 20 pages, comments welcome

Given a finite graph $G$, we characterize the automorphisms and automorphism groups of $G$ that can be realized as geometric symmetries and symmetry groups of straight line drawings of $G$ in the plane. In doing so, we correct a previous version of this characterization from the literature. As an application, we show that the graphs recently constructed by the first two authors to disprove the Polycirculant Conjecture, which have orders $16{,}464^k$ for each positive integer $k$, are the first known vertex-transitive graphs with no non-trivial realizable geometric symmetries. We also construct infinite families of graphs that exhibit all possible kinds of geometric symmetry.

0.22

Every $k$-Quasi-Planar Graph Has Linearly Many Edges

cs.CG math.CO ·2026-11-01 ·Ankan Sadhu
theory similarity 0.50
Abstract · 6 pages, 1 figure

For every fixed integer $k\ge2$, we prove that every simple graph on $n$ vertices drawn in the plane with no $k$ pairwise crossing edges has at most $C_kn$ edges, where $C_k$ depends only on $k$. We allow any finite number of proper crossings between two edges, including edges with a common endpoint. For $n\ge3$, removing a small disk around each vertex turns the drawing into a family of arcs on a sphere with $n$ boundary circles. Each arc joins two different boundary circles, and different edges have different unordered pairs of endpoint circles. The arcs are therefore essential and pairwise nonhomotopic, with endpoints allowed to move along their boundary circles during a homotopy. Any family of pairwise intersecting lifts to the universal cover projects to distinct graph edges that cross pairwise. Its size is consequently at most $k-1$. Beeker and Lazarovich's theorem on surface patterns then bounds the number of arcs. Their estimate is linear in the size of a triangulation, and an explicit triangulation of the $n$-holed sphere has linearly many edges and triangles.

0.54

Potatoes and Onions

cs.DM math.CO ·2026-10-14 ·Marcin Briański, Meike Hatzel, Karolina Okrasa, Michał Pilipczuk
top venuetheory similarity 0.49
Abstract · This work has been accepted for presentation at SODA 2027

The first major step in the theory of graph minors of Robertson and Seymour was the grid theorem, a fundamental duality result describing that any graph of sufficiently high treewidth must contain a large grid as a minor. Since this pioneering work, multiple grid theorems have been established in structural graph theory, linking various width parameters of combinatorial objects with the non-existence of grid-like obstructions. In particular, Kawarabayashi and Kreutzer [STOC'15] proved a variant of the grid theorem for directed graphs that links directed treewidth with the non-existence of topological minors of large cylindrical walls. On the other hand, to study immersions of undirected graphs $-$ another containment relation that focuses on edge-disjointness, rather than vertex-disjointness $-$ Wollan [JCTB'15] introduced a parameter, tree-cutwidth, and proved that it is dual to immersions of large walls. In this work, we present a version of Wollan's parameter for directed graphs, the directed tree-cutwidth. The main result is a grid theorem for directed tree-cutwidth, establishing that it is dual to directed immersions of large cylindrical walls.

0.50

Computations of the slice genus and the unknotting number of links via machine learning

cs.LG math.GTstat.ML ·2026-10-07 ·Yutong Dai, Oliver Hayman, András Juhász, Ludovico Morellato
unusual similarity 0.49
Abstract · 72 pages, 34 figures

Links are disjoint unions of circles smoothly embedded in $S^3$. We use reinforcement learning and Bayesian optimisation to obtain new upper bounds on several link invariants that are not known to be algorithmically computable: the slice genus and the unknotting number for links, and the strong slice genus for algebraically split links. We also compute lower bounds using known invariants. Combining the upper and lower bounds, we obtain new exact values in many cases. Our unknotting agents can reproduce the non-additivity of the unknotting number for several counterexamples due to Brittenham and Hermiller, in some cases finding new unknotting trajectories.

0.52