Semi-random Process Without Replacement

Shoni Gilboa, Dan Hefetz

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرفصلمراجعة النظراء


We introduce and study a semi-random multigraph process, which forms a no-replacement variant of the process that was introduced in [3]. The process starts with an empty graph on the vertex set [n]. For every positive integers q and 1 ≤ r≤ n, in the ((q- 1 ) n+ r) th round of the process, the decision-maker, called Builder, is offered the vertex πq(r), where π1, π2, … is a sequence of permutations in Sn, chosen independently and uniformly at random. Builder then chooses an additional vertex (according to a strategy of his choice) and connects it by an edge to πq(r). For several natural graph properties, such as k-connectivity, minimum degree at least k, and building a given spanning graph (labeled or unlabeled), we determine the typical number of rounds Builder needs in order to construct a graph having the desired property. Along the way we introduce and analyze two urn models which may also have independent interest.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفExtended Abstracts EuroComb 2021
المحررونJaroslav Nešetřil
ناشرSpringer Nature
عدد الصفحات7
رقم المعيار الدولي للكتب (المطبوع)9783030838225
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2021
الحدثEuropean Conference on Combinatorics, Graph Theory and Applications 2021 - Barcelona, أسبانيا
المدة: ٦ سبتمبر ٢٠٢١١٠ سبتمبر ٢٠٢١

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

الاسمTrends in Mathematics
مستوى الصوت14
رقم المعيار الدولي للدوريات (المطبوع)2297-0215
رقم المعيار الدولي للدوريات (الإلكتروني)2297-024X


!!ConferenceEuropean Conference on Combinatorics, Graph Theory and Applications 2021

ملاحظة ببليوغرافية

Funding Information:
D. Hefetz—Research supported by ISF grant 822/18.

Publisher Copyright:
© 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.


أدرس بدقة موضوعات البحث “Semi-random Process Without Replacement'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا