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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2021
אירועEuropean Conference on Combinatorics, Graph Theory and Applications 2021 - Barcelona, ספרד
משך הזמן: 6 ספט׳ 202110 ספט׳ 2021

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

שםTrends in Mathematics
מוציא לאורSpringer
ISSN (מודפס)2297-0215
ISSN (אלקטרוני)2297-024X


כנסEuropean Conference on Combinatorics, Graph Theory and Applications 2021

הערה ביבליוגרפית

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

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Semi-random Process Without Replacement'. יחד הם יוצרים טביעת אצבע ייחודית.

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