## Abstract

We investigate the genus g(n,m) of the Erdös-Rényi random graph G(n,m), providing a thorough description of how this relates to the function m=m(n), and finding that there is different behaviour depending on which 'region' m falls into.

Existing results are known for when m is at most n/(2) + O(n^{2/3}) and when m is at least omega (n^{1+1/(j)}) for j in N, and so we focus on intermediate cases.

In particular, we show that g(n,m) = (1+o(1)) m/(2) whp (with high probability) when n << m = n^{1+o(1)}; that g(n,m) = (1+o(1)) mu (lambda) m whp for a given function mu (lambda) when m ~ lambda n for lambda > 1/2; and that g(n,m) = (1+o(1)) (8s^3)/(3n^2) whp when m = n/(2) + s for n^(2/3) << s << n.

We then also show that the genus of fixed graphs can increase dramatically if a small number of random edges are added. Given any connected graph with bounded maximum degree, we find that the addition of epsilon n edges will whp result in a graph with genus Omega (n), even when epsilon is an arbitrarily small constant! We thus call this the `fragile genus' property.

Existing results are known for when m is at most n/(2) + O(n^{2/3}) and when m is at least omega (n^{1+1/(j)}) for j in N, and so we focus on intermediate cases.

In particular, we show that g(n,m) = (1+o(1)) m/(2) whp (with high probability) when n << m = n^{1+o(1)}; that g(n,m) = (1+o(1)) mu (lambda) m whp for a given function mu (lambda) when m ~ lambda n for lambda > 1/2; and that g(n,m) = (1+o(1)) (8s^3)/(3n^2) whp when m = n/(2) + s for n^(2/3) << s << n.

We then also show that the genus of fixed graphs can increase dramatically if a small number of random edges are added. Given any connected graph with bounded maximum degree, we find that the addition of epsilon n edges will whp result in a graph with genus Omega (n), even when epsilon is an arbitrarily small constant! We thus call this the `fragile genus' property.

Original language | English |
---|---|

Title of host publication | 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) |

Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |

Pages | 17:1--17:13 |

Number of pages | 17 |

ISBN (Print) | 978-3-95977-078-1 |

DOIs | |

Publication status | Published - 2018 |

Event | 29th International Conference on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms: AofA 2018 - Uppsala University, Uppsala, Sweden Duration: 25 Jun 2018 → 29 Jun 2018 |

### Publication series

Name | Leibniz International Proceedings in Informatics |
---|---|

Volume | 110 |

### Conference

Conference | 29th International Conference on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms |
---|---|

Abbreviated title | AofA 2018 |

Country/Territory | Sweden |

City | Uppsala |

Period | 25/06/18 → 29/06/18 |

## Fields of Expertise

- Information, Communication & Computing