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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 يونيو 2018
الحدث29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018 - Uppsala, السويد
المدة: ٢٥ يونيو ٢٠١٨٢٩ يونيو ٢٠١٨

سلسلة المنشورات

الاسمLeibniz International Proceedings in Informatics, LIPIcs
مستوى الصوت110

!!Conference

!!Conference29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018
الدولة/الإقليمالسويد
المدينةUppsala
المدة٢٥/٠٦/١٨٢٩/٠٦/١٨

All Science Journal Classification (ASJC) codes

  • !!Software

قم بذكر هذا