We know that planar graphs have $O(1)$ degree.

We know balanced (each color has same number of vertices) complete bipartite graphs have genus $O(n^2)$.

  1. If maximum and average degree are $O(n^\alpha)$ where $\alpha\in[0,1]$ then is genus also $O(n^\alpha)$?

  2. If maximum degree is $O(n^\alpha)$ where $\alpha\in[0,1]$ then is genus also $O(n^\alpha)$? (this is weaker than $1.$)

  • $\begingroup$ What is n? is it the coloring number of the graph? $\endgroup$ – Ori Gurel-Gurevich Jul 23 '17 at 6:46
  • $\begingroup$ The average degree is less then (or equal to) the maximum degree, so I guess I don't understand the difference between 1 and 2. $\endgroup$ – Ori Gurel-Gurevich Jul 23 '17 at 6:47
  • $\begingroup$ @OriGurel-Gurevich number of vertices is $n$ per color (so $2n$ is total number of vertices). I only look at bipartite graph genus. $\endgroup$ – Turbo Jul 23 '17 at 6:50
  • $\begingroup$ @OriGurel-Gurevich sometimes max degree could be much larger than average degree. $\endgroup$ – Turbo Jul 23 '17 at 6:50
  • $\begingroup$ Still, the conditions in 1 and 2 are equivalent, aren't they? $\endgroup$ – Ori Gurel-Gurevich Jul 23 '17 at 6:52

The answer is no. Hossein Namazi, Pekka Pankka, Juan Souto showed that expander graphs have genus that is linear in the number of vertices. You can construct bipartite, bounded degree expanders.

  • $\begingroup$ bounded meaning degree $\leq 3$ possible? $\endgroup$ – Turbo Jul 23 '17 at 8:20
  • $\begingroup$ Sure. A random 3-regular graph is an expander with high probability. If you want it to be bipartite, just replace every edge with a path of length 2. $\endgroup$ – Ori Gurel-Gurevich Jul 23 '17 at 15:41

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.