Primitive spatial graphs and graph minors (Q2471413): Difference between revisions

\textit{N. Robertson}, \textit{P. D. Seymour} and \textit{R. Thomas} [Bull. Am. Math. Soc., New Ser. 28, No. 1, 84--89 (1993; Zbl 0769.05034)] proved that the following are equivalent for a graph \(G\): {\parindent=5mm \begin{itemize}\item[1.] \(G\) has a spatial embedding, \(\phi\), every subgraph of which is free (\(\pi_1(S^3-\phi(G)\) is free)). \item[2.] \(G\) has a flat embedding (every cycle bounds a disk that is internally disjoint from the graph, and whose boundary is the cycle). \item[3.] \(G\) has a linkless embedding. \item[4.] \(G\) has no minor in the Petersen family (the set of seven graphs obtained from \(K_6\) by \(\Delta- Y\) and \(Y-\Delta\) exchanges). \end{itemize}} Here the authors study the notion of a primitive embedding of a graph, and attempt to generalize the above result to a result that relates graphs with a primitive embedding and graphs that have a knotless embedding. An embedding \(\phi\) of a graph \(G\) is said to be primitive if for each component \(G_i\) of \(G\), and any spanning tree \(T_i\) of \(G_i\), the bouquet \(\phi(G_i)/\phi(T_i)\) obtained from \(\phi(G_i)\) by contracting all of the edges of \(\phi(T_i)\) is trivial. Though the authors do not produce a full generalization of the Robertson, Seymour and Thomas result, they do produce a number of interesting results. They conjecture that a graph has a primitive embedding if and only if it has a knotless embedding. Their fundamental theorem is the following: An embedding \(\phi\) of a graph \(G\) in \(S^3\) is primitive if and only if the restriction \(\phi|_{G'}\) is free for all connected subgraphs \(G'\) of \(G\). Therefore, a flat embedding is primitive, but the converse is not true. In order to prove one direction of this result, the authors relate primitive embeddings to trivial \(n\)-string tangles. They also show that the property of having a primitive embedding is preserved under taking minors. They further establish that the \(K_7\) family and \(K_{3,3,1,1}\) family are contained in the obstruction set for graphs that have a primitive embedding, where the \(K_7\) family (respectively \(K_{3,3,1,1}\)) consists of the set of graphs obtained from \(K_7\) (respectively \(K_{3,3,1,1}\)) by \(\Delta- Y\) exchanges. An important tool used in establishing this result is the fact that a planar graph joined with two vertices is primitive. There is a known intrinsically knotted graph (hence does not have a primitive embedding), \(F\), that has an edge e such that \(F- e\) is not a planar graph joined with two vertices. Thus it is not known if \(F\) is in the obstruction set for primitive graphs, but \(F\) or some minor of \(F\) is in the obstruction set. The authors prove a number of other results about the structure of primitive embeddings of certain graphs. For example, if a graph has no disjoint cycles, then any primitive embedding of the graph is also flat. If a graph has disjoint cycles, then primitive embeddings of the graph are not flat in general. The authors then characterize primitive embeddings of ``handcuff graphs with \(n\)-bridges,'' for \(n= 1,2,3\) (pretty much the simplest connected graphs with disjoint cycles). A planar graph has a unique primitive embedding if and only if it has no disjoint cycles. Moreover, if a planar graph has disjoint cycles, then it has infinitely many primitive embeddings. They also show that any link contained in a primitive embedding of a graph in the Petersen family is either the trivial link or the Hopf link. Finally, they show that an \(n\)-component link contained in a primitive embedding of a connected graph has bridge number \(n\).