{"id":48,"date":"2020-04-21T09:55:00","date_gmt":"2020-04-21T09:55:00","guid":{"rendered":"http:\/\/blogs.rollins.edu\/graphembeddings\/?page_id=48"},"modified":"2020-05-05T10:34:14","modified_gmt":"2020-05-05T10:34:14","slug":"kpp-theorems","status":"publish","type":"page","link":"https:\/\/blogs.rollins.edu\/graphembeddings\/embedding-complete-bipartite-graphs-with-cayley-maps\/kpp-theorems\/","title":{"rendered":"Kp,p Theorems"},"content":{"rendered":"\n\n\n

Theorem 1 (Inverse Theorem)<\/strong> If there exists a face, \"F_0\", that is closed with respect to inverses and resulted from rotation \"\rho\", then every element in \"\rho\" is in \"F_0\".<\/em><\/p>\n\n\n\n

Proof- <\/em> Suppose there exists a face, \"F_0\", that is closed with respect to inverses and resulted from rotation \"\rho\". Let \"x\" be an arbitrary element in \"F_0\". Because \"F_0\" is closed with respect to inverses, \"x^{-1} \in F_0\". By Equation 1, \"\lambda(x^{-1}) = \rho(x)\". Therefore, for any element, \"x\", in \"F_0\", the element following it in \"\rho\" is also in \"F_0\". Thus, there does not exist an element in \"\rho\" that is not in \"F_0\". This implies that every element in \"\rho\" is in \"F_0\".<\/p>\n\n\n\n

<\/div>\n\n\n\n
\n\n\n\n

Theorem 2 (2-gon Theorem)<\/strong> There does not exist a 2-gon face for \"{K_{p,p}}\" using \"Z_{2p}\".<\/em><\/p>\n\n\n\n

Proof- <\/em>Case 1. \"p=2\":<\/strong> The Cayley Map for \"K_{2,2}\" only has one possible rotation, \"\rho=(1\" \"3)\", and \"C_M(Z_4,(1\" \"3)\" forms two 4-gons.
Case 2. \"p>2\":<\/strong> Let \"x, y \in \rho\", where \"(x + y)\bmod{2p}=0\". By the definition of inverse, \"x\" and \"y\" are inverses. By Theorem 1, there does not exists a face generated with only \"x\" and \"y\". Therefore, there does not exist a \"2\"-gon face for \"{K_{p,p}}\" using \"Z_{2p}\".<\/p>\n\n\n\n

\n\n\n\n

Theorem 3 (Odd-gon Theorem) <\/strong>There does not exist a face with an odd number of sides (an “odd-gon”) for \"{K_{p,p}}\" using \"Z_{2p}\".<\/em><\/p>\n\n\n\n

Proof- <\/em> Let \"n\" be an odd integer. The sum of an odd number of integers is odd, and \"2p\" is an even number, so there does not exist an \"n\"-gon face for \"{K_{p,p}}\" using \"Z_{2p}\".<\/p>\n\n\n\n

<\/div>\n\n\n\n
\n\n\n\n

Theorem 4 (\"D_p\" Face Theorem) <\/strong>For all rotations \"\rho\" of \"{K_{p,p}}\" using \"D_p\", \"F={\rho}\", and there are p number of \"2p\"-size faces.<\/em>

Proof- <\/em>Because every element in \"\rho\" of \"{K_{p,p}}\" using \"D_p\" has order 2, each element is its own inverse. By Equation 1, the resulting Cayley Map will produce one distinct face, \"F_0=\rho\". By Theorem 3, the face must have an even number of sides. Since \"p\", the size of \"\rho\", is odd, the face will be a \"2p\"-gon. Additionally, by Equation 5, \"\frac{2p^2}{2p}=p\". Therefore, \"\rho\" produces \"p\" \"2p\"-gons in total.<\/p>\n\n\n\n

<\/div>\n\n\n\n
\n\n\n\n

Lemma 1 (\"K_{5,5}\" Smallest Face using \"Z_{10}\") <\/strong>The smallest face size possible for \"{K_{5,5}}\" using \"Z_{10}\" is \"10\".<\/em>

Proof- <\/em>There exists a rotation that produces 10-gons for 

*** QuickLaTeX cannot compile formula:\n{K_{5,5}\n\n*** Error message:\nMissing } inserted.\r\nleading text: ${K_{5,5}$\r\n\n<\/pre> using \"Z_{10}\":<\/strong>
Let 
*** QuickLaTeX cannot compile formula:\n\rho=(1 \hspace{2} 7\hspace{2} 5\hspace{2} 3 \hspace{2} 9)\n\n*** Error message:\nIllegal unit of measure (pt inserted).\r\nleading text: $\rho=(1 \hspace{2}\r\n\n<\/pre>. The resulting face set is 
*** QuickLaTeX cannot compile formula:\nF= {(5 \hspace{3} 3)(7 \hspace{3} 9)(1)}\n\n*** Error message:\nIllegal unit of measure (pt inserted).\r\nleading text: $F= {(5 \hspace{3}\r\n\n<\/pre>, all of which are 10-gons.<\/p>\n\n\n\n

We  rule out the possibility that there exists a smaller sized face, \"F_s\" (Cases 3-5 use proof by contradiction):<\/strong>
Case 1. Odd-gons:<\/strong>
By Theorem 3, there does not exist an odd-gon face for \"{K_{5,5}}\" using \"Z_{10}\"

Case 2. 2-gons:<\/strong>
By the Theorem 2, there does not exist a \"2\"-gon face for \"{K_{5,5}}\" using \"Z_{10}\".

Case 3. 4-gons:<\/strong>
a) The 4-gon is formed by two distinct elements:<\/em>
Let \"x, y \in \rho\", where \"2(x + y)\bmod{10}=0\" and \"(x + y)\bmod{10}\neq0\". Since \"2(x + y)\bmod{10}=0\", \"(x + y)\bmod{5}=0\". Therefore, \"x+y\" is a multiple of 5, but not 10. So, \"x+y\" is an odd number. This is a contradiction since \"x, y \in \rho\", \"x\" and \"y\" are odd, so \"x+y\" is even.

b) The 4-gon is formed by four distinct elements:<\/em>
Let \"x, y, w, z \in \rho\", where \"x, y, w,\" and \"z\" form a face. Therefore, \"(x + y + w + z)\bmod{10} = 0\". Since \"|\rho|= 5\", there exists a pair of inverses in \"F_s\", and by Theorem 1, \"5 \in F_s\". Let \"x=5\" and \"y\" and \"w\" be the inverse pair. It follows that \"(5+10+z)\mod{10}=0\", so \"z=5\". This contradicts \"x=5\".
Therefore, there does not exist a \"4\"-gon face for \"{K_{5,5}}\" using \"Z_{10}\".<\/p>\n\n\n\n
Case 4. 6-gons<\/strong>
a) The 6-gon is formed by two distinct elements:<\/em>
Let \"x, y \in \rho\", where \"3(x + y)\bmod{10}=0\", \"2(x + y)\bmod{10}\neq0\", and \"(x + y)\bmod{10}\neq0\".
By the modular multiplication property, since 3 is not divisible by 10, \"x+y\" is divisible by 10. This contradicts \"(x + y)\bmod{10}\neq0\".

b) The 6-gon is formed by three distinct elements:<\/em>
 Let \"x, y, w \in \rho\", where \"x, y,\" and \"w\" form a 6-gon face, such that \"2(x + y + w)\bmod{10} = 0\" and \"(x + y + w)\bmod{10} \neq 0\". Since \"2(x + y + w)\bmod{10} = 0, (x + y + w)\bmod{5} = 0\". \"|\rho|=5\", so there exists a pair of inverses in \"F_s\". Let \"x\" and \"y\" be the inverse pair. Therefore, \"(10+w)\mod{5}=0\", so \"w=5\". This contradicts Theorem 1.
Therefore, there does not exist a \"6\"-gon face for \"{K_{5,5}}\" using \"Z_{10}\".<\/p>\n\n\n\n
Case 5. 8-gons:<\/strong>
a) The 8-gon is formed by two distinct elements:<\/em>
Let \"x, y \in \rho\", where \"4(x + y)\bmod{10}=0\", \"2(x + y)\bmod{10}\neq0\", and \"(x + y)\bmod{10}\neq0\".
By the modular multiplication property, since 4 is not divisible by 10, \"x+y\" is divisible by 10. This contradicts \"(x + y)\bmod{10}\neq0\". Therefore, there does not exists an 8-gon face generated with only \"x\" and \"y\".

b) The 8-gon is formed by four distinct elements:<\/em>
Let \"x, y, w, z \in \rho\", where \"x, y, w,\" and \"z\" form an 8-gon face, such that \"2(x + y + w + z)\bmod{10} = 0\" and \"(x + y + w + z)\bmod{10} \neq 0\". Since \"2(x + y + w + z)\bmod{10} = 0, (x + y + w + z)\bmod{5} = 0\", where \"x + y + w + z\" is not a multiple of 10. Therefore, \"x + y + w + z\" is odd. However, this contradicts \"x, y, w\" and \"z\" forming an 8-gon face, since the sum of four odd numbers is even.
Therefore, there does not exist an \"8\"-gon face for \"{K_{5,5}}\" using \"Z_{10}\".<\/p>\n\n\n\n
<\/div>\n\n\n\n
\n\n\n\n
Theorem  5 (The Best \"C_M\" Genus for \"{K_{5,5}}\") <\/strong>The optimal genus for \"{K_{5,5}}\" using a Cayley Map is \"g=6\".<\/em><\/p>\n\n\n\n
Proof-<\/em> By Lemma 1 and Theorem 4, the smallest face size that a rotation of \"{K_{5,5}}\" could possibly produce is 10, so an optimal rotation would produce five 10-gons. Using the Euler Characteristic formula, \"\chi=-10.\" Thus, \"g=6\".<\/p>\n\n\n\n
<\/div>\n\n\n\n
\n\n\n\n
Lemma 2 (The Best Rotation for \"{K_{7,7}}\" using \"Z_{14}\") <\/strong>The best rotation possible for \"{K_{7,7}}\" using \"Z_{14}\" produces 4-gons and 6-gons.<\/em><\/p>\n\n\n\n
Proof-<\/em> There exists a rotation for \"{K_{7,7}}\" using \"Z_{14}\" that produces fourteen 4-gons and seven 6-gons:<\/strong>
Let \"\rho=(5\" \"1\" \"3\" \"7\" \"9\" \"13\" \"11)\". \"\rho\" produces 
*** QuickLaTeX cannot compile formula:\n\mathcal{F}={(1\n\n*** Error message:\nMissing } inserted.\r\nleading text: $\mathcal{F}={(1$\r\n\n<\/pre> \"11\" \"7\" \"9),(5\" \"13\" 
*** QuickLaTeX cannot compile formula:\n3)}\n\n*** Error message:\nExtra }, or forgotten $.\r\nleading text: $3)}\r\n\n<\/pre>, which is a face set of fourteen 4-gons and seven six-gons.

We rule out the existence of a better rotation using a proof by contradiction:<\/strong>
Let \"\rho_a\" be a rotation of \"{K_{7,7}}\" using \"Z_{14}\" that produces only 4-gons and 6-gons. Suppose this is not the best possible rotation. Therefore, there exists a rotation that produces faces with less than four sides, a rotation that produces only 4-gons, a rotation that produces only 5-gons, or a rotation that produces only 4-gons and 5-gons. By Theorem 2, there does not exist a rotation that produces 2-gons. By Theorem 3, there does not exist a rotation that produces 1-gons, 3-gons, or 5-gons. Therefore, there exists a rotation, \"\rho_b\" that produces only 4-gons. Since the number of darts in \"C_M(Z_{14}, \rho_b)\" is 98, \"\rho_b\" produces 24.5 4-gons. This is a contradiction, because there cannot be a non-integer number of faces. Thus, \"\rho_b\" cannot produce only 4-gons.<\/p>\n\n\n\n
<\/div>\n\n\n\n
\n\n\n\n
Lemma 2 (The Best Rotation for \"{K_{7,7}}\" using \"Z_{14}\") <\/strong>The best rotation possible for \"{K_{7,7}}\" using \"Z_{14}\" produces fourteen 4-gons and seven 6-gons.<\/em><\/p>\n\n\n\n
Proof-<\/em> Case 1: <\/strong>The 4-gons, \"F_0\" and \"F_1\", are produced by two pairs of two distinct elements, and the 6-gon, \"F_2\", is produced by three distinct elements.<\/em> By Equation 2, \"m_0=m_1=m_2=2\". By Equation 3, there are seven occurrences of each of the 4-gons and seven 6-gons.
Case 2:<\/strong> The 4-gon, \"F_0\", is produced by four distinct elements, and the 6-gon, \"F_1\", is produced by three distinct elements.<\/em> By Equation 2, \"m_0=1\" and \"m_1=2\". By Equation 3, there are fourteen 4-gons and seven 6-gons.
Case 3: <\/strong>The 4-gon, \"F_0\", is produced by one distinct element, and the 6-gon, \"F_1\", is produced by six distinct elements.<\/em> By Equation 2, \"m_0=4\". By Equation 3, since 14 is not divisible by 4, there cannot be a 4-gon made from one distinct element.<\/p>\n\n\n\n
<\/div>\n\n\n\n
\n\n\n\n
Theorem 6 (Best \"C_M\" genus for \"{K_{7,7}}\") <\/strong>The best possible genus for \"{K_{7,7}}\" when using a Cayley Map is \"g=8\".<\/em><\/p>\n\n\n\n
Proof-<\/em> Case 1. Using group \"D_{7}\":<\/strong>
By Theorem 4, any rotation for \"{K_{7,7}}\" using \"D_{7}\" will result in seven 14-gons. By the Euler’s Characteristic formula, \"\chi=-28\", so \"g=15\".

Case 2. Using group \"Z_{14}\":<\/strong>
By Lemma 2, the best rotation for \"{K_{7,7}}\" using \"Z_{14}\" results in fourteen 4-gons and seven 6-gons. By the Euler’s Characteristic formula, \"\chi=-14\", thus, \"g=8\".

Therefore, an eight-holed torus is the best surface \"{K_{7,7}}\" can embed when using a Cayley Map.<\/p>\n\n\n\n
<\/div>\n\n\n\n
\n\n\n\n
Lemma 3 <\/strong>If \"\rho(x)=x^{-1}\", then \"(x^{-1}) \in \mathcal{F}\".<\/em>

Proof- <\/em>Let \"\rho(x)=x^{-1}\". Since \"\lambda(x^{-1})=\rho(x)=x^{-1}\", there exists a \"(x^{-1})\" face in \"\mathcal{F}\".<\/p>\n\n\n\n
<\/div>\n\n\n\n
\n\n\n\n
Lemma 4 <\/strong>If \"\rho(x)=y\" and \"\rho(y^{-1})=x^{-1}\", then \"(x^{-1}y) \in F\".<\/em>

Proof- <\/em>Let \"\rho(x)=y\" and \"\rho(y^{-1})=x^{-1}\". Since \"\lambda(y)=\rho(y^{-1})=x^{-1}\" and \"\lambda(x^{-1})=\rho(x)=y\", there exists a \"(x^{-1}y)\" face in \"\mathcal{F}\".<\/p>\n\n\n\n
<\/div>\n\n\n\n
\n\n\n\n
Lemma 5 <\/strong>There does not exist a rotation for \"{K_{11,11}}\" such that the resulting face set includes a 4-gon with two distinct elements.<\/em><\/p>\n\n\n\n
Proof-<\/em> (Proof by Contradiction) Suppose there exists a rotation for \"{K_{11,11}}\" such that the resulting face set includes a 4-gon with two distinct elements, \"x\" and \"y\". Therefore, \"2(x+y)\bmod{22}=0\". Since \"x\" and \"y\" are odd, \"x+y \neq 11\" or \"33\". The sum of the highest two elements in \"\rho\" is 40, so \"x+y \neq 44\". Therefore, \"x+y=22\". This contradicts Theorem 1.<\/p>\n\n\n\n
<\/div>\n\n\n\n
\n\n\n\n
Theorem 7 (\"{K_{11,11}}\" Two 4-gons and a 6-gon Theorem) <\/strong>There does not exist a rotation for \"{K_{11,11}}\" such that the resulting faces are two distinct 4-gons and a 6-gon.<\/em><\/p>\n\n\n\n
Proof-<\/em> Case 1: \"D_{11}\"<\/strong>
By Theorem 4, rotations using \"D_{11}\" will only ever result in 22-gons.

Case 2: \"Z_{22}\" (Proof by Contradiction)<\/strong>
Let \"A\", \"B\", and \"C\" represent the three distinct faces, where \"A\" and \"B\" are the 4-gons and \"C\" is the 6-gon, such that \"A=(a\" \"b\" \"c\" \"d\"), \"B=(c^{-1}\" \"d^{-1}\" \"e\" \"11),\" and \"C=(a^{-1}\" \"b^{-1}\" \"e^{-1})\". For simplification purposes, we remove the 11 and let \"B=(c^{-1}\" \"d^{-1}\" \"e)\". This will not affect the results since 11 is its own inverse and we can place it back into the rotation at the end. By labeling an empty 10-branched graph with \"A\"s, \"B\"s, and \"C\"s, we can form a template for the graph’s rotation.<\/p>\n\n\n\n
The only rotation that could form two distinct 4-gons and a 6-gon follows the template \"(ABCABACBAC)\":<\/strong>
Because faces \"B\" and \"C\" only share one inverse pairing (\"e\" and \"e^{-1}),\" \"\dots CBC \dots\" and \"\dots BCB \dots\" \"\notin \rho\", and \"\dots CB \dots\" and \"\dots BC \dots\" can each only appear once in the rotation. Since \"A\" and \"B\" share two inverse pairs (\"c\", \"c^{-1}\", \"d\", and \"d^{-1}\"), \"\dots BABA \dots\" and \"\dots ABAB \dots\" \"\notin \rho\", and \"\dots AB \dots\" and \"\dots BA \dots\" each appear twice. Similarly, \"\dots ACAC \dots\" and \"\dots CACA \dots\" \"\notin \rho\", and\"\dots AC \dots\" and \"\dots CA \dots\" only appear twice. No face contains a pair of inverses, therefore \"\dots AA \dots\", \"\dots BB \dots\", and \"\dots CC \dots\" cannot occur in \"\rho\". Finally, there must be four \"A\"s, three \"B\"s, and three \"C\"s, since each face has that amount of elements.
By exhausting all possibilities, the only rotations that satisfy those requirements are \"(ABACBACABC)\" and \"(ABCABACBAC)\", which are the same rotation.<\/p>\n\n\n\n
When assigning a specific element to a letter in the rotation template, the following letter must also be considered. For instance, for \"ABC \dots\" the element for \"A\" must be an inverse to an element in \"B\", and the element for \"B\" must be an inverse to an element in \"C\". Thus \"\rho = (A_B\" \"B_C\" \"C_A\" \"A_B\" \"B_A\" \"A_C\" \"C_B\" \"B_A\" \"A_C\" \"C_A)\", where the subscript denotes the location of an inverse. Notice there are two occurrences of \"C_AA_B\" and \"B_AA_C\" in the rotation, and these two pairs of elements are adjacent in both instances. The possible elements for each pair are: \"C_AA_B \in {a^{-1}c,b^{-1}d,a^{-1}d,b^{-1}c}\" and \"B_AA_C \in {c^{-1}a,d^{-1}b,c^{-1}b,d^{-1}a}\". There are 32 combinations of elements for \"C_AA_BB_AA_C\" and \"B_AA_CC_AA_B\"; however, by Lemma 3, 24 of the combinations are not possible. Since the same element cannot appear in both \"C_AA_BB_AA_C\" and \"B_AA_CC_AA_B\", there are four remaining possibilities for assigning elements to \"C_AA_BB_AA_C \dots B_AA_CC_AA_B\": \"(a^{-1}c,d^{-1}b) \dots (c^{-1}a,b^{-1}d)\", \"(a^{-1}d,c^{-1}b)\dots (d^{-1}a,b^{-1}c)\", \"(b^{-1}d,c^{-1}a)\dots (d^{-1}b,a^{-1}c)\",  and \"(b^{-1}c,d^{-1}a)\dots\" \"(c^{-1}b,a^{-1}d)\".  By Lemma 4, using these rotations will produce two distinct faces, each made of two distinct elements. At least one of these must be a 4-gon, which contradicts Lemma 5. Therefore it is impossible that either of the faces are 4-gons, and becasue one of the combinations for \"C_AA_BB_AA_C \dots B_AA_CC_AA_B\" must be in the rotation, the rotation template \"(ABCABACBAC)\" does not produce two distinct 4-gons and a 6-gon.
Therefore, there does not exist a rotation for \"{K_{11,11}}\" such that the resulting faces are two distinct 4-gons and a 6-gon.<\/p>\n\n\n\n
<\/div>\n\n\n\n
\n\n\n\n
Theorem 8 <\/strong>There does not exist a rotation for \"{K_{11,11}}\" such that the resulting face set is a combination of only 4-gons and 6-gons.<\/em><\/p>\n\n\n\n
Proof-<\/em>  There are a total of 11 elements in a rotation for \"{K_{11,11}}\". By Lemma 5, each distinct 4-gon uses 4 elements from \"\rho\", and the 6-gon uses 3 or 6 elements.
Case 1: One distinct 4-gon and one distinct 6-gon.<\/strong>
Since \"1(4)+1(3)\neq11\" and \"1(4)+1(6)\neq11\", there does not exist a rotation that results in one distinct 4-gon and one distinct 6-gon.

Case 2: Two distinct 4-gons and one distinct 6-gon.<\/strong>
By Theorem 7, there does not exist a rotation that results in two distinct 4-gons and one distinct 6-gon.

Case 3: Three or more distinct 4-gons.<\/strong>
Since \"3(4)=12>11\", there does not exist a rotation that results in three or more distinct 4-gons.

Case 4: One distinct 4-gon and two distinct 6-gons.<\/strong>
Since \"1(4)+2(3)\neq11\" and \"1(4)+2(6)\neq11\", there does not exist a rotation that results in one distinct 4-gon and two distinct 6-gons.

Case 5: One or more distinct 4-gons and three or more distinct 6-gons.<\/strong>
Since \"1(4)+3(3)>11\", there does not exist a rotation that results in one or more distinct 4-gons and three or more distinct 6-gons.

Case 6: Two distinct 4-gons and two distinct 6-gons.<\/strong>
Since \"2(4)+2(3)\neq11\" and \"2(4)+2(6)\neq11\", there does not exist a rotation that results in two distinct 4-gons and two distinct 6-gons.
Therefore, there does not exist a rotation for \"{K_{11,11}}\" such that the resulting face set is a combination of 4-gons and 6-gons.<\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
Theorem 1 (Inverse Theorem) If there exists a face, $F_0$, that is closed with respect to inverses and resulted from rotation $\\rho$, then every element in $\\rho$ is in $F_0$. Proof- Suppose there exists a face, $F_0$, that is closed with respect to inverses and resulted from rotation $\\rho$. Let $x$ be an arbitrary element […]<\/p>\n","protected":false},"author":5,"featured_media":0,"parent":97,"menu_order":9,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-48","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/blogs.rollins.edu\/graphembeddings\/wp-json\/wp\/v2\/pages\/48","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.rollins.edu\/graphembeddings\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/blogs.rollins.edu\/graphembeddings\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.rollins.edu\/graphembeddings\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.rollins.edu\/graphembeddings\/wp-json\/wp\/v2\/comments?post=48"}],"version-history":[{"count":59,"href":"https:\/\/blogs.rollins.edu\/graphembeddings\/wp-json\/wp\/v2\/pages\/48\/revisions"}],"predecessor-version":[{"id":426,"href":"https:\/\/blogs.rollins.edu\/graphembeddings\/wp-json\/wp\/v2\/pages\/48\/revisions\/426"}],"up":[{"embeddable":true,"href":"https:\/\/blogs.rollins.edu\/graphembeddings\/wp-json\/wp\/v2\/pages\/97"}],"wp:attachment":[{"href":"https:\/\/blogs.rollins.edu\/graphembeddings\/wp-json\/wp\/v2\/media?parent=48"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}