Do triple-linked graphs exist?

Question

Lets say that a finite simple graph $G$ is (intrinsically) fully triple-linked if for each embedding of $G$ into $\Bbb R^3$ we can find three disjoint cycles $C_1,C_2,C_3\subset G$ whose embeddings are pairwise linked.

Question: Do fully triple-linked graphs exist?

This is a natural generalization of intrinsically linked graphs: every embedding of $K_6$ has two linked cycles. A lot has been written on such generalizations [1]. For example, $K_{10}$ is (partially) triple-linked in the sense that every embedding has three cycles that form a non-split link. This link might however be a "chain" (one cycle linked to two others that are unlinked). Moreover, arbitrarily large non-split links are forced to appear in embeddings of large enough complete graphs, but as far as I know, these might just form "long chains" or perhaps "branching chains". If something has been proven about forcing more complicated links, I was unable to find it.

---

• [1] J. L. Ramírez Alfonsín, "Knots and links in spatial graphs: A survey"

Answer 1

Yes.

Theorem 1. For every $k$ there exists $N=N(k)$ such that in every embedding of the complete tripartite graph $K_{N,N,N}$ into $\mathbb{R}^3$ there are $k$ disjoint pairwise linked triangles; in particular, each pair of the triangles has an odd linking number.

Theorem 2. In every embedding of $K_{3,3,3}$ into $\mathbb{R}^3$ there is a pair of disjoint triangles with an odd linking number.

Lemma 3. If a pair of triangles $a_1a_2a_3$ and $b_1b_2b_3$ is straight-line embedded on the moment curve, then their interiors are intersecting if and only if the order of their vertices along the moment curve contains the pattern $ababa$ or $babab$. The triangles are linked if the order of their vertices along the moment curve contains both patterns $ababa$ and $babab$. Therefore, the only possible ordering for the case of linked triangles starting with $a$ is $ababab$. This also means that if $K_6$ is straight-line embedded on the moment curve, and the vertices are ordered as $1,2,3,4,5,6$, then there is exactly one pair of linked triangles: $135$ and $246$.

Corollary 4. If $K_{3,3,3}$ is straight-line embedded on the moment curve, such that the vertices are ordered $1,2,\dots 9$, and the three independent sets are $\{1,2,3\}, \{4,5,6\}$ and $\{7,8,9\}$, then there are exactly $27$ pairs of linked triangles (with linking number $1$ or $-1$).

Proof of Theorem 2. A pair of disjoint edges $e,f$ in $K_{3,3,3}$ determines $4$ or $6$ pairs of disjoint triangles. Therefore, if during a homotopy of an edge $e$ we cross over $f$, the total linking number of pairs of disjoint triangles changes by an even number. Since we can transform any pair of embeddings (with a common vertex set) into each other by a sequence of homotopies of the edges, the total linking number of pairs of disjoint triangles must be odd by Corollary 4.

Proof of Theorem 1. Let $N$ be sufficiently large and fix an embedding of $K_{N,N,N}$ into $\mathbb{R}^3$. Label the vertices of $K_{N,N,N}$ so that the three independent sets forming the tripartition are $\{a_1,a_2,\dots,a_N\}, \{b_1,b_2,\dots,b_N\}$ and $\{c_1,c_2,\dots,c_N\}$. The vertices of every copy of $K_{3,3,3}$ in $K_{N,N,N}$ are of the form $a_{i_1},a_{i_2},a_{i_3},b_{j_1},b_{j_2},b_{j_3},c_{k_1},c_{k_2},c_{k_3}$ where $i_1<i_2<i_3$, $j_1<j_2<j_3$ and $k_1<k_2<k_3$. By Theorem 2, each copy of $K_{3,3,3}$ contains a pair of disjoint linked triangles, out of possible $3\cdot 6\cdot 6=108$ pairs of disjoint triangles. There can be more such pairs, but we can fix one of them. In this way, we can assign one color out of $108$ to every copy of $K_{3,3,3}$ in $K_{N,N,N}$, according to the ordering of the vertices of the selected pair of triangles. Now we apply the ``tripartite Ramsey theorem'', also called the product Ramsey theorem; see e.g. [R. L. Graham, B. L. Rothschild and J. H. Spencer, Ramsey Theory, Second edition, Theorem 5 on p. 113] or [H. J. Prömel, Ramsey Theory of Discrete Structures, Theorem 9.2]. Therefore, if $N$ is sufficiently large, we will find a monochromatic copy of $K_{2k-1,2k-1,2k-1}$. Inside this copy we will now find $k$ disjoint pairwise linked triangles. The choice will depend on the color. We can choose the vertices in each part of the tripartition separately. For example, if the linked triangles in each copy of $K_{3,3,3}$ used the vertices $a_{i_1},a_{i_2}$, then we take the $k$ vertices $a_{j}$ with smallest indices. If the linked triangles in each copy of $K_{3,3,3}$ used the vertices $a_{i_2},a_{i_3}$, then we take the $k$ vertices $a_{j}$ with largest indices. Finally, if the linked triangles in each copy of $K_{3,3,3}$ used the vertices $a_{i_1},a_{i_3}$, then we take every odd vertex $a_{j}$ in the linear ordering of the indices.

Answer 2

If you restrict to straight-line embeddings (where edges are line segments), then the answer is yes: using the result in Erdos-Szekeres in high dimensions there exists some $n$ such that if you have $n$ points in $\mathbb{R}^3$ in general linear position, then 9 of them must form the vertices of a cyclic polytope $(v_1, v_2, \dots, v_9)$.

Consequently, any straight-line embedding of such a $K_n$ contains a $K_9$ forming a cyclic polytope, in which case the triangles $\{ v_1, v_4, v_7 \}, \{ v_2, v_5, v_8 \}, \{ v_3, v_6, v_9 \}$ are pairwise-linked.

---

[begin non-rigorous section] It should be possible to adapt this into a topological proof that works for every embedding, but I don't have a complete proof (just a rough outline). In particular, given an embedding of a complete graph $K_n$ (with the vertices labelled by integers $1, \dots, n$), it should be possible to extend this to an immersion of the complete simplicial complex of dimension 2 (where we have triangles as well as vertices and edges).

Then we can colour each set of 4 points (note that we have an order on the underlying vertex set) according to the orientation of the simplicial sphere, and use Ramsey's theorem for 4-sets to guarantee some homogeneous 9-vertex set where all of the 4-vertex subsets have the same orientation. Then it should be possible to prove that this forms a cyclic polytope, and then we're done by the same argument. [end non-rigorous section]

Answer 3

I have since come across the following paper which seems to answer the question affirmatively in a very strong sense:

• E. Flapan, B. Mellor, R. Naimi, "Intrinsic linking and knotting are arbitrarily complex".

Theorem For every $n,\alpha\in\Bbb N$, there is a complete graph $K_r$ such that every embedding of $K_r$ in $\Bbb R^3$ contains an oriented link with components $Q_1,...,Q_n$ such that for $i \not= j$ holds $|\operatorname{lk}(Q_i, Q_j)|\ge \alpha$ and $|a_2(Q_i)| \ge \alpha$.

Here $a_2(Q)$ denotes the second coefficient of the Conway polynomial of $Q$, that is, is a measure of knottedness of $Q$. In other words, the theorem says that one can force arbitrarily large "fully-linked" links, where each component is itself knotted in an arbitrarily complicated way.