Kp,p Theorems

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 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$ .

Theorem 2 (2-gon Theorem) There does not exist a 2-gon face for ${K_{p,p}}$ using $Z_{2p}$ .

Proof- Case 1. $p=2$ : 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$ : 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}$ .

Theorem 3 (Odd-gon Theorem) There does not exist a face with an odd number of sides (an “odd-gon”) for ${K_{p,p}}$ using $Z_{2p}$ .

Proof- 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}$ .

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

Proof- 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.

Lemma 1 ( $K_{5,5}$ Smallest Face using $Z_{10}$ ) The smallest face size possible for ${K_{5,5}}$ using $Z_{10}$ is $10$ .

Proof- There exists a rotation that produces 10-gons for

*** QuickLaTeX cannot compile formula:
{K_{5,5}

*** Error message:
Missing } inserted.
leading text: ${K_{5,5}$

using $Z_{10}$ :
Let

*** QuickLaTeX cannot compile formula:
\rho=(1 \hspace{2} 7\hspace{2} 5\hspace{2} 3 \hspace{2} 9)

*** Error message:
Illegal unit of measure (pt inserted).
leading text: $\rho=(1 \hspace{2}

. The resulting face set is

*** QuickLaTeX cannot compile formula:
F= {(5 \hspace{3} 3)(7 \hspace{3} 9)(1)}

*** Error message:
Illegal unit of measure (pt inserted).
leading text: $F= {(5 \hspace{3}

, all of which are 10-gons.

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

Case 2. 2-gons:
By the Theorem 2, there does not exist a $2$ -gon face for ${K_{5,5}}$ using $Z_{10}$ .

Case 3. 4-gons:
a) The 4-gon is formed by two distinct elements:
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:
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}$ .

Case 4. 6-gons
a) The 6-gon is formed by two distinct elements:
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:
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}$ .

Case 5. 8-gons:
a) The 8-gon is formed by two distinct elements:
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:
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}$ .

Theorem 5 (The Best $C_M$ Genus for ${K_{5,5}}$ ) The optimal genus for ${K_{5,5}}$ using a Cayley Map is $g=6$ .

Proof- 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$ .

Lemma 2 (The Best Rotation for ${K_{7,7}}$ using $Z_{14}$ ) The best rotation possible for ${K_{7,7}}$ using $Z_{14}$ produces 4-gons and 6-gons.

Proof- There exists a rotation for ${K_{7,7}}$ using $Z_{14}$ that produces fourteen 4-gons and seven 6-gons:
Let $\rho=(5$ $1$ $3$ $7$ $9$ $13$ $11)$ . $\rho$ produces

*** QuickLaTeX cannot compile formula:
\mathcal{F}={(1

*** Error message:
Missing } inserted.
leading text: $\mathcal{F}={(1$

$11$ $7$ $9),(5$ $13$

*** QuickLaTeX cannot compile formula:
3)}

*** Error message:
Extra }, or forgotten $.
leading text: $3)}

, 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:
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.

Lemma 2 (The Best Rotation for ${K_{7,7}}$ using $Z_{14}$ ) The best rotation possible for ${K_{7,7}}$ using $Z_{14}$ produces fourteen 4-gons and seven 6-gons.

Proof- Case 1: 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. 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: The 4-gon, $F_0$ , is produced by four distinct elements, and the 6-gon, $F_1$ , is produced by three distinct elements. By Equation 2, $m_0=1$ and $m_1=2$ . By Equation 3, there are fourteen 4-gons and seven 6-gons.
Case 3: The 4-gon, $F_0$ , is produced by one distinct element, and the 6-gon, $F_1$ , is produced by six distinct elements. 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.

Theorem 6 (Best $C_M$ genus for ${K_{7,7}}$ ) The best possible genus for ${K_{7,7}}$ when using a Cayley Map is $g=8$ .

Proof- Case 1. Using group $D_{7}$ :
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}$ :
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.

Lemma 3 If $\rho(x)=x^{-1}$ , then $(x^{-1}) \in \mathcal{F}$ .

Proof- Let $\rho(x)=x^{-1}$ . Since $\lambda(x^{-1})=\rho(x)=x^{-1}$ , there exists a $(x^{-1})$ face in $\mathcal{F}$ .

Lemma 4 If $\rho(x)=y$ and $\rho(y^{-1})=x^{-1}$ , then $(x^{-1}y) \in F$ .

Proof- 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}$ .

Lemma 5 There does not exist a rotation for ${K_{11,11}}$ such that the resulting face set includes a 4-gon with two distinct elements.

Proof- (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.

Theorem 7 ( ${K_{11,11}}$ Two 4-gons and a 6-gon Theorem) There does not exist a rotation for ${K_{11,11}}$ such that the resulting faces are two distinct 4-gons and a 6-gon.

Proof- Case 1: $D_{11}$
By Theorem 4, rotations using $D_{11}$ will only ever result in 22-gons.

Case 2: $Z_{22}$ (Proof by Contradiction)
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.

The only rotation that could form two distinct 4-gons and a 6-gon follows the template $(ABCABACBAC)$ :
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.

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.

Theorem 8 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.

Proof- 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.
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.
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.
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.
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.
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.
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.

Graph Embeddings

Menu