Diameter of Ramanujan Graphs and Random Cayley Graphs

Naser T. Sardari

doi:10.1007/s00493-017-3605-0

Diameter of Ramanujan Graphs and Random Cayley Graphs

Naser T. Sardari

Mathematics

Research output: Contribution to journal › Article › peer-review

14 Scopus citations

Abstract

We study the diameter of LPS Ramanujan graphs X_p,q. We show that the diameter of the bipartite Ramanujan graphs is greater than (4/3)log_p(n)+O(1), where n is the number of vertices of X_p,q. We also construct an infinite family of (p+1)-regular LPS Ramanujan graphs X_p,m such that the diameter of these graphs is greater than or equal to ⌊(4/3)log_p(n)⌋. On the other hand, for any k-regular Ramanujan graph we show that only a tiny fraction of all pairs of vertices have distance greater than (1+ϵ) log_k–1(n). We also have some numerical experiments for LPS Ramanujan graphs and random Cayley graphs which suggest that the diameters are asymptotically (4/3)log_k–1(n) and log_k–1(n), respectively.

Original language	English (US)
Pages (from-to)	427-446
Number of pages	20
Journal	Combinatorica
Volume	39
Issue number	2
DOIs	https://doi.org/10.1007/s00493-017-3605-0
State	Published - Apr 1 2019

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-017-3605-0

Cite this

@article{4a53a2cf75194777888bd2f7a1ec663d,

title = "Diameter of Ramanujan Graphs and Random Cayley Graphs",

abstract = "We study the diameter of LPS Ramanujan graphs Xp,q. We show that the diameter of the bipartite Ramanujan graphs is greater than (4/3)logp(n)+O(1), where n is the number of vertices of Xp,q. We also construct an infinite family of (p+1)-regular LPS Ramanujan graphs Xp,m such that the diameter of these graphs is greater than or equal to ⌊(4/3)logp(n)⌋. On the other hand, for any k-regular Ramanujan graph we show that only a tiny fraction of all pairs of vertices have distance greater than (1+ϵ) logk–1(n). We also have some numerical experiments for LPS Ramanujan graphs and random Cayley graphs which suggest that the diameters are asymptotically (4/3)logk–1(n) and logk–1(n), respectively.",

author = "Sardari, {Naser T.}",

note = "Publisher Copyright: {\textcopyright} 2018, J{\'a}nos Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.",

year = "2019",

month = apr,

day = "1",

doi = "10.1007/s00493-017-3605-0",

language = "English (US)",

volume = "39",

pages = "427--446",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "2",

}

TY - JOUR

T1 - Diameter of Ramanujan Graphs and Random Cayley Graphs

AU - Sardari, Naser T.

PY - 2019/4/1

Y1 - 2019/4/1

N2 - We study the diameter of LPS Ramanujan graphs Xp,q. We show that the diameter of the bipartite Ramanujan graphs is greater than (4/3)logp(n)+O(1), where n is the number of vertices of Xp,q. We also construct an infinite family of (p+1)-regular LPS Ramanujan graphs Xp,m such that the diameter of these graphs is greater than or equal to ⌊(4/3)logp(n)⌋. On the other hand, for any k-regular Ramanujan graph we show that only a tiny fraction of all pairs of vertices have distance greater than (1+ϵ) logk–1(n). We also have some numerical experiments for LPS Ramanujan graphs and random Cayley graphs which suggest that the diameters are asymptotically (4/3)logk–1(n) and logk–1(n), respectively.

AB - We study the diameter of LPS Ramanujan graphs Xp,q. We show that the diameter of the bipartite Ramanujan graphs is greater than (4/3)logp(n)+O(1), where n is the number of vertices of Xp,q. We also construct an infinite family of (p+1)-regular LPS Ramanujan graphs Xp,m such that the diameter of these graphs is greater than or equal to ⌊(4/3)logp(n)⌋. On the other hand, for any k-regular Ramanujan graph we show that only a tiny fraction of all pairs of vertices have distance greater than (1+ϵ) logk–1(n). We also have some numerical experiments for LPS Ramanujan graphs and random Cayley graphs which suggest that the diameters are asymptotically (4/3)logk–1(n) and logk–1(n), respectively.

UR - http://www.scopus.com/inward/record.url?scp=85051433617&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85051433617&partnerID=8YFLogxK

U2 - 10.1007/s00493-017-3605-0

DO - 10.1007/s00493-017-3605-0

M3 - Article

AN - SCOPUS:85051433617

SN - 0209-9683

VL - 39

SP - 427

EP - 446

JO - Combinatorica

JF - Combinatorica

IS - 2

ER -

Diameter of Ramanujan Graphs and Random Cayley Graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this