Expanders with respect to Hadamard spaces and random graphs

Manor Mendel, Assaf Naor

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


It is shown that there exist a sequence of 3-regular graphs {Gn}n=1 and a Hadamard space X such that {Gn}n=1 forms an expander sequence with respect to X, yet random regular graphs are not expanders with respect to X. This answers a question of the second author and Silberman. The graphs {Gn}n=1 are also shown to be expanders with respect to random regular graphs, yielding a deterministic sublineartime constant-factor approximation algorithm for computing the average squared distance in subsets of a random graph. The proof uses the Euclidean cone over a random graph, an auxiliary continuous geometric object that allows for the implementation of martingale methods.

שפה מקוריתאנגלית
עמודים (מ-עד)1471-1548
מספר עמודים78
כתב עתDuke Mathematical Journal
מספר גיליון8
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2015

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

Publisher Copyright:
© 2015.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Expanders with respect to Hadamard spaces and random graphs'. יחד הם יוצרים טביעת אצבע ייחודית.

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