کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5773268 | 1631066 | 2017 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Shift lifts preserving Ramanujan property
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
اعداد جبر و تئوری
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In a breakthrough work, Marcus et al. [1] recently showed that every d-regular bipartite Ramanujan graph has a 2-lift that is also d-regular bipartite Ramanujan. As a consequence, a straightforward iterative brute-force search algorithm leads to the construction of a d-regular bipartite Ramanujan graph on N vertices in time 2O(dN). Shift k-lifts studied in [2] lead to a natural approach for constructing Ramanujan graphs more efficiently. The number of possible shift k-lifts of a d-regular n-vertex graph is knd/2. Suppose the following holds for k=2Ω(n):(â)There exists a shift k-lift that maintains the Ramanujanproperty of d-regular bipartite graphson n vertices for all n. Then, by performing a similar brute-force algorithm, one would be able to construct an N-vertex bipartite Ramanujan graph in time 2O(dlog2â¡N). Also, if (â) holds for all kâ¥2, then one would obtain an algorithm that runs in poly(Nd) time. In this work, we take a first step towards proving (â) by showing the existence of shift k-lifts that preserve the Ramanujan property in d-regular bipartite graphs for k=3 and for k=4.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 529, 15 September 2017, Pages 199-214
Journal: Linear Algebra and its Applications - Volume 529, 15 September 2017, Pages 199-214
نویسندگان
Karthekeyan Chandrasekaran, Ameya Velingker,