10
$\begingroup$

I have ask this question in math.stackexchange, here. Since, there is no answer and apart from that i feel that the problem is difficult, i would like to ask it here. The problem is to find the genus of $K_{4,2,2,2}$. I want a theoretical technique(if possible), otherwise using sage programming is good enough. I have tried using sage for a week now, but my computer is too slow. Thanks for any help.

The graph $K_{4,2,2,2}$ is a complete $4-$partite graph, that is, its vertex set can be partition into 4 disjoint parts of size 4, 2, 2 and 2, and any two vertices are adjacent if and only if they belong to different parts.

$\endgroup$
  • 2
    $\begingroup$ See question mathoverflow.net/questions/157894/genus-of-the-graph-k-m-2-2-2 $\endgroup$ – F. C. Mar 27 '14 at 8:14
  • 3
    $\begingroup$ @F.C. But that question has no answer. If that question has an answer, then it will be an answer to this question also. $\endgroup$ – bor Mar 27 '14 at 8:34
  • 6
    $\begingroup$ One lower bound is the genus of $K_{4,4,2}$, which is $2$. An upper bound is the genus of $K_{10}$, which is $4$. $\endgroup$ – Douglas Zare Mar 27 '14 at 9:14
  • 2
    $\begingroup$ Since the answer is between $2$ and $4$, as shown by @DouglasZare, you might want to try the algebraic approach of Diestel and Bruhn (sciencedirect.com/science/article/pii/S0095895608000476). In fact, you might want to contact Henning Bruhn who might be able to compute this for you using their characterization! $\endgroup$ – Felix Goldberg Mar 27 '14 at 10:14
  • 2
    $\begingroup$ If I'm not misreading, Theorem 4.1 from the reference given by David Wood states that the genus of the complete k-partite graph with partitions of sizes $V_1,V_2,\dots,V_k$ is $\sum_{i<j}\left\lceil\frac{(V_i-2)(V_j-2)}{4}\right\rceil+\left\lceil\frac{(k-3)(k-4)}{12}\right\rceil$, which gives zero for your graph. It also gives 1 for $K_{4,4,2}$ so I'm not sure what's going on. $\endgroup$ – j.c. Mar 27 '14 at 11:24
12
$\begingroup$

I understand it's been years since this question was asked, but I figured I should give an answer for anyone still interested.

From the Euler equation, if $K_{4,2,2,2}$ has genus 2, it would actually triangulate $S_2$. Searching for triangular embeddings is much quicker than enumerating over all embeddings (as sage does). In fact, Jungerman was able to find a triangular embedding of $K_{18}-K_3$ in about half an hour back in the 1970s. Applying such an algorithm on $K_{4,2,2,2}$ shows that it has no such embedding on $S_2$.

Not only is $K_{4,2,2,2}$ a subgraph of $K_{10}$, as observed by @Douglas Zare, but it is a subgraph of $K_{10}-K_3$ as well, which has genus 3 (see Youngs, "The Heawood Map-Coloring Problem--Cases 1, 7, 10").

These two parts together show that the genus of $K_{4,2,2,2}$ is 3.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.