> kmjq` TbjbjqPqP i::*x%***
4@@@T8P<4T"?.m$!h#6@Z"?ZZ6@@/Z@@Z@@ f00$"p$$@ 0"_66^ZZZZTTTTTTTTT@@@@@@Intrinsic Knotting of Partite Graphs
Chloe Collins, Ryan Hake, Cara Petonic, Laura Sardagna
Abstract: A graph is intrinsically knotted (IK) if for every embedding of the graph there exists a knotted cycle. Let G be a partite graph, and form the partite graph G by increasing the number of vertices in each of the parts except one and then deleting an edge. We show that if G is IK, then the resulting graph G is also IK. We use this idea to produce new examples of IK graphs. In particular we use the fact that K5,5\ 2e is IK to show that for a bipartite graph with 5 (resp. 6) vertices in one part and E(G) e" 4V(G)-17 (resp. E(G) e" 5V(G)-27) is IK. Our method can t be improved since we also show that K5,5\ 3e is not IK in general.
1. Introduction
We bring together ideas from knot theory and graph theory. When a graph reaches a certain complexity it will contain a knot. We have found new ways of characterizing when this must happen and new ways to generate graphs that contain knots. To explain, we need to give some definitions. Well start by explaining graphs.
A graph is a collection of edges and vertices. Edges connect pairs of vertices and any given pair of vertices share either one edge or none. Any particular depiction of a graph in space (with the vertices represented as points and the edges as curves connecting those points) is referred to as an embedding. The degree of a vertex is the number of edges incident to that vertex. For instance, in figure 1 A1 has degree 2 while B1 has degree 3. Two vertices are adjacent, or neighbors, if they share an edge. For an example of adjacent vertices, consider A1,B2. Similarly, two edges are adjacent if they share a vertex.
A graph is n-partite if the vertices of the graph can be partitioned into n disjoint sets (or parts) such that any two vertices in the same part do not share an edge. For example, figure 1 is a bipartite graph (i.e. n=2) with 3 vertices in one part and 2 vertices in the other. We denote it K3,2. K refers to the fact that its complete. It includes all possible edges between any two vertices taken from different parts. Additionally we may specify that some number of edges have been removed from a graph. For example K3,2\ 3e means 3 edges have been removed from the graph K3,2 . The notation K3,2\ 3e represents a set of graphs as there are many ways to remove 3 edges.
A cycle is a sequence of adjacent vertices such that the sequence begins and ends with the same vertex. For example the cycle {A1,B2,A3,B1,A1} in figure 1. A cycle is either trivial or knotted. For an example of a knotted cycle, see figure 3. A trivial cycle can be deformed into a circle in the plane. In other words, it bounds a disc. If not, we say the cycle is knotted. A graph is intrinsically knotted(IK) if for every embedding of the graph, there exists at least one knotted cycle.
In 1983 Conway & Gordon [CG] showed that K7 is intrinsically knotted. Figure 2 is a particular embedding of K7, the complete graph on 7 vertices. This graph is the simplest example of an IK graph. In other words, K7 is the only IK graph on 7 or fewer vertices. It is known that if H is a subgraph of G, and G is not IK, then H is also not IK. Additionally, if H is IK and a subgraph of G, then G must also be IK. More recently, work done by [BBFFML] and [CMOPRW] has completely characterized IK graphs up to 8 vertices. There are 20 IK graphs on 8 vertices.
In our work, we have improved upon a 5n-14 bound on bipartite graphs. The bound 5n-14 tells us that graphs on n vertices with 5n-14 edges or more are IK [CMOPRW]. This is a powerful result. For example, although very little is known about graphs on 9 or more vertices, this bound immediately tells us that all 45 of the 9 vertex graphs with 31 or more edges are IK. In this paper we use a similar technique to improve the bound and therefore determine a new, large class of IK graphs. Our argument is based on the fact that K5,5 \ 2e is IK [CMOPRW] and presented in Section 2. It follows that we cannot generalize this argument since we also show (in Section 3) that K5,5 \ 3e is in general not IK.
2. Partite Graphs with IK Subgraphs
In this section we will prove Theorem 2.1 and then deduce several corollaries. In particular, Corollaries 2.6 and 2.7 give a new sufficient condition for IK bipartite graphs that improves on the 5n-14 bound of [CMOPRW].
Theorem 2.1: A graph of the form Ka, (a+1)n\ e has Ka, (a)n as a subgraph.
By Ka, (a+1)n \e we mean an (n+1)-partite graph, with one part having a vertices and the remaining n parts having a+1 vertices each, with one edge removed.
Proof: We will think of Ka, (a+1)n\ e as obtained from Ka, (a)n by adding a vertex to all but one part and then removing an edge. The edge removed must be taken from either parts with a and a+1 vertices (1) or parts with a+1 and a+1 vertices (2).
Case 1: The edge is removed between parts with a and a+1 vertices. By choosing the a vertices with no edge removed in the a+1 part in question and any a vertices in the other parts, we construct Ka, (a)n.
Case 2: The edge is between a+1 and a+1. Again we can choose a vertices from those two parts and every other part to form Ka, (a)n as a subgraph.
Therefore Ka, (a+1)n\ e has a Ka, (a)n as a subgraph. (
As an example of this process, we offer the following specific example, with a=2, n=2. Here Ka, (a+1)n\ e is either of the form G \(A1-A2) or G \(A1-A3) where G = K3,3,2. We will argue that K2,2,2 is contained in both G \ (A1-A2) and G \ (A1-A3).
In identifying our subgraph we need to pick groups of vertices that correspond to a K2,2,2 graph.
In each case we see that the missing edge can be avoided and thus we can find a K2,2,2 subgraph, as desired.
Corollary 2.2: If Ka, (a+1)n\ e is not IK, then Ka, (a)n is not IK
Corollary 2.3: If Ka, (a)n is IK, then Ka, (a+1)n\ e is IK.
We can use the proof of the Theorem to create an infinite family of graphs by beginning with a graph that is IK.
Corollary 2.4: A graph of the form Ka,(a+n)k\(n+a-2)e is intrinsically knotted for ae"3, ne"0, and ke"2.
Proof (by Induction on n):
Let n=0 and ae"3, ke"2.
A graph of the form Ka,a,a,& ,a\(a-2)e always has a K3,3,3\e subgraph. Since K3,3,3 \e is intrinsically knotted [CMOPRW], Ka,(a+n)k\(n+a-2)e is also intrinsically knotted for n=0.
Assume that every graph of the form Ka,(a+n)k\(n+a-2)e is intrinsically knotted, with ae"3, ne"0, ke"2. For the induction step, assume n is increased by 1 to form a graph G`= Ka,(a+n+1)k\(n+a-1). Compared to G, the number of edges removed from G` is also increased by 1, from n+a-2 to n+a-1. We view G` as formed from G by adding vertices and then removing an edge. The extra edge that is removed is either removed between parts with a and a+(n+1) vertices or between parts with a+(n+1) and a+(n+1) vertices.
Case 1: The edge is removed between parts with a and a+(n+1). We still have a+n choices of vertices from the a+(n+1) part so that we can choose our subgraph and avoid including the edge that has been removed. Therefore we will have a Ka,(a+n)k\(n+a-2)e subgraph which is intrinsically knotted(by inductive hypothesis).
Case 2: The edge is removed between two a+(n+1) parts. Again there are still a+n choices of vertices from which we can choose our subgraph and still avoid including that edge. Therefore we will have a Ka,(a+n)k\(n+a-2)e subgraph which is intrinsically knotted(by inductive hypothesis).
Therefore when every Ka,(a+n)k\(n+a-2)e is intrinsically knotted, then every Ka,(a+(n+1))k\((n+1)+a-2)e is also intrinsically knotted. By induction, Ka,(a+n)k\(n+a-2)e is IK.(
We can use the theorem to improve the sufficient condition for IK of [CMOPRW]:
E(G) e" 5V(G)-14, where E(G)= the number of edges and V(G) is the number of vertices of the graph G.
Corollary 2.5: A graph of the form Ka, a+n\ (a+n-3) edges is IK for ae"5, ne"0.
We omit proof, since it is similar in nature to Corollary 2.4, using the graph K5, 5 \ 2e to start the induction. Note that K5, 5 \ 2e is IK [CMOPRW].
Corollary 2.6: A bipartite graph with 5 vertices in one part and E(G) e"4V(G)-17 is IK.
Proof:
Using corollary 2.5, if a= 5, K5, n+5\ (5+n-3)e = K5, n+5\ (n+2)e has 5n+25-(n+2) = 4n+23 = 4(n+10)-17 edges and 5+(n+5) = n+10 vertices.
Therefore, if E(G) e"4V(G)-17, the graph has a K5, n+5\ (n+2)e minor and is IK. (
Corollary 2.7: A bipartite graph with 6 vertices in one part and E(G) e"5V(G) -27 is IK.
Proof:
Using corollary 2.5, if a=6, K6, n+6\ (6+n-3)e = K6, n+6\ (n+3)e has 6n+36-(n+3) = 5n+33 = 5(n+12)-27edges and 6+(n+6) = n+12 vertices.
Therefore, if E(G) e"5V(G) -27, the graph has a K6, n+6\ (n+3)e minor and is IK. (
It follows from [CMOPRW] that a bipartite graph with 4 or fewer vertices in one part is not IK. If there is a part of 7 or more vertices, we do get a bound of the form given in Corollary 2.5 and 2.6, but it is weaker%=>[\]ik
<
A
clrxNO_`즙jhQhUjhQhUh@hCJEHaJh@hCJEHaJ hH*hFhhQhH*hhhQh>*"jhQh0JB*UphhhQhhQh>*CJaJ3%]^_`9
IKnpZDEijGH`gdgd$a$gd$^a$gdVSFTT`lmoprw02%).Dj
EFHTVkt}4:NWlmt.5{09w} jhQhh[8hH*h[8hhQhH*hQh6H*hQh6hQhEH hH*hQh>*hjhQhUhQh?34-./1h j L!N!""T"X""#gd!'/01
$ @ R f N!h!n!!!!""R"t"v"~"""""""#.#~##>$N$$$P%d%&'''=(D(
))C)\)̻hhQhH*hQh]h6H*hQh6H*hQh6hQh>*jhUhBhjhUhQh hH*B##&&;(=(^)`)$*&**++.,0,^-`-..2///001'2(2BDDD$a$gdgd\)w)))))* *"*+++++,,,,,*-2-4-`-|--.\.h...L/N////////0000122%2&24DBDDDD*E0EEEnFxFFFFFFFFFFFFFFFFFFFU hH*hQh6H*hQh6hQh>* jhQhhhQhH*hQhL than the bound E(G) e" 5V(G)-14.
3. Not Intrinsically Knotted Graph
Theorem 2.1 is based on showing graphs of form Ka, a+n\ (a+n-3) edges have a K5,5\ 2e IK subgraph. Here we show that this method cannot be improved because, in general, K5,5\ 3e is not IK.
Following [CMOPRW], we denote the vertices in Kl,m,n by {A1, A2,& ,AL}, {B1, B2,& ,BM}, {C1, C2,& ,CN}. Thus, K5,5 \ {A5-B1, A4-B1, A3-B1} denotes K5,5 with 3 edges removed all of them incident to the same vertex B1 in the second part.
Theorem 3.1: K5,5 \ {A5-B1, A4-B1, A3-B1} is not IK.
Proof: Let G = K4,4,1 \ {A5-C, A4-C}. It is known that G is not IK. [CMOPRW]
Let H be K4,4,1 \ {A5-C, A4-C, A3-C}. H is also not IK, since H is a subgraph of G.
In a knotless embedding of H, add a vertex D on the edge A2-C and label this graph H`. The graph is now bipartite as we will show. In adding D, the vertex C is no longer connected by an edge to any vertex in the A part. C is connected to {B2, B3, B4, B5, D}. Thus, we can consider C to be a vertex in the A part. D is connected to {A2, C}. Therefore we can consider D to be a vertex in the B part. But then we have 10 vertices split into 2 sets of 5, so H` is a bipartite graph. Since deg(C)=5,deg(D)=2,deg(A3)= deg(A4)= deg(A5)= 4 and deg(A2)= deg(B2)= deg(B3)= deg(B4)= deg(B5)= 5, we have a bipartite graph on 10 vertices. This graph is precisely K5,5 \ 3e with a vertex D of degree two.
Therefore K5,5 \ {A5-B1, A4-B1, A3-B1} has at least one knotless embedding. (
4. References
[BBFFHL] P. Blain, G. Bowlin, T. Fleming, J. Foisy, J. Hendricks, and J. LaCombe, Some Results on IK Graphs , (preprint).
[CG] J.H. Conway and C. McA. Gordon, Knots and Links in Spatial Graphs , Journal of Graph Theory, Vol 7, (1983), 445-453.
[CMOPRW] J. Campbell, T. Mattman, R. Ottman, J. Pyzer, M. Rodrigues, and S. Williams, Intrinsic Knotting and Linking of Almost Complete Graphs (preprint available at www.arXiv.org).
Funded by NSF REU Award 0354174 and supported by the MAA's NREUP program with funding from the NSF, NSA, and Moody's.
PAGE
PAGE 5
DDDDFGGTHVHHIOOOOOOOOOOOOOOOOOOOgd$a$gdFFFFGGGGG4G:GGHHHHH"H,H0H:HRHVHbHvHHHHHHHHIII I"I*I.I6IIIII
JJJJJJxK|KKKKKKKKKKK4L8LL\MhMpMrMMMMMMMMMMMMM h6hQh6H*hQh6hQh>*hhQhH*hQhQMMMNNN"NNNNNO$O*O4O8OBOFOPOOOOOOOOOO~QQQQQPSRSTSVSSSBTFTHTLTNTRTTTXTZT^TӼjhUh@hhF[hhV
hhQh5hQh5\hQh6 h>*#jhUaJmHnHsHtHhBh>*hQh>* jhQhhQhH*hhQh0OPPQQRSTSVSBTDTFTJTLTPTRTVTXT\T^TpTrTtTTTTh]hgd&`#$gdgdgd`^``gd^T`TlTnTpTtTvTTTTTTTThF[hhn10JmHnHuh
h0Jjh0JU
TTT6&P1h:p/ =!"#$8%`!kYݿswFԚ|.,xڭKTQƿ,urnER٘3Xv{OqL=[{(K猞)
\{9}f}ڳ9lI04JLA6"[fgZlt6%5`!J}ل
57s4 P%hR!;]7jn6MW_|HK3dTl0˚m֤fv5/`\Ι~=hMJX~)`=
~@7݂^mL6iD5eLX-B̚=-`3(Ι7)M
FkRkؔ(#f~ͷW1>Yf}E`Ǆc5@5'`}lΙu~]hMJX~/"dWb5!g]$q{kO9.߯+
FkRk~}__! c
75u=}4+)}v{*^[u٨9y]<m iw:CRßhPWs;S>mmBcۨJr
լuvy@15iVT
.?SC:49;OۻHD+Ш?25*)#y5;+"yjtNӺPck#{+Ҩ;n4ojG<,WoC`CL\"kP2 Ԛ|.,Gx][HTQ+,KJh:RC B1"IRg^Qj>T
R|Ǡlc99߿fwUSpY݇za
5{uĐ4ոJܫ:Saf)ŀ|qz>ep,s̱<뙇;ysL[*36#lVx:`f̦_~-2͊PWG%A|N~ݗ/Ԇi,9MNI(LMwlv9SKZե4O^Y4JĉuZ`@k7]0nP/٠= ܦl>`+>QV2V(;$YuT빇dV6x>K6de-8LnfUZY.
VdfX-=)k쨕UɳZ^I= ʂU[F
G̏գjNUa%*)k찕nUEYڏbuSjQfŚnZP}ZzC;@OڮP h9tNUN[7E-=sRKPZGV4aIjV%$tEݡå{R:8_`rDd
5 0
#A"ȇv ~AFkD@=ȇv ~AFkdV`xYLUu?^xHMƈ6m
(e[8`@a^k46X9uKt:sr5 Dte[(j
pѢs=_\=}|9=sh+/i+:OЫu}ZM#DUD.Ece@IZ*$ޅ.
_dm
gZꩉQ
BeBAܐ[~dM,|MƝqFん1WF㖸;S('#>σ90Bfcqf=n(o2mvYQ]ynLio3jB{rK"G?r_8]q>+6ʉ7{d
1[[o_Gx_1
-)&
"AcHBaBwU
Y..&53NkH͋яɃX1VqFobGbJO#sӼJC=Uo]`{8جEO
+m1ϱqOz5U?s$"m&
s>@^2Ϋ_6s!b}l,b7[b
l0ܒQq}ˆ<1Dk$X=v7_]tHa+o`*
7Pm@k@%REcD"LlzV}boD\lץ1g%:[j3CE/M0yePR"7Vbb]cϝ%/ٸTlIO=Kjf/7l,8|>8"u xj5zÞtc&W~߆K1tݖ\b\q!Ѹdi(Xc?ohs9V>՚mqLcܙ2$ʙ&tx9S]X北\|}7WYӂ̽jv~j3V9ˑsbX旼Y4q&a?1=ř܂痡_qFǙoT9tA_`μc`?͙Lx9rgfo
LSyϻNgԞ)p3~-*~~Wp5JO9l#"gӆ\7UŲl*so@c5fe4`k'U+Yq96ؔ;4]dS
5Wy5?~7s7x܉lX[i,ɦ=\lr֏_lr7n&w$q/gSwOO0l2YDd
3
sqD
#A#"`"l[ٛ*@=l[ٛ* #dKXxŘQlUt6PW)
6J4@CBQV#5-
Z\IS)dyTm⃤|(}XIxPblP111i7 ֬9ޮdO֛{{?
>=DOUD/'b3Cj5hc')QXQ|h쮠W
ꦷPuA5^qY [[
{P
[&`aro{R-l-l盐e lneI5v
{6AEj&'q69Z+b23E8g,α9XIs&2V2.p(ř8=FɜV"'16q3^SoWlo8v5a%OZX{
YFGu
eSѤpR#Б؟ޟ̩?]q5yZ:g:yd8Sg:.p[:2理9d95ta<)f>Qc>=ScΔũ?YSC3iqj}FusɌɾ+ֺ)f>SCG5h]GszVX=oҤ@#k[K.7
h^uyG-jz-ћ_Tz65F;;$ZO@yΛIƲ\nc&'n3y-7gAtd{epօ5:&ż֦
i.ёykV~`y_lIoҧDWy?6}39k{ +ZY
WuBs1lWQ!PJI~S{}S&o迗V9n ~q߈+.>{}ޏ1`yli~4Ed_r_G0+">=H9¿W?p~zc>弶w9g1f#R.t#`>^~!D9i ߇ʜm\D,y="n/g^0\C yګ#awC 'Ū/'
3KXxZOA}'w\1@GD"C4T+@P%4 !D~TtƎFZ;
:o1.ߒfn}of\n}5%O¶Aq*_u(aS
9X6?v>ǣI&G?9:k|3!G;oTN誾ape;~H9>4B6
oEc_Pm'Wfsh̟C煭w~;Vh6yd@jSc.ڨ4JcZ VЌxU_f@G^Z"
WJ#lazbǪ3%LUN)좊cN)B>j茩W>U-Y״u
Z8|=/!čw)bǒ 7ANeٖ3K>}s|ʻʘ-gu"}kR׆S[^ꂳ
z7B
{m-1φSz1Þoeĭ91~67Xm9O0w9JSeyߟbK4Ǽbk|Or*cζL/:X~%c=RI^>f=P'9m9߇6oC2Ֆ=|j1x}Vg#V
[9weur`=>Y+}iG0}<)`Op~FNp|yp~CS!2w$cyn8s9>~?ߴnf? q86_--P5s-9keky6j˩{<p6O2v2F:i
τs(N_57fϯADK6ʚr?搜ȓք{_BJ.Edׁf\)>*8vC7$KQ[dUī既qblɄtxXx`,|kL m2Sh xO{y#DYn>>9m~6?|uzj/US/9j6P:S9xc0EA1L2lc`a`Bh19 7M!'E&*Lf+.ELB B3d,^pRhk&e>~3Q=>ctcX0E&'c&(c:QvR,EXDYSU"hMT-Dd
*870
#A2fY}5~`!}fY}5~"i+xڭKTAob{Ò]TiTZb4b{ |YR"SH&aDOHkD Tft9Sfevg7s#D@ b%'$KS)UDq&Z H8%ׇcQ;Y~0۔0nmEsYlbcL{`1kϕ9R4fic{݆,&۫ol`#ӎ!J;ZxYjl`Z%Ls-Yeȴ_53ն~/?fmH0=oƶAS{ 33m7-*|bZ%Ls-?Wjk[x1kWjZRW)kʐi
2+kdO8-+ö|X~Ϳ%{}2o*u(D&YIc%G^SRϔ|:TNdY!Oޝ7l9y4xUTqg>g>abݸTx#WyWאmuܙiL>0cy=E~~__MI5|R
4.|/Z!/AjE;Y1Z]6;xoZÅPܩ㧱$\@*٫,>LĎҩ&rxƄCGz
XE.}\'m=by|D>~%8.M
Wv3b=$Qii'v@t&KZmzl8IҥS1)kd6M<怛.aGebw[fi~cHibr2@Uխ]dKeDd
%0
#A2GhfE6Q\?#L`!hfE6Q\?6]@.xڥMhAoMjQbAiiB@Dы xQEZKEID*EYB@he}` o03f
!OK*Ֆ")m_SD~-\&H9#M
Ni䲨k ȥl~WJ7nb;vkVװr?vrBV2^9]Ƹ`|Rm|Rm|R}טE'4|Ɨp>ݑX}pڭBċ&%NMsŊ2+YdU3;Uџ>O{lzM6ĴŒÓAVI-d(MiyL8lL,ӆ]97vxeȰROda.Y]!an=|4]z&fXkKd
]zİa9^2T4A7 Ӊ6-L
;~Tb8v*n8D@D/;NormalCJ_HaJmH nHsH tHDA@DDefault Paragraph FontRiRTable Normal4
l4a(k(No Liste@A(HTML Preformatted7
2(
Px4 #\'*.25@9CJOJPJQJ^JaJtH F@FA(
Footnote TextCJPJaJtH @&@@A(Footnote ReferenceH*4 @"4xZFooter
!.)@1.xZPage Number[I+wzI+b%]^_`9I K n p Z
DEijGH34-./145*,C;=^`c D!K!!'"("!#"#E#F#$$$*%+%x%%(((((((((((((((((((t)u)))***!+"+#+%+&+(+)+++,+.+/+8+9+:+E+F+G+J+I0I0I0I0I0I0I0I0I0I0I0I0I0I0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000I00I0000w@0I00@0I00@0I00@0I00I00I00I00@0@0I00I00P $$$'`\)FM^TT!,-/#DDOTT +.0T '!!H
o2$L\"kP2s8b2$:u|"$l[ٛ*"$YL2٘f"$
=w2h/B$VW*Tܳmw@
t(
<
#AB
S ?(I+
$T OLE_LINK1 OLE_LINK2eeJ+hhJ+S1lT1U1 J+"J+9*urn:schemas-microsoft-com:office:smarttagsplaceX?@Dsw{_h##*#+#+%+%+&+&+(+)+++,+.+/+G+J+fi
&(rtUWdp79"&Z^ "02ikgi
ce< > -!/!w!y!!!####8$<$v$x$%%<%@%%%&&[(](((z))*#+#+%+%+&+&+(+)+++,+.+/+G+J+3333333333333333333333333333333333333333333333333333333((*#+#+%+%+&+&+(+)+++,+.+/+:+D+J+*#+#+%+%+&+&+(+)+++,+.+/+G+J+n1@((,(((| "#I+@@@
@@@ @$@L@@*@.@d@@DUnknownGz Times New Roman5Symbol3&z ArialY
aMathematica1Courier NewG
MS Mincho-3 fg?5 z Courier New"hsfmufsf^M$M^M$MA4d**>2qHP ?F[2QLemma: Let G be an intrinsically knotted partite graph of two or more partitionsSTCP Ryan HakeOh+'0$0@ T`
TLemma: Let G be an intrinsically knotted partite graph of two or more partitionsSTCPNormalRyan Hake4Microsoft Office Word@Ik@ f@f@?@ABCDEFHIJKLMNOPQRSTUVWXY[\]^_`acdefghilRoot Entry F/*fnData
5#1TableG$WordDocumentiSummaryInformation(ZDocumentSummaryInformation8bCompObjq
FMicrosoft Office Word Document
MSWordDocWord.Document.89q__