The genus of the Erdos-Rényi random graph and the fragile genus property

Chris Dowden, Mihyun Kang, Michael Krivelevich

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

We investigate the genus g(n,m) of the Erdos-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 {equation Presented} and when m is at least {equation Presented} and so we focus on intermediate cases. In particular, we show that {equation Presented} whp (with high probability) when {equation Presented} whp for a given function μ(λ) when m ~ λn for {equation Presented}. 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 n edges will whp result in a graph with genus (n), even when is an arbitrarily small constant! We thus call this the 'fragile genus' property.

שפה מקוריתאנגלית
כותר פרסום המארח29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018
עורכיםMark Daniel Ward, James Allen Fill
מסת"ב (אלקטרוני)9783959770781
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 יוני 2018
אירוע29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018 - Uppsala, שבדיה
משך הזמן: 25 יוני 201829 יוני 2018

סדרות פרסומים

שםLeibniz International Proceedings in Informatics, LIPIcs
כרך110

כנס

כנס29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018
מדינה/אזורשבדיה
עירUppsala
תקופה25/06/1829/06/18

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???

פורמט ציטוט ביבליוגרפי