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.

Improve this question
$\endgroup$
12
  • 2
    $\begingroup$ See question mathoverflow.net/questions/157894/genus-of-the-graph-k-m-2-2-2 $\endgroup$
    – F. C.
    Commented Mar 27, 2014 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
    Commented Mar 27, 2014 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
    Commented Mar 27, 2014 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
    Commented Mar 27, 2014 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.
    Commented Mar 27, 2014 at 11:24

1 Answer 1

Reset to default
14
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .