Ramanujan graf
Ramanujan graf , pojmenoval Srinivasa Ramanujan , je pravidelný graf , jehož spektrální mezera je skoro stejně velká jako je to možné. Takové grafy jsou vynikajícími expandéry . Jinými slovy, jedná se o rodinu grafů, kde každý vrchol má stejný (normální) stupeň a kde dvě nejvyšší vlastní čísla mají rozdíl téměř co největší.
Mezi grafy Ramanujan patří kliky , kompletní bipartity a Petersenův graf . Jak poznamenal pan Ram Murty (in) , grafy Ramanujan „zahrnují různá odvětví matematiky, jako je teorie čísel , teorie reprezentací a algebraická geometrie .“
K.ne,ne{\ displaystyle K_ {n, n}}
Definice
Dovolit být connected- pravidelný graf s vrcholů, a nechť jsou vlastní hodnoty z matice přilehlosti části (viz spektrální teorie grafů ). Jak je připojeno a -regular, ověřují se jeho vlastní hodnoty . Kdykoliv existuje taková, že definujeme
G{\ displaystyle G}
d{\ displaystyle d}
ne{\ displaystyle n}
λ0≥λ1≥...≥λne-1{\ displaystyle \ lambda _ {0} \ geq \ lambda _ {1} \ geq \ ldots \ geq \ lambda _ {n-1}}
G{\ displaystyle G}
G{\ displaystyle G}
d{\ displaystyle d}
d=λ0≥λ1≥...≥λne-1≥-d{\ displaystyle d = \ lambda _ {0} \ geq \ lambda _ {1} \ geq \ ldots \ geq \ lambda _ {n-1} \ geq -d}
λi{\ displaystyle \ lambda _ {i}}
|λi|<d{\ displaystyle | \ lambda _ {i} | <d}![{\ displaystyle | \ lambda _ {i} | <d}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8cb5d94fecf92fc1ad7379e6012943e6900e3090)
λ(G)=max|λi|<d|λi|.{\ displaystyle \ lambda (G) = \ max _ {| \ lambda _ {i} | <d} | \ lambda _ {i} |. \,}![{\ displaystyle \ lambda (G) = \ max _ {| \ lambda _ {i} | <d} | \ lambda _ {i} |. \,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/631ec2809db166d85505a52d15ac2504f1f2dac5)
Pravidelný graf je graf Ramanujan, pokud je definován a je platný .
d{\ displaystyle d}
G{\ displaystyle G}
λ(G){\ displaystyle \ lambda (G)}
λ(G)≤2d-1{\ displaystyle \ lambda (G) \ leq 2 {\ sqrt {d-1}}}![{\ displaystyle \ lambda (G) \ leq 2 {\ sqrt {d-1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08f0d56b3985aaa720cf0bce04f50e53474db655)
Extrémnost grafů Ramanujan
Pro a pevné, Ramanujan -regular graf s vrcholy minimalizuje . Pokud je pravidelný graf průměru , věta o Noga Alon dává:
d{\ displaystyle d}
ne{\ displaystyle n}
d{\ displaystyle d}
ne{\ displaystyle n}
λ(G){\ displaystyle \ lambda (G)}
G{\ displaystyle G}
d{\ displaystyle d}
m{\ displaystyle m}![m](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
λ1≥2d-1-2d-1-1m.{\ displaystyle \ lambda _ {1} \ geq 2 {\ sqrt {d-1}} - {\ frac {2 {\ sqrt {d-1}} - 1} {m}}.}![{\ displaystyle \ lambda _ {1} \ geq 2 {\ sqrt {d-1}} - {\ frac {2 {\ sqrt {d-1}} - 1} {m}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9621d9c50f8e368a219c1893983dea28df00b76d)
Když je -pravidelný a spojený na nejméně třech jeho vrcholech, proto . Dovolit být množina všech pravidelných grafů, které mají alespoň vrcholy. Protože minimální průměr těchto grafů má tendenci být nekonečný, aby byl fixován a má sklon k nekonečnu, Nilliova věta zahrnuje Alonovu a Boppanovu teorému, která byla prokázána dříve a která uvádí:
G{\ displaystyle G}
d{\ displaystyle d}
|λ1|<d{\ displaystyle | \ lambda _ {1} | <d}
λ(G)≥λ1{\ displaystyle \ lambda (G) \ geq \ lambda _ {1}}
Gned{\ displaystyle {\ mathcal {G}} _ {n} ^ {d}}
d{\ displaystyle d}
G{\ displaystyle G}
ne{\ displaystyle n}
Gned{\ displaystyle {\ mathcal {G}} _ {n} ^ {d}}
d{\ displaystyle d}
ne{\ displaystyle n}![ne](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
limne→∞infG∈Gnedλ(G)≥2d-1.{\ displaystyle \ lim _ {n \ to \ infty} \ inf _ {G \ in {\ mathcal {G}} _ {n} ^ {d}} \ lambda (G) \ geq 2 {\ sqrt {d- 1}}.}![{\ displaystyle \ lim _ {n \ to \ infty} \ inf _ {G \ in {\ mathcal {G}} _ {n} ^ {d}} \ lambda (G) \ geq 2 {\ sqrt {d- 1}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0fba4c137d64017a7cc2d81315502d64da071bbe)
Konstrukce
Konstrukce grafů Ramanujan se často provádí pomocí běžných grafů Ramanujan pro všechny hlavní a takové, že p ≡ 1 (mod 4). Jejich důkaz používá domněnku Ramanujan , která dala grafům jejich jméno. Morgenstern rozšířil konstrukci na všechny mocnosti lichých prvočísel.
p+1{\ displaystyle p + 1}
p{\ displaystyle p}
Poznámky a odkazy
-
(in) M. Ram Murty , „ Ramanujan Graphs “ , J. Ramanujan Math. Soc. , sv. 18, n o 1,2003, str. 1-20 ( číst online )
-
(in) Nilli Alon , „ Na druhé vlastní hodnotě grafu “ , Diskrétní matematika , sv. 91, n O 21991, str. 207-210 ( číst online )
Podívejte se také
Bibliografie
- (en) Guiliana Davidoff, Elementární teorie čísel, teorie grup a Ramanjuanské grafy , sv. 55, Cambridge University Press , coll. "Studentské texty LMS",2003( ISBN 0-521-53143-8 , OCLC 50253269 )
- (en) Alexander Lubotzky , R. Phillips, Peter Sarnak, „ Ramanujan graphs “ , Combinatorica , roč. 8,1988, str. 261–277 ( DOI 10.1007 / BF02126799 )
- (en) Moshe Morgenstern, „ Existence a explicitní konstrukce q + 1 pravidelných grafů Ramanujan pro každou hlavní moc q “ , J. Combinatorial Theory, Series B , sv. 62,1994, str. 44–62 ( DOI 10.1006 / jctb.1994.1054 )
Související článek
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">