The Genus of a Random Bipartite Graph

Jing, Yifan ; Mohar, Bojan

Canadian journal of mathematics, Tome 72 (2020) no. 6, pp. 1607-1623

Résumé

Archdeacon and Grable (1995) proved that the genus of the random graph $G\in {\mathcal{G}}_{n,p}$ is almost surely close to $pn^{2}/12$ if $p=p(n)\geqslant 3(\ln n)^{2}n^{-1/2}$. In this paper we prove an analogous result for random bipartite graphs in ${\mathcal{G}}_{n_{1},n_{2},p}$. If $n_{1}\geqslant n_{2}\gg 1$, phase transitions occur for every positive integer $i$ when $p=\unicode[STIX]{x1D6E9}((n_{1}n_{2})^{-i/(2i+1)})$. A different behaviour is exhibited when one of the bipartite parts has constant size, i.e., $n_{1}\gg 1$ and $n_{2}$ is a constant. In that case, phase transitions occur when $p=\unicode[STIX]{x1D6E9}(n_{1}^{-1/2})$ and when $p=\unicode[STIX]{x1D6E9}(n_{1}^{-1/3})$.

Détail

DOI : 10.4153/S0008414X19000440

Mots-clés : Genus, graph genus, topological embedding, surface embedding, random bipartite graph

Bibliographie

[1] Alon, N. and Spencer, J. H., The probabilistic method, Fourth ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. Google Scholar

[2] Archdeacon, D. and Grable, D. A., The genus of a random graph. Discrete Math. 142(1995), 1–3, 21–37. https://doi.org/10.1016/0012-365X(95)00215-I Google Scholar | DOI

[3] Bollobás, B., Random graphs, Second ed., Cambridge Studies in Advanced Mathematics, 73, Cambridge University Press, Cambridge, 2001. https://doi.org/10.1017/CBO9780511814068 Google Scholar | DOI

[4] Diestel, R., Graph theory, Fourth ed., Graduate Texts in Mathematics, 173, Springer, Heidelberg, 2010. https://doi.org/10.1007/978-3-642-14279-6 Google Scholar | DOI

[5] Frankl, P. and Rödl, V., Near perfect coverings in graphs and hypergraphs. European J. Combin. 6(1985), 317–326. https://doi.org/10.1016/S0195-6698(85)80045-7 Google Scholar | DOI

[6] Jing, Y. and Mohar, B., The genus of complete 3-uniform hypergraphs. J. Combin. Theory Ser. B 141(2020), 223–239. https://doi.org/10.1016/j.jctb.2019.08.002 Google Scholar | DOI

[7] Jing, Y. and Mohar, B., Efficient polynomial-time approximation scheme for the genus of dense graphs. In: 59th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2018. IEEE Computer Soc., Los Alamitos, CA, 2018, pp. 719–730. Google Scholar

[8] Mohar, B. and Thomassen, C., Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2001. Google Scholar

[9] Parsons, T. D., Pica, G., Pisanski, T., and Ventre, A. G. S., Orientably simple graphs. Math. Slovaca 37(1987), 391–394. Google Scholar

[10] Pippenger, N. and Spencer, J., Asymptotic behavior of the chromatic index for hypergraphs. J. Combin. Theory Ser. A 51(1989), 24–42. https://doi.org/10.1016/0097-3165(89)90074-5 Google Scholar | DOI

[11] Ringel, G., Das Geschlecht des vollständigen paaren Graphen. Abh. Math. Sem. Univ. Hamburg 28(1965), 139–150. https://doi.org/10.1007/BF02993245 Google Scholar | DOI

[12] Ringel, G. and Youngs, J. W. T., Solution of the Heawood map-coloring problem. Proc. Natl Acad. Sci. USA 60(1968), 438–445. https://doi.org/10.1073/pnas.60.2.438 Google Scholar PubMed | DOI

[13] Rödl, V. and Thomas, R., On the genus of a random graph. Random Structures Algorithms 6(1995), 1–12. https://doi.org/10.1002/rsa.3240060102 Google Scholar | DOI

[14] Stahl, S., On the average genus of the random graph. J. Graph Theory 20(1995), 1–18. https://doi.org/10.1002/jgt.3190200102 Google Scholar | DOI

[15] Thomassen, C., The graph genus problem is NP-complete. J. Algorithms 10(1989), 568–576. https://doi.org/10.1016/0196-6774(89)90006-0 Google Scholar | DOI

[16] Youngs, J. W. T., Minimal imbeddings and the genus of a graph. J. Math. Mech. 12(1963), 303–315. Google Scholar