Title: Characterizing (2,3)-Linkages
Xiying Du
ACO PhD Candidate
School of Mathematics
Date: July 9, 2026
Time: 9:30 AM (ET)
Location: Skiles 246
Zoom Link: https://gatech.zoom.us/j/94115202114?pwd=8W17lA4coTANMbIoMSoyGkyyJ8Zcf1.1
Committee:
Dr. Xingxing Yu (Co-advisor), School of Mathematics, Georgia Institute of Technology
Dr. Rose McCarty (Co-advisor), School of Mathematics, Georgia Institute of Technology
Dr. Tom Kelly, School of Mathematics, Georgia Institute of Technology
Dr. Anton Bernshteyn, Department of Mathematics, University of California, Los Angeles
Dr. Zongchen Chen, School of Computer Science, Georgia Institute of Technology
Reader: Dr. Chun-Hung Liu, Department of Mathematics, Texas A&M University
Draft of Thesis: https://drive.google.com/file/d/1Blt3-Gm8jQ1g4st1kQlQQJ24YkEFBpMH/view?u...
Abstract:
Let $G$ be a graph and let $a_1, \ldots, a_m, b_1, b_2$ be distinct vertices of $G$. We call the triple $\mathcal{G} = (G, \{a_1, \ldots, a_m\}, \{b_1, b_2\})$ a $(2,m)$-rooted graph. We say it is feasible if $G$ contains a $(2,m)$-linkage $(A, B)$, that is, a pair of disjoint connected subgraphs of $G$ with $\{a_1, \ldots, a_m\} \subseteq V(A)$ and $\{b_1, b_2\} \subseteq V(B)$. A fundamental result in graph theory is the characterization of $(2,2)$-linked graphs, resolved independently by Robertson and Chakravarti, Seymour, and Thomassen: $(G, \{a_1, a_2\}, \{b_1, b_2\})$ is infeasible if and only if $G$ admits a certain "essentially planar" structure with $a_1, b_1, a_2, b_2$ appearing on the outer boundary in this cyclic order.
Motivated by J\o{}rgensen's conjecture on $K_6$-minors, this dissertation investigates the structural characterization of infeasible $(2,3)$-rooted graphs. We introduce a set of six obstructions and three reductions that we conjecture to give a full characterization. An obstruction describes a structure of $\mathcal{G}$ that is immediately infeasible, just as the essentially planar structure above is the only obstruction for $(2,2)$-linkages; a reduction shows that the feasibility of $\mathcal{G}$ is equivalent to that of a smaller rooted graph, on a proper subgraph of $G$ with its own prescribed vertices. In these terms, every infeasible $(2,3)$-rooted graph is conjectured to satisfy an obstruction after a finite sequence of reductions.
In this dissertation, we prove the following reduction theorem: any minimal infeasible $(2,3)$-rooted graph avoiding all of these obstructions and reductions must admit a weak planar separation -- roughly, a $(k+1)$-separation $(G_1, G_2)$ whose planar side $G_2$ contains $k$ of the prescribed vertices $a_1, a_2, a_3, b_1, b_2$ and can be drawn in a disc with these $k$ vertices and the cut $V(G_1 \cap G_2)$ on the boundary in a certain order. Had the cut matched the $k$ prescribed vertices in size, this would be one of our reductions; the one extra vertex in the cut allows more than one way for a linkage to pass into $G_1$, which is why the separation is called "weak" and requires separate analysis. This result reduces the full characterization to the only remaining structural case.
