scientific article; zbMATH DE number 3843773

From MaRDI portal
Publication:3313879





Let \(G\) be a connected graph having \(n\) edges, with \(S=\{(u,v)\mid [u,v]\varepsilon E(G)\}\). Let G be 2-cell embedded on \(S_ k\), the closed orientable 2-manifold of genus \(k\). The orientation on \(S_k\) induces a permutation \(Q\) on \(S\), each of whose cycles consists of the set of arcs emanating from one vertex, cyclically ordered by the orientation of \(S_k\); \(Q\) is called a rotation for \(G\). Let \(P\) be the involutionary permutation of \(S\) that associates each arc with its inverse. Then the number of orbits of the product \(PQ\) is the number of regions of the embedding and hence determines the genus \(k\). Then the average genus for \(G\) would be taken over all possible rotations for \(G\). The author extends these ideas to arbitrary (i.e., possibly disconnected) pseudo-graphs on a fixed number of edges and obtains the following results: 1) The average genus of all embeddings of all pseudographs on \(e\) edges is \[\frac{e}{2}-\log(2e)+1- C+O\left(\frac{1}{e}\right),\] where \(C\) is the Euler constant \(0,577\dots\). 2) Among all embeddings of all cubic pseudographs with \(e\) (odd) edges, the proportion of those with only one region (thereby giving the maximum genus of the pseudograph) is \(\frac{1}{e}+ O(\frac{1}{e^2})\). The proof techniques involve standard counting procedures and an analysis of the characters of the symmetric group (acting on \(S)\). [For the entire collection see Zbl 0523.00001.]











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3313879)