4364:
5938:
containing roughly the larger half of the inputs. To achieve this, sequentially process each matching by comparing the registers paired up by the edges of this matching and correct any inputs that are out of order. Specifically, for each edge of the matching, if the larger input is in the register in
661:
is the minimum number of edges that need to be cut in order to split the graph in two. The edge expansion normalizes this concept by dividing with smallest number of vertices among the two parts. To see how the normalization can drastically change the value, consider the following example. Take two
5760:
Sorting networks take a set of inputs and perform a series of parallel steps to sort the inputs. A parallel step consists of performing any number of disjoint comparisons and potentially swapping pairs of compared inputs. The depth of a network is given by the number of parallel steps it takes.
958:
4928:
The original motivation for expanders is to build economical robust networks (phone or computer): an expander with bounded degree is precisely an asymptotic robust graph with the number of edges growing linearly with size (number of vertices), for all subsets.
1129:
1356:
4180:
5430:
4032:
introduced the zig-zag product in 2003. Roughly speaking, the zig-zag product of two expander graphs produces a graph with only slightly worse expansion. Therefore, a zig-zag product can also be used to construct families of expander graphs. If
5733:
states that, when sampling many independent samples from a random variable in the range , with high probability the average of our samples is close to the expectation of the random variable. The expander walk sampling lemma, due to
2633:
3745:
2945:
264:
2128:
4781:
There are many results that show the existence of graphs with good expansion properties through probabilistic arguments. In fact, the existence of expanders was first proved by
Pinsker who showed that for a randomly chosen
5007:, typical behavior, explicit constructions, and algorithms. Extremal problems focus on the bounding of expansion parameters, while typical behavior problems characterize how the expansion parameters are distributed over
5712:
3980:
5624:
3427:
2433:
5917:
The vertices of the graph can be thought of as registers that contain inputs and the edges can be thought of as wires that compare the inputs of two registers. At the start, arbitrarily place half of the inputs in
2231:
361:
5290:
3017:
3275:
656:
2013:
517:
3213:
2823:
1729:
1612:
817:
777:
3896:
3835:
1782:
3163:
3574:
7192:
4369:
Note that property (1) implies that the zig-zag product of two expander graphs is also an expander graph, thus zig-zag products can be used inductively to create a family of expander graphs.
3490:
3624:
3079:
There are four general strategies for explicitly constructing families of expander graphs. The first strategy is algebraic and group-theoretic, the second strategy is analytic and uses
5633:
of a graph is the maximum distance between two vertices, where the distance between two vertices is defined to be the shortest path between them. Chung showed that the diameter of an
4711:
4647:
1395:
1003:
2273:
1824:
1230:
4359:{\displaystyle \phi (\lambda _{1},\lambda _{2})={\frac {1}{2}}(1-\lambda _{2}^{2})\lambda _{2}+{\frac {1}{2}}{\sqrt {(1-\lambda _{2}^{2})^{2}\lambda _{1}^{2}+4\lambda _{2}^{2}}}.}
5301:
4744:
5011:. Explicit constructions focus on constructing graphs that optimize certain parameters, and algorithmic questions study the evaluation and estimation of parameters.
3110:
are known for various variants of expander graphs. The following construction is due to
Margulis and has been analysed by Gabber and Galil. For every natural number
2743:
2719:
4590:
2534:
3652:
2853:
5772:. While this is asymptotically the best known depth for a sorting network, the reliance on expanders makes the constant bound too large for practical use.
2309:. Its eigenvalues are between −1 and 1. For not necessarily regular graphs, the spectrum of a graph can be defined similarly using the eigenvalues of the
158:
2036:
5649:
3923:
5545:
7678:
3283:
2356:
1784:. The latter is a weaker notion that holds also for bipartite graphs and is still useful for many applications, such as the Alon-Chung lemma.
7571:
7385:
7341:
7305:
7261:
7206:
7182:
2278:
The normalized versions of these definitions are also widely used and more convenient in stating some results. Here one considers the matrix
2139:
271:
5160:
2951:
3218:
7281:
590:
6774:
1943:
7697:
953:{\displaystyle h(G)=\min _{\emptyset \subsetneq S\subsetneq V(G)}{\frac {E({S},{\overline {S}})}{\min\{|S|,|{\overline {S}}|\}}}.}
418:
3168:
5742:, states that this also holds true when sampling from a walk on an expander graph. This is particularly useful in the theory of
2761:
1675:
1558:
7066:
4965:
712:
130:
59:
7651:
6237:
N. Alon and F. R. K. Chung, Explicit construction of linear sized tolerant networks. Discrete Math., vol. 72, pp. 15-19, 1988.
3856:
3795:
1738:
5452:
3124:
105:
is empty. Every connected graph is an expander; however, different connected graphs have different expansion parameters. The
4769:. The original non-constructive proof was turned into an algorithm by Michael B. Cohen. Later the method was generalized to
7687:
7174:
6635:
3518:
6695:
4592:
vertices. The lifted graph inherits the eigenvalues of the original graph, and has some additional eigenvalues. Bilu and
6798:
Bilu, Yonatan; Linial, Nathan (2004-04-08). "Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap".
4649:
in magnitude. They also showed that if the starting graph is a good enough expander, then a good 2-lift can be found in
6717:
6683:
5072:
4751:
3988:
58:
expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to
43:
7198:
3453:
6938:
6149:
5503:, is the minimum number of colors needed such that adjacent vertices have different colors. Hoffman showed that
3590:
1124:{\displaystyle h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}},}
6572:
2302:
102:
4667:
4603:
1364:
1351:{\displaystyle h_{\text{in}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{in}}(S)|}{|S|}},}
6995:
7712:
6899:
5630:
4945:
4762:, who used the method of interlacing polynomials. As a result, they obtained an alternative construction of
4372:
Intuitively, the construction of the zig-zag product can be thought of in the following way. Each vertex of
1858:
83:
2243:
1794:
7549:
7455:
7363:
6943:
6357:
6139:
5724:
4949:
3583:
is the second largest eigenvalue in absolute value. As a direct consequence, we know that for every fixed
3080:
3767:(1988), Margulis (1988), and Morgenstern (1994) show how Ramanujan graphs can be constructed explicitly.
6154:
5746:, since sampling according to an expander walk uses many fewer random bits than sampling independently.
5425:{\displaystyle \left|E(S,T)-{\frac {d\cdot |S|\cdot |T|}{n}}\right|\leq \lambda {\sqrt {|S|\cdot |T|}}.}
5020:
5004:
1903:
1662:
110:
67:
55:
47:
7542:
Studies in
Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation
5000:
2847:
Similar connections between vertex isoperimetric numbers and the spectral gap have also been studied:
7007:
6591:
6536:
4380:
vertices, each associated to a different edge connected to the vertex. Each vertex is now labeled as
3846:
7554:
7460:
6948:
6484:
Friedman, Joel (2004-05-05). "A proof of Alon's second eigenvalue conjecture and related problems".
6362:
6014:. Furthermore, this property remains true throughout the rest of the process. Now, suppose for some
4716:
7675:
7485:
7368:
7053:
2841:
51:
7692:
7632:
7602:
7585:
7507:
7488:(1984), "Difference equations, isoperimetric inequality and transience of certain random walks",
7473:
7427:
7391:
7347:
7311:
7104:
7031:
6964:
6908:
6869:
6846:
6799:
6780:
6662:
6644:
6615:
6581:
6552:
6526:
6485:
6466:
6375:
4747:
3760:
3508:
7285:
2438:
Consequently, for constant degree graphs, vertex and edge expansion are qualitatively the same.
7567:
7381:
7337:
7301:
7257:
7202:
7178:
7126:
7085:
7023:
6838:
6770:
6725:
6691:
6607:
6458:
4759:
3996:
2027:
670:
edges between the two graphs by connecting their vertices one-to-one. The minimum cut will be
6633:
Friedman, Joel; Puder, Doron (2023). "A note on the trace method for random regular graphs".
6348:
Alon, Noga (1986). "Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory".
113:. Informally, a graph is a good expander if it has low degree and high expansion parameters.
7624:
7594:
7559:
7540:
7528:
7497:
7465:
7419:
7403:
7373:
7327:
7293:
7239:
7224:
7116:
7075:
7015:
6976:
6918:
6879:
6830:
6819:
Bilu, Yonatan; Linial, Nathan (2006). "Lifts, discrepancy and nearly optimal spectral gap".
6762:
6755:"Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors"
6654:
6599:
6544:
6450:
6367:
5154:. If the two sets are not disjoint, edges in their intersection are counted twice, that is,
4961:
4933:
3103:
2837:
2310:
1496:
1492:
1451:
63:
2483:. By standard spectral graph theory, the trivial eigenvalue of the adjacency operator of a
7682:
7615:
6721:
6687:
6144:
5755:
5743:
4969:
4953:
4791:
4766:
4763:
4755:
4650:
4016:
4000:
3992:
3639:
3502:
3092:
3084:
2728:
2704:
2639:
2628:{\displaystyle {\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}
2318:
1524:. It is known that all these eigenvalues are in and more specifically, it is known that
7277:
6294:
B. Mohar. Isoperimetric numbers of graphs. J. Combin. Theory Ser. B, 47(3):274–291, 1989.
2342:
The expansion parameters defined above are related to each other. In particular, for any
86:. Different formalisations of these notions give rise to different notions of expanders:
7440:
7011:
6729:
6595:
6540:
5761:
Expander graphs play an important role in the AKS sorting network, which achieves depth
5003:, Hoory, Linial, and Wigderson split the study of expander graphs into four categories:
7019:
5730:
5488:
4973:
4575:
4562:
3841:
In 2003, Joel
Friedman both proved the conjecture and specified what is meant by "most
2314:
1443:
106:
7121:
6897:
Hall, Chris; Puder, Doron; Sawin, William F. (2018). "Ramanujan coverings of graphs".
3740:{\displaystyle \lambda =\max _{|\lambda _{i}|<d}|\lambda _{i}|\leq 2{\sqrt {d-1}}.}
2940:{\displaystyle h_{\text{out}}(G)\leq \left({\sqrt {4(d-\lambda _{2})}}+1\right)^{2}-1}
7706:
7606:
7580:
7322:
Ajtai, M.; Komlós, J.; Szemerédi, E. (1987), "Deterministic simulation in LOGSPACE",
7220:
7057:
6821:
6666:
6556:
4993:
4941:
4029:
4021:
2833:
2829:
2525:
1436:
7636:
7477:
7360:
The 43rd Annual IEEE Symposium on
Foundations of Computer Science, 2002. Proceedings
7351:
7315:
7035:
6850:
6619:
6470:
5775:
Within the AKS sorting network, expander graphs are used to construct bounded depth
259:{\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial S|}{|S|}},}
7548:, Lecture Notes in Computer Science (Vol. 6650), vol. 6650, pp. 451–464,
7431:
7395:
7157:
6379:
5008:
4989:
4025:
3764:
3107:
1912:
39:
31:
7244:
6784:
6517:
Puder, Doron (2015-08-21). "Expansion of random graphs: New proofs, new results".
7670:
7563:
2123:{\displaystyle \lambda =\max _{v\perp u,v\neq 0}{\frac {\|Av\|_{2}}{\|v\|_{2}}},}
7216:
5447:-graphs are corollaries of the expander mixing lemmas, including the following.
4981:
4593:
2638:
In fact, the lower bound is tight. The lower bound is achieved in limit for the
1880:
17:
7532:
7377:
6922:
6834:
6754:
6658:
6603:
6548:
6048:. Then by expansion properties of the graph, the registers of these inputs in
2019:
1447:
79:
7130:
7089:
7027:
6842:
6766:
6611:
6462:
82:
in which every subset of the vertices that is not "too large" has a "large"
7628:
7598:
7519:
Gillman, D. (1998), "A Chernoff Bound for Random Walks on
Expander Graphs",
7469:
7153:
7049:
6570:
Puder, Doron (2015). "Expansion of random graphs: new proofs, new results".
5707:{\displaystyle \left\lceil \log {\frac {n}{\log(d/\lambda )}}\right\rceil .}
4937:
4600:-regular graph has a 2-lift in which the additional eigenvalues are at most
3975:{\displaystyle \tau =\left\lceil {\frac {{\sqrt {d-1}}+1}{2}}\right\rceil .}
3088:
2521:
7688:
Lecture notes from a course on expanders (by Nati Linial and Avi
Wigderson)
7080:
7061:
6980:
6868:. Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium.
6118:
is. This violates the previous property however, and thus the output sets
5619:{\displaystyle \chi (G)\leq O\left({\frac {d}{\log(1+d/\lambda )}}\right).}
7423:
7297:
6737:. Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium.
6703:. Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium.
2325:, which are equal to the roots of the eigenvalues of the symmetric matrix
6883:
5295:
Then the expander mixing lemma says that the following inequality holds:
3750:
Hence
Ramanujan graphs have an asymptotically smallest possible value of
7332:
5455:
of a graph is a subset of vertices with no two vertices adjacent. In an
4572:
vertices, and each edge by a matching between the corresponding sets of
3422:{\displaystyle (x\pm 2y,y),(x\pm (2y+1),y),(x,y\pm 2x),(x,y\pm (2x+1)).}
2428:{\displaystyle h_{\text{out}}(G)\leq h(G)\leq d\cdot h_{\text{out}}(G).}
7511:
6454:
6371:
3087:
and related graph products, and the fourth strategy is based on lifts.
811:
with an optimization over all non-empty subsets, we can rewrite it as
6804:
2237:
2226:{\displaystyle \|v\|_{2}=\left(\sum _{i=1}^{n}v_{i}^{2}\right)^{1/2}}
356:{\displaystyle \partial S:=\{\{u,v\}\in E(G)\ :\ u\in S,v\notin S\},}
7502:
7358:
Alon, N.; Capalbo, M. (2002), "Explicit unique-neighbor expanders",
6759:
Proceedings 41st Annual
Symposium on Foundations of Computer Science
7324:
Proceedings of the 19th Annual ACM Symposium on Theory of
Computing
7290:
Proceedings of the 15th Annual ACM Symposium on Theory of Computing
6913:
6874:
6649:
6490:
5285:{\displaystyle E(S,T)=2|E(G)|+E(S\setminus T,T)+E(S,T\setminus S).}
7671:
Brief introduction in Notices of the American Mathematical Society
6586:
6531:
6006:
then after the matching with this edge is processed, the input in
4964:. They have also been used in proofs of many important results in
2670:. The upper bound is (asymptotically) achieved for a cycle, where
2018:
as this is the largest eigenvalue corresponding to an eigenvector
6697:
Interlacing families I: Bipartite Ramanujan graphs of all degrees
5887:
of equal size such that every subset of vertices of size at most
3012:{\displaystyle h_{\text{in}}(G)\leq {\sqrt {8(d-\lambda _{2})}}.}
101:
A disconnected graph is not an expander, since the boundary of a
7173:, CBMS Regional Conference Series in Mathematics, vol. 92,
6731:
Interlacing families IV: Bipartite Ramanujan graphs of all sizes
3985:
A simpler proof of a slightly weaker result was given by Puder.
3270:{\displaystyle (x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}}
651:{\displaystyle \min {|\partial S|}=\min E({S},{\overline {S}})}
2008:{\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}}
7693:
Lecture notes from a course on expanders (by Prahladh Harsha)
7613:
Yehudayoff, Amir (2012), "Proving expansion in three steps",
7539:
Goldreich, Oded (2011), "Basic Facts about Expander Graphs",
4914:
getting to infinity, the resulting graph is almost surely an
2458:, there is a relationship between the isoperimetric constant
109:
has the best expansion property, but it has largest possible
3646:-regular graphs for which this bound is tight, satisfying
512:{\displaystyle E(A,B)=\{\{u,v\}\in E(G)\ :\ u\in A,v\in B\}}
7194:
Elementary number theory, group theory and Ramanujan graphs
6936:
Pinkser, M. (1973). "On the Complexity of a Concentrator".
6246:
This definition of the spectral gap is from Section 2.3 in
3208:{\displaystyle \mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z} }
7191:
Davidoff, Guiliana; Sarnak, Peter; Valette, Alain (2003),
2818:{\displaystyle h(G)\leq {\sqrt {d^{2}-\lambda _{2}^{2}}}.}
1724:{\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }
1607:{\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }
5947:, then swap the two inputs so that the smaller one is in
4750:. This conjecture was proved in the bipartite setting by
772:{\displaystyle E(S,{\overline {S}})=E({\overline {S}},S)}
5063:-regular graph. The approximation is better the smaller
3891:{\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }
3830:{\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }
1777:{\displaystyle \max _{i\neq 1}\lambda _{i}\leq \lambda }
688:, the optimization can be equivalently done either over
7254:
Expander families and Cayley graphs: A beginner's guide
3158:{\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{n}}
544:
In the equation, the minimum is over all nonempty sets
78:
Intuitively, an expander graph is a finite, undirected
6441:
Alon, Noga (1986-06-01). "Eigenvalues and expanders".
5934:
roughly containing the smaller half of the inputs and
5522:, while Alon, Krivelevich, and Sudakov showed that if
3095:
are the sparsest examples of highly expanding graphs.
2539:
1930:, and it measures the spectral expansion of the graph
577:, i.e., the set of edges with exactly one endpoint in
5652:
5548:
5304:
5163:
4932:
Expander graphs have found extensive applications in
4719:
4670:
4606:
4578:
4183:
3926:
3859:
3798:
3655:
3593:
3521:
3456:
3286:
3221:
3171:
3127:
2954:
2856:
2764:
2731:
2707:
2537:
2359:
2246:
2142:
2039:
1946:
1797:
1741:
1678:
1561:
1367:
1233:
1006:
820:
715:
593:
421:
274:
161:
7652:"Universal Method to Sort Complex Information Found"
6505:
6429:
6417:
6405:
6283:
6247:
6226:
6189:
6177:
5861:
5735:
4957:
3569:{\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-o(1)}
2338:
Relationships between different expansion properties
5059:is approximately what you would expect in a random
3083:, the third strategy is combinatorial and uses the
6304:
6203:
5706:
5618:
5424:
5284:
4738:
4705:
4641:
4584:
4358:
3974:
3890:
3829:
3739:
3618:
3568:
3484:
3421:
3269:
3207:
3157:
3011:
2939:
2817:
2737:
2713:
2627:
2427:
2267:
2225:
2122:
2007:
1818:
1776:
1723:
1606:
1389:
1350:
1123:
952:
771:
650:
511:
355:
258:
5986:-halving. To see this, notice that if a register
4568:of a graph is formed by replacing each vertex by
2520:. An inequality due to Dodziuk and independently
1446:definition of expansion is possible based on the
662:complete graphs with the same number of vertices
7583:(2008), "Undirected connectivity in log-space",
6753:Reingold, O.; Vadhan, S.; Wigderson, A. (2000).
3757:. This makes them excellent spectral expanders.
3663:
2047:
1953:
1743:
1680:
1563:
1257:
1030:
899:
837:
618:
594:
178:
5871:-halver can be constructed as follows. Take an
6199:
6197:
2828:These inequalities are closely related to the
7232:Bulletin of the American Mathematical Society
5795:and halves the inputs into two disjoint sets
5025:The expander mixing lemma states that for an
2479:in the spectrum of the adjacency operator of
8:
7109:Journal of the American Mathematical Society
6996:"On Eigenvalues and Colorings of Graphs, Ii"
6173:
6171:
6169:
5955:. It is clear that this process consists of
5943:and the smaller input is in the register in
5467:-graph, an independent set has size at most
5037:-graph, for any two subsets of the vertices
4436:are connected if it is possible to get from
3485:{\displaystyle \lambda (G)\leq 5{\sqrt {2}}}
3091:showed that certain graphs constructed from
2150:
2143:
2105:
2098:
2087:
2077:
2002:
1956:
941:
902:
506:
458:
446:
443:
347:
299:
287:
284:
7062:"Coloring Graphs with Sparse Neighborhoods"
6270:
6214:
5930:perfect matchings. The goal is to end with
5750:AKS sorting network and approximate halvers
4877:such that the following holds: For a group
4858:. Alon and Roichman showed that for every
4664:Bilu and Linial conjectured that the bound
4653:, thus giving an efficient construction of
2454:-regular, meaning each vertex is of degree
2026:, it can be equivalently defined using the
7698:Definition and application of spectral gap
7410:, vertex isoperimetry and concentration",
7160:(2011). "9.2. Eigenvalues and Expanders".
7000:Annals of the New York Academy of Sciences
6336:
3619:{\displaystyle \lambda <2{\sqrt {d-1}}}
3056:are all bounded above by the spectral gap
1172:. In a variant of this definition (called
522:the edges between the subsets of vertices
7553:
7501:
7459:
7367:
7331:
7288:(1983), "An O(n log n) sorting network",
7243:
7120:
7079:
6947:
6912:
6873:
6803:
6648:
6585:
6530:
6489:
6393:
6361:
6086:registers so there must be some register
6082:. Altogether, this constitutes more than
5682:
5664:
5651:
5595:
5571:
5547:
5412:
5404:
5396:
5388:
5386:
5364:
5356:
5348:
5340:
5331:
5303:
5220:
5188:
5162:
4723:
4718:
4686:
4677:
4669:
4622:
4613:
4605:
4577:
4460:through the following sequence of moves.
4345:
4340:
4324:
4319:
4309:
4299:
4294:
4279:
4269:
4260:
4247:
4242:
4219:
4207:
4194:
4182:
3940:
3937:
3925:
3869:
3858:
3808:
3797:
3721:
3710:
3704:
3695:
3682:
3676:
3667:
3666:
3654:
3603:
3592:
3538:
3526:
3520:
3475:
3455:
3285:
3261:
3257:
3256:
3246:
3242:
3241:
3220:
3201:
3200:
3192:
3188:
3187:
3178:
3174:
3173:
3170:
3149:
3145:
3144:
3134:
3130:
3129:
3126:
2995:
2977:
2959:
2953:
2925:
2903:
2885:
2861:
2855:
2836:and can be seen as a discrete version of
2804:
2799:
2786:
2780:
2763:
2730:
2706:
2611:
2590:
2563:
2538:
2536:
2407:
2364:
2358:
2259:
2255:
2254:
2245:
2213:
2209:
2198:
2193:
2183:
2172:
2153:
2141:
2108:
2090:
2074:
2050:
2038:
1997:
1991:
1982:
1974:
1968:
1959:
1945:
1810:
1806:
1805:
1796:
1762:
1746:
1740:
1710:
1704:
1695:
1683:
1677:
1593:
1587:
1578:
1566:
1560:
1372:
1366:
1337:
1329:
1322:
1307:
1298:
1295:
1283:
1275:
1267:
1260:
1238:
1232:
1110:
1102:
1095:
1080:
1071:
1068:
1056:
1048:
1040:
1033:
1011:
1005:
936:
926:
921:
913:
905:
884:
876:
867:
840:
819:
750:
728:
714:
635:
627:
609:
598:
597:
592:
420:
273:
245:
237:
230:
219:
216:
204:
196:
188:
181:
160:
7225:"Expander graphs and their applications"
6712:
6710:
6678:
6676:
5978:to be the set of inputs in registers in
5970:to be the set of inputs in registers in
4992:, expander graphs are used to construct
4977:
4706:{\displaystyle O({\sqrt {d\log ^{3}d}})}
4642:{\displaystyle O({\sqrt {d\log ^{3}d}})}
3022:Asymptotically speaking, the quantities
2498:and the first non-trivial eigenvalue is
1479:is the number of edges between vertices
1390:{\displaystyle \partial _{\text{in}}(S)}
6994:Hoffman, A. J.; Howes, Leonard (1970).
6326:of the current article (see p.153, l.5)
6258:
6165:
5739:
5270:
5237:
1661:is useful many contexts, including the
7441:"The PCP theorem by gap amplification"
7252:Krebs, Mike; Shaheen, Anthony (2011),
7164:(3rd ed.). John Wiley & Sons.
1188:is replaced by the set of vertices in
7676:Introductory paper by Michael Nielsen
6748:
6746:
6744:
4985:
3782:, are almost Ramanujan. That is, for
3770:In 1985, Alon, conjectured that most
2268:{\displaystyle v\in \mathbb {R} ^{n}}
1819:{\displaystyle u\in \mathbb {R} ^{n}}
1791:is regular, the uniform distribution
709:or over any non-empty subset, since
27:Sparse graph with strong connectivity
7:
6975:(2). Wiley Online Library: 271–284.
6965:"Random Cayley graphs and Expanders"
6506:Hoory, Linial & Wigderson (2006)
6430:Hoory, Linial & Wigderson (2006)
6418:Hoory, Linial & Wigderson (2006)
6406:Hoory, Linial & Wigderson (2006)
6284:Hoory, Linial & Wigderson (2006)
6248:Hoory, Linial & Wigderson (2006)
6227:Hoory, Linial & Wigderson (2006)
6190:Hoory, Linial & Wigderson (2006)
6178:Hoory, Linial & Wigderson (2006)
5862:Ajtai, Komlós & Szemerédi (1983)
5736:Ajtai, Komlós & Szemerédi (1987)
4958:Ajtai, Komlós & Szemerédi (1983)
4746:, which would be optimal due to the
7197:, LMS student texts, vol. 55,
6866:Ramanujan Graphs in Polynomial Time
6761:. IEEE Comput. Soc. pp. 3–13.
5146:denote the number of edges between
7020:10.1111/j.1749-6632.1970.tb56474.x
6305:Bobkov, Houdré & Tetali (2000)
6204:Bobkov, Houdré & Tetali (2000)
4924:Applications and useful properties
3277:, its eight adjacent vertices are
2755:. A better bound is given in as
1369:
1304:
1077:
841:
674:but the edge expansion will be 1.
603:
275:
224:
25:
7122:10.1090/S0894-0347-1989-0965008-X
5071:-regular graph, as well as in an
4773:-lifts by Hall, Puder and Sawin.
4073:-graph, then the zig-zag product
3845:-regular graphs" by showing that
3778:vertices, for sufficiently large
6969:Random Structures and Algorithms
6303:See Theorem 1 and p.156, l.1 in
5783:-halver takes as input a length
4396:refers to an original vertex of
790:because of the normalization by
7067:Journal of Combinatorial Theory
6963:Alon, N.; Roichman, Y. (1994).
4966:computational complexity theory
4885:, consider the Cayley graph on
3626:, there are only finitely many
1405:, i.e., the set of vertices in
1154:, i.e., the set of vertices in
5879:bipartite expander with parts
5690:
5676:
5603:
5583:
5558:
5552:
5413:
5405:
5397:
5389:
5365:
5357:
5349:
5341:
5325:
5313:
5276:
5258:
5249:
5231:
5221:
5217:
5214:
5202:
5196:
5189:
5179:
5167:
5051:, the number of edges between
5001:2006 survey of expander graphs
4906:randomly chosen elements from
4739:{\displaystyle 2{\sqrt {d-1}}}
4700:
4674:
4636:
4610:
4498:Jump across clouds using edge
4306:
4281:
4253:
4229:
4213:
4187:
4111:has the following properties.
3711:
3696:
3683:
3668:
3563:
3557:
3466:
3460:
3450:has second-largest eigenvalue
3413:
3410:
3395:
3380:
3374:
3353:
3347:
3338:
3323:
3314:
3308:
3287:
3234:
3222:
3001:
2982:
2971:
2965:
2909:
2890:
2873:
2867:
2774:
2768:
2617:
2598:
2584:
2578:
2569:
2550:
2419:
2413:
2391:
2385:
2376:
2370:
1998:
1983:
1975:
1960:
1711:
1696:
1594:
1579:
1544:More formally, we refer to an
1409:with at least one neighbor in
1384:
1378:
1338:
1330:
1323:
1319:
1313:
1299:
1276:
1268:
1250:
1244:
1168:with at least one neighbor in
1111:
1103:
1096:
1092:
1086:
1072:
1049:
1041:
1023:
1017:
937:
922:
914:
906:
894:
873:
862:
856:
830:
824:
766:
747:
738:
719:
645:
624:
610:
599:
473:
467:
437:
425:
314:
308:
246:
238:
231:
220:
197:
189:
171:
165:
1:
7245:10.1090/S0273-0979-06-01126-8
7175:American Mathematical Society
6636:Israel Journal of Mathematics
6102:such that the final input of
5926:and decompose the edges into
4836:with high probability, where
4657:-regular expanders for every
366:which can also be written as
46:properties, quantified using
7564:10.1007/978-3-642-22670-0_30
6052:are connected with at least
4819:for all subsets of vertices
4376:is blown up to a "cloud" of
931:
889:
755:
733:
640:
7256:, Oxford University Press,
7105:"Diameters and eigenvalues"
6114:, while the final input of
6094:connected to some register
5803:such that for each integer
4843:is a constant depending on
3509:theorem of Alon and Boppana
1205:vertex isoperimetric number
970:vertex isoperimetric number
779:. The same is not true for
7729:
7658:(published 13 August 2018)
7199:Cambridge University Press
5922:and half of the inputs in
5753:
5722:
5018:
4014:
4004:
4003:Ramanujan graphs based on
3500:
3432:Then the following holds:
3114:, one considers the graph
1668:Spectral expansion can be
7533:10.1137/S0097539794268765
7521:SIAM Journal on Computing
7378:10.1109/SFCS.2002.1181884
7326:, ACM, pp. 132–140,
7169:Chung, Fan R. K. (1997),
6939:SIAM Journal on Computing
6923:10.1016/j.aim.2017.10.042
6864:Michael B. Cohen (2016).
6835:10.1007/s00493-006-0029-7
6659:10.1007/s11856-023-2497-5
6604:10.1007/s00222-014-0560-x
6549:10.1007/s00222-014-0560-x
6215:Alon & Capalbo (2002)
6150:Superstrong approximation
6002:are connected by an edge
5951:and the larger one is in
3999:, gave a construction of
3511:, all sufficiently large
1174:unique neighbor expansion
7650:Hartnett, Kevin (2018),
7402:Bobkov, S.; Houdré, C.;
7162:The Probabilistic Method
7103:Chung, F. R. K. (1989).
6767:10.1109/sfcs.2000.892006
6573:Inventiones Mathematicae
6519:Inventiones Mathematicae
5073:Erdős–Rényi random graph
4910:. Then, in the limit of
4777:Randomized constructions
3515:-regular graphs satisfy
2321:of the adjacency matrix
2303:Markov transition matrix
1633:. The bound given by an
1507:real-valued eigenvalues
7629:10.1145/2421096.2421115
7599:10.1145/1391289.1391291
7490:Trans. Amer. Math. Soc.
7470:10.1145/1236457.1236459
6900:Advances in Mathematics
6271:Alon & Spencer 2011
5829:smallest inputs are in
4950:pseudorandom generators
3106:constructions based on
1859:stationary distribution
152:vertices is defined as
7081:10.1006/jctb.1999.1910
6981:10.1002/rsa.3240050203
6140:Algebraic connectivity
5841:largest inputs are in
5725:Expander walk sampling
5719:Expander walk sampling
5708:
5620:
5426:
5286:
5075:with edge probability
4942:error correcting codes
4740:
4707:
4643:
4586:
4360:
3976:
3892:
3831:
3741:
3620:
3570:
3494:
3486:
3423:
3271:
3209:
3159:
3081:additive combinatorics
3013:
2941:
2819:
2739:
2715:
2629:
2429:
2269:
2227:
2188:
2124:
2009:
1820:
1778:
1725:
1608:
1391:
1352:
1125:
954:
800:. If we want to write
773:
652:
513:
357:
260:
68:error-correcting codes
7424:10.1007/s004930070018
7298:10.1145/800061.808726
7171:Spectral Graph Theory
7147:Textbooks and surveys
6314:there corresponds to
6155:Spectral graph theory
6010:is less than that of
5709:
5621:
5427:
5287:
5021:Expander mixing lemma
5015:Expander mixing lemma
4741:
4708:
4644:
4587:
4361:
3977:
3893:
3832:
3742:
3621:
3571:
3487:
3434:
3424:
3272:
3210:
3160:
3099:Margulis–Gabber–Galil
3014:
2942:
2820:
2740:
2716:
2630:
2430:
2270:
2228:
2168:
2125:
2010:
1821:
1779:
1726:
1663:expander mixing lemma
1609:
1552:-regular graph with
1392:
1353:
1126:
955:
774:
653:
514:
358:
261:
7439:Dinur, Irit (2007),
7054:Krivelevich, Michael
6884:10.1109/FOCS.2016.37
5650:
5546:
5302:
5161:
4717:
4668:
4604:
4576:
4181:
3924:
3857:
3796:
3653:
3591:
3519:
3454:
3284:
3219:
3169:
3125:
3121:with the vertex set
2952:
2854:
2838:Cheeger's inequality
2762:
2738:{\displaystyle \pi }
2729:
2714:{\displaystyle \pi }
2705:
2535:
2442:Cheeger inequalities
2357:
2317:, one considers the
2244:
2140:
2037:
1944:
1795:
1739:
1676:
1559:
1365:
1231:
1004:
818:
713:
591:
419:
272:
159:
127:isoperimetric number
98:, as defined below.
66:, and the theory of
7644:Recent Applications
7333:10.1145/28395.28410
7012:1970NYASA.175..238H
6596:2015InMat.201..845P
6541:2015InMat.201..845P
6416:Definition 5.11 of
6225:cf. Section 2.3 in
5435:Many properties of
5131:More formally, let
4713:can be improved to
4491:, using an edge of
4350:
4329:
4304:
4252:
3774:-regular graphs on
3215:: For every vertex
2842:Riemannian geometry
2809:
2509:is connected, then
2203:
1906:of the vertices of
1865:. That is, we have
103:connected component
62:, design of robust
7681:2016-08-17 at the
7586:Journal of the ACM
7448:Journal of the ACM
6455:10.1007/BF02579166
6392:see, e.g., p.9 of
6372:10.1007/BF02579382
6188:Definition 2.1 in
5704:
5616:
5422:
5282:
4748:Alon-Boppana bound
4736:
4703:
4639:
4596:showed that every
4582:
4356:
4336:
4315:
4290:
4238:
3972:
3888:
3827:
3737:
3694:
3616:
3566:
3482:
3419:
3267:
3205:
3155:
3009:
2937:
2815:
2795:
2735:
2711:
2625:
2548:
2487:-regular graph is
2425:
2265:
2223:
2189:
2120:
2073:
2005:
1816:
1774:
1757:
1721:
1694:
1604:
1577:
1427:Spectral expansion
1387:
1348:
1294:
1121:
1067:
950:
866:
769:
648:
509:
408:the complement of
353:
256:
215:
96:spectral expanders
7573:978-3-642-22669-4
7387:978-0-7695-1822-0
7343:978-0-89791-221-1
7307:978-0-89791-099-6
7271:Research articles
7263:978-0-19-976711-3
7208:978-0-521-53143-6
7184:978-0-8218-0315-8
6726:Nikhil Srivastava
6692:Nikhil Srivastava
6337:Yehudayoff (2012)
5694:
5645:-graph is at most
5607:
5417:
5373:
5005:extremal problems
4962:computer networks
4734:
4698:
4634:
4585:{\displaystyle r}
4548:using an edge of
4351:
4277:
4227:
3963:
3951:
3905:with probability
3880:
3819:
3732:
3662:
3614:
3549:
3480:
3093:finite geometries
3004:
2962:
2912:
2864:
2810:
2620:
2547:
2410:
2367:
2115:
2046:
2028:Rayleigh quotient
1920:is defined to be
1742:
1679:
1672:, as above, with
1562:
1375:
1343:
1310:
1291:
1256:
1241:
1116:
1083:
1064:
1029:
1014:
945:
934:
892:
836:
758:
736:
643:
484:
478:
325:
319:
251:
212:
177:
64:computer networks
60:complexity theory
16:(Redirected from
7720:
7659:
7639:
7609:
7576:
7557:
7547:
7535:
7527:(4): 1203–1220,
7514:
7505:
7480:
7463:
7445:
7434:
7398:
7371:
7354:
7335:
7318:
7292:, pp. 1–9,
7266:
7248:
7247:
7229:
7211:
7187:
7165:
7158:Spencer, Joel H.
7135:
7134:
7124:
7100:
7094:
7093:
7083:
7046:
7040:
7039:
6991:
6985:
6984:
6960:
6954:
6953:
6951:
6933:
6927:
6926:
6916:
6894:
6888:
6887:
6877:
6861:
6855:
6854:
6816:
6810:
6809:
6807:
6795:
6789:
6788:
6750:
6739:
6738:
6736:
6714:
6705:
6704:
6702:
6680:
6671:
6670:
6652:
6630:
6624:
6623:
6589:
6567:
6561:
6560:
6534:
6514:
6508:
6504:Theorem 7.10 of
6502:
6496:
6495:
6493:
6481:
6475:
6474:
6438:
6432:
6428:Theorem 5.12 of
6426:
6420:
6414:
6408:
6402:
6396:
6394:Goldreich (2011)
6390:
6384:
6383:
6365:
6345:
6339:
6333:
6327:
6325:
6313:
6301:
6295:
6292:
6286:
6280:
6274:
6268:
6262:
6256:
6250:
6244:
6238:
6235:
6229:
6223:
6217:
6212:
6206:
6201:
6192:
6186:
6180:
6175:
6129:
6125:
6121:
6117:
6113:
6105:
6101:
6097:
6093:
6089:
6085:
6081:
6077:
6073:
6071:
6070:
6065:
6062:
6051:
6047:
6043:
6035:
6031:
6030:
6029:
6025:
6013:
6009:
6005:
6001:
5997:
5993:
5989:
5985:
5981:
5977:
5973:
5969:
5965:
5959:parallel steps.
5958:
5954:
5950:
5946:
5942:
5937:
5933:
5929:
5925:
5921:
5913:
5912:
5910:
5909:
5904:
5901:
5890:
5886:
5882:
5878:
5874:
5870:
5867:
5856:
5852:
5848:
5844:
5840:
5836:
5832:
5828:
5824:
5820:
5819:
5818:
5814:
5802:
5798:
5794:
5786:
5782:
5778:
5771:
5713:
5711:
5710:
5705:
5700:
5696:
5695:
5693:
5686:
5665:
5644:
5625:
5623:
5622:
5617:
5612:
5608:
5606:
5599:
5572:
5540:
5539:
5538:
5534:
5521:
5515:
5514:
5510:
5502:
5494:
5489:chromatic number
5483:
5482:
5481:
5475:
5466:
5446:
5431:
5429:
5428:
5423:
5418:
5416:
5408:
5400:
5392:
5387:
5379:
5375:
5374:
5369:
5368:
5360:
5352:
5344:
5332:
5291:
5289:
5288:
5283:
5224:
5192:
5153:
5149:
5145:
5127:
5123:
5119:
5117:
5111:
5105:
5104:
5098:
5090:
5089:
5088:
5082:
5070:
5067:is. In a random
5066:
5062:
5058:
5054:
5050:
5036:
4954:sorting networks
4934:computer science
4919:
4913:
4909:
4905:
4888:
4884:
4880:
4876:
4866:, there is some
4865:
4857:
4846:
4842:
4835:
4826:
4818:
4816:
4806:
4789:
4785:
4772:
4767:Ramanujan graphs
4745:
4743:
4742:
4737:
4735:
4724:
4712:
4710:
4709:
4704:
4699:
4691:
4690:
4678:
4660:
4656:
4648:
4646:
4645:
4640:
4635:
4627:
4626:
4614:
4599:
4591:
4589:
4588:
4583:
4571:
4565:
4551:
4547:
4535:
4517:
4505:
4501:
4494:
4490:
4478:
4459:
4447:
4435:
4423:
4412:. Two vertices,
4411:
4407:
4403:
4399:
4395:
4391:
4379:
4375:
4365:
4363:
4362:
4357:
4352:
4349:
4344:
4328:
4323:
4314:
4313:
4303:
4298:
4280:
4278:
4270:
4265:
4264:
4251:
4246:
4228:
4220:
4212:
4211:
4199:
4198:
4169:
4145:
4130:
4122:
4110:
4106:
4082:
4072:
4056:
4052:
4036:
3981:
3979:
3978:
3973:
3968:
3964:
3959:
3952:
3941:
3938:
3916:
3904:
3897:
3895:
3894:
3889:
3881:
3870:
3850:
3844:
3836:
3834:
3833:
3828:
3820:
3809:
3788:
3781:
3777:
3773:
3763:, Phillips, and
3756:
3746:
3744:
3743:
3738:
3733:
3722:
3714:
3709:
3708:
3699:
3693:
3686:
3681:
3680:
3671:
3645:
3640:Ramanujan graphs
3637:
3625:
3623:
3622:
3617:
3615:
3604:
3586:
3582:
3575:
3573:
3572:
3567:
3550:
3539:
3531:
3530:
3514:
3497:Ramanujan graphs
3491:
3489:
3488:
3483:
3481:
3476:
3449:
3442:
3428:
3426:
3425:
3420:
3276:
3274:
3273:
3268:
3266:
3265:
3260:
3251:
3250:
3245:
3214:
3212:
3211:
3206:
3204:
3196:
3191:
3183:
3182:
3177:
3164:
3162:
3161:
3156:
3154:
3153:
3148:
3139:
3138:
3133:
3120:
3113:
3070:
3055:
3046:
3037:
3036:
3035:
3029:
3018:
3016:
3015:
3010:
3005:
3000:
2999:
2978:
2964:
2963:
2960:
2946:
2944:
2943:
2938:
2930:
2929:
2924:
2920:
2913:
2908:
2907:
2886:
2866:
2865:
2862:
2824:
2822:
2821:
2816:
2811:
2808:
2803:
2791:
2790:
2781:
2754:
2744:
2742:
2741:
2736:
2720:
2718:
2717:
2712:
2691:
2669:
2658:
2647:
2634:
2632:
2631:
2626:
2621:
2616:
2615:
2591:
2568:
2567:
2549:
2540:
2519:
2508:
2504:
2497:
2486:
2482:
2478:
2468:
2457:
2453:
2449:
2434:
2432:
2431:
2426:
2412:
2411:
2408:
2369:
2368:
2365:
2349:
2345:
2333:
2324:
2311:Laplacian matrix
2308:
2300:
2296:
2294:
2293:
2288:
2285:
2274:
2272:
2271:
2266:
2264:
2263:
2258:
2232:
2230:
2229:
2224:
2222:
2221:
2217:
2208:
2204:
2202:
2197:
2187:
2182:
2158:
2157:
2129:
2127:
2126:
2121:
2116:
2114:
2113:
2112:
2096:
2095:
2094:
2075:
2072:
2025:
2014:
2012:
2011:
2006:
2001:
1996:
1995:
1986:
1978:
1973:
1972:
1963:
1933:
1929:
1919:
1909:
1901:
1897:
1887:with eigenvalue
1886:
1878:
1874:
1864:
1856:
1846:
1845:
1844:
1838:
1825:
1823:
1822:
1817:
1815:
1814:
1809:
1790:
1783:
1781:
1780:
1775:
1767:
1766:
1756:
1730:
1728:
1727:
1722:
1714:
1709:
1708:
1699:
1693:
1660:
1653:
1644:
1628:
1613:
1611:
1610:
1605:
1597:
1592:
1591:
1582:
1576:
1551:
1547:
1540:
1536:
1523:
1506:
1502:
1497:spectral theorem
1490:
1486:
1482:
1478:
1471:
1467:
1452:adjacency matrix
1444:linear algebraic
1439:
1434:
1422:
1408:
1404:
1396:
1394:
1393:
1388:
1377:
1376:
1373:
1357:
1355:
1354:
1349:
1344:
1342:
1341:
1333:
1327:
1326:
1312:
1311:
1308:
1302:
1296:
1293:
1292:
1284:
1279:
1271:
1243:
1242:
1239:
1223:
1219:
1199:
1196:one neighbor in
1191:
1187:
1171:
1167:
1153:
1145:
1130:
1128:
1127:
1122:
1117:
1115:
1114:
1106:
1100:
1099:
1085:
1084:
1081:
1075:
1069:
1066:
1065:
1057:
1052:
1044:
1016:
1015:
1012:
996:
987:vertex expansion
984:
964:Vertex expansion
959:
957:
956:
951:
946:
944:
940:
935:
927:
925:
917:
909:
897:
893:
885:
880:
868:
865:
810:
799:
797:
789:
778:
776:
775:
770:
759:
751:
737:
729:
708:
707:
706:
702:
695:
687:
685:
673:
669:
665:
657:
655:
654:
649:
644:
636:
631:
614:
613:
602:
580:
576:
568:
561:
560:
559:
555:
547:
540:
518:
516:
515:
510:
482:
476:
411:
407:
394:
387:
385:
362:
360:
359:
354:
323:
317:
265:
263:
262:
257:
252:
250:
249:
241:
235:
234:
223:
217:
214:
213:
205:
200:
192:
151:
147:
143:
131:Cheeger constant
92:vertex expanders
42:that has strong
21:
7728:
7727:
7723:
7722:
7721:
7719:
7718:
7717:
7703:
7702:
7683:Wayback Machine
7667:
7662:
7656:Quanta Magazine
7649:
7646:
7616:ACM SIGACT News
7612:
7579:
7574:
7555:10.1.1.231.1388
7545:
7538:
7518:
7503:10.2307/1999107
7484:
7461:10.1.1.103.2644
7443:
7438:
7409:
7401:
7388:
7357:
7344:
7321:
7308:
7276:
7273:
7264:
7251:
7227:
7215:Hoory, Shlomo;
7214:
7209:
7190:
7185:
7168:
7152:
7149:
7143:
7138:
7102:
7101:
7097:
7048:
7047:
7043:
6993:
6992:
6988:
6962:
6961:
6957:
6949:10.1.1.393.1430
6935:
6934:
6930:
6896:
6895:
6891:
6863:
6862:
6858:
6818:
6817:
6813:
6797:
6796:
6792:
6777:
6752:
6751:
6742:
6734:
6722:Daniel Spielman
6716:
6715:
6708:
6700:
6688:Daniel Spielman
6682:
6681:
6674:
6632:
6631:
6627:
6569:
6568:
6564:
6516:
6515:
6511:
6503:
6499:
6483:
6482:
6478:
6440:
6439:
6435:
6427:
6423:
6415:
6411:
6404:Theorem 2.7 of
6403:
6399:
6391:
6387:
6363:10.1.1.300.5945
6347:
6346:
6342:
6334:
6330:
6323:
6315:
6312:
6308:
6302:
6298:
6293:
6289:
6282:Theorem 2.4 in
6281:
6277:
6269:
6265:
6257:
6253:
6245:
6241:
6236:
6232:
6224:
6220:
6213:
6209:
6202:
6195:
6187:
6183:
6176:
6167:
6163:
6145:Zig-zag product
6136:
6127:
6123:
6119:
6115:
6107:
6103:
6099:
6095:
6091:
6087:
6083:
6079:
6066:
6063:
6057:
6056:
6054:
6053:
6049:
6045:
6037:
6033:
6032:that more than
6027:
6021:
6020:
6015:
6011:
6007:
6003:
5999:
5995:
5991:
5987:
5983:
5979:
5975:
5971:
5967:
5963:
5956:
5952:
5948:
5944:
5940:
5935:
5931:
5927:
5923:
5919:
5905:
5902:
5896:
5895:
5893:
5892:
5888:
5884:
5880:
5876:
5875:vertex, degree
5872:
5868:
5865:
5854:
5850:
5846:
5842:
5838:
5834:
5830:
5826:
5822:
5816:
5810:
5809:
5804:
5800:
5796:
5788:
5787:permutation of
5784:
5780:
5776:
5762:
5758:
5756:Sorting network
5752:
5744:derandomization
5727:
5721:
5669:
5657:
5653:
5648:
5647:
5634:
5576:
5567:
5544:
5543:
5536:
5529:
5528:
5523:
5512:
5506:
5505:
5504:
5496:
5492:
5477:
5470:
5469:
5468:
5456:
5453:independent set
5436:
5333:
5309:
5305:
5300:
5299:
5159:
5158:
5151:
5147:
5132:
5125:
5121:
5113:
5112:| • |
5107:
5100:
5094:
5093:
5092:
5084:
5078:
5077:
5076:
5068:
5064:
5060:
5056:
5052:
5038:
5026:
5023:
5017:
4978:Reingold (2008)
4936:, in designing
4926:
4915:
4911:
4907:
4901:
4890:
4886:
4882:
4878:
4867:
4859:
4848:
4844:
4841:
4837:
4832:
4822:
4820:
4812:
4797:
4795:
4792:bipartite graph
4787:
4783:
4779:
4770:
4715:
4714:
4682:
4666:
4665:
4658:
4654:
4651:polynomial time
4618:
4602:
4601:
4597:
4574:
4573:
4569:
4563:
4559:
4549:
4537:
4525:
4507:
4503:
4499:
4492:
4480:
4468:
4449:
4437:
4425:
4413:
4409:
4405:
4401:
4397:
4393:
4381:
4377:
4373:
4305:
4256:
4203:
4190:
4179:
4178:
4168:
4164:
4160:
4156:
4149:
4143:
4139:
4132:
4128:
4124:
4120:
4116:
4108:
4104:
4100:
4084:
4074:
4070:
4058:
4054:
4050:
4038:
4034:
4019:
4017:Zig-zag product
4013:
4011:Zig-Zag product
3939:
3933:
3922:
3921:
3906:
3899:
3855:
3854:
3851:-regular graphs
3848:
3842:
3794:
3793:
3789:, they satisfy
3783:
3779:
3775:
3771:
3755:
3751:
3700:
3672:
3651:
3650:
3643:
3627:
3589:
3588:
3584:
3581:
3577:
3522:
3517:
3516:
3512:
3505:
3503:Ramanujan graph
3499:
3452:
3451:
3448:
3444:
3440:
3282:
3281:
3255:
3240:
3217:
3216:
3172:
3167:
3166:
3143:
3128:
3123:
3122:
3119:
3115:
3111:
3101:
3077:
3068:
3057:
3054:
3048:
3045:
3039:
3031:
3025:
3024:
3023:
2991:
2955:
2950:
2949:
2899:
2884:
2880:
2879:
2857:
2852:
2851:
2782:
2760:
2759:
2727:
2726:
2703:
2702:
2700:
2693:
2680:
2671:
2667:
2660:
2649:
2646:
2642:
2607:
2559:
2533:
2532:
2514:
2510:
2506:
2503:
2499:
2492:
2488:
2484:
2480:
2477:
2470:
2459:
2455:
2451:
2447:
2444:
2403:
2360:
2355:
2354:
2347:
2346:-regular graph
2343:
2340:
2326:
2322:
2319:singular values
2315:directed graphs
2306:
2301:, which is the
2289:
2286:
2283:
2282:
2280:
2279:
2253:
2242:
2241:
2167:
2163:
2162:
2149:
2138:
2137:
2104:
2097:
2086:
2076:
2035:
2034:
2023:
1987:
1964:
1942:
1941:
1931:
1928:
1921:
1917:
1907:
1899:
1892:
1888:
1884:
1876:
1866:
1862:
1848:
1840:
1836:
1835:
1832:
1827:
1804:
1793:
1792:
1788:
1758:
1737:
1736:
1731:, or it can be
1700:
1674:
1673:
1655:
1652:
1646:
1634:
1618:
1583:
1557:
1556:
1549:
1545:
1538:
1537:if and only if
1531:
1525:
1522:
1516:
1512:
1508:
1504:
1500:
1488:
1484:
1480:
1477:
1473:
1469:
1454:
1437:
1432:
1429:
1410:
1406:
1402:
1368:
1363:
1362:
1328:
1303:
1297:
1234:
1229:
1228:
1221:
1213:
1207:
1197:
1189:
1181:
1177:
1169:
1155:
1151:
1139:
1135:
1101:
1076:
1070:
1007:
1002:
1001:
994:
978:
972:
966:
898:
869:
816:
815:
801:
793:
791:
780:
711:
710:
704:
698:
697:
691:
689:
680:
678:
677:Notice that in
671:
667:
663:
589:
588:
578:
574:
563:
557:
551:
550:
549:
545:
523:
417:
416:
409:
390:
389:
381:
367:
270:
269:
236:
218:
157:
156:
149:
145:
134:
119:
76:
28:
23:
22:
18:Expander graphs
15:
12:
11:
5:
7726:
7724:
7716:
7715:
7713:Graph families
7705:
7704:
7701:
7700:
7695:
7690:
7685:
7673:
7666:
7665:External links
7663:
7661:
7660:
7645:
7642:
7641:
7640:
7610:
7581:Reingold, Omer
7577:
7572:
7536:
7516:
7496:(2): 787–794,
7486:Dodziuk, Jozef
7482:
7436:
7418:(2): 153–172,
7407:
7399:
7386:
7369:10.1.1.103.967
7362:, p. 73,
7355:
7342:
7319:
7306:
7272:
7269:
7268:
7267:
7262:
7249:
7238:(4): 439–561,
7234:, New Series,
7221:Wigderson, Avi
7217:Linial, Nathan
7212:
7207:
7188:
7183:
7166:
7148:
7145:
7144:
7142:
7139:
7137:
7136:
7115:(2): 187–196.
7095:
7060:(1999-09-01).
7058:Sudakov, Benny
7041:
7006:(1): 238–242.
6986:
6955:
6928:
6889:
6856:
6829:(5): 495–519.
6811:
6790:
6775:
6740:
6706:
6672:
6625:
6580:(3): 845–908.
6562:
6525:(3): 845–908.
6509:
6497:
6476:
6433:
6421:
6409:
6397:
6385:
6356:(3): 207–219.
6340:
6328:
6321:
6310:
6296:
6287:
6275:
6263:
6251:
6239:
6230:
6218:
6207:
6193:
6181:
6164:
6162:
6159:
6158:
6157:
6152:
6147:
6142:
6135:
6132:
6036:of the inputs
5754:Main article:
5751:
5748:
5740:Gillman (1998)
5731:Chernoff bound
5723:Main article:
5720:
5717:
5716:
5715:
5703:
5699:
5692:
5689:
5685:
5681:
5678:
5675:
5672:
5668:
5663:
5660:
5656:
5627:
5615:
5611:
5605:
5602:
5598:
5594:
5591:
5588:
5585:
5582:
5579:
5575:
5570:
5566:
5563:
5560:
5557:
5554:
5551:
5485:
5433:
5432:
5421:
5415:
5411:
5407:
5403:
5399:
5395:
5391:
5385:
5382:
5378:
5372:
5367:
5363:
5359:
5355:
5351:
5347:
5343:
5339:
5336:
5330:
5327:
5324:
5321:
5318:
5315:
5312:
5308:
5293:
5292:
5281:
5278:
5275:
5272:
5269:
5266:
5263:
5260:
5257:
5254:
5251:
5248:
5245:
5242:
5239:
5236:
5233:
5230:
5227:
5223:
5219:
5216:
5213:
5210:
5207:
5204:
5201:
5198:
5195:
5191:
5187:
5184:
5181:
5178:
5175:
5172:
5169:
5166:
5120:edges between
5019:Main article:
5016:
5013:
4994:hash functions
4925:
4922:
4899:
4839:
4830:
4778:
4775:
4733:
4730:
4727:
4722:
4702:
4697:
4694:
4689:
4685:
4681:
4676:
4673:
4638:
4633:
4630:
4625:
4621:
4617:
4612:
4609:
4581:
4558:
4555:
4554:
4553:
4519:
4496:
4404:refers to the
4367:
4366:
4355:
4348:
4343:
4339:
4335:
4332:
4327:
4322:
4318:
4312:
4308:
4302:
4297:
4293:
4289:
4286:
4283:
4276:
4273:
4268:
4263:
4259:
4255:
4250:
4245:
4241:
4237:
4234:
4231:
4226:
4223:
4218:
4215:
4210:
4206:
4202:
4197:
4193:
4189:
4186:
4174:Specifically,
4172:
4171:
4166:
4162:
4158:
4154:
4147:
4141:
4137:
4126:
4118:
4102:
4098:
4068:
4048:
4015:Main article:
4012:
4009:
3983:
3982:
3971:
3967:
3962:
3958:
3955:
3950:
3947:
3944:
3936:
3932:
3929:
3887:
3884:
3879:
3876:
3873:
3868:
3865:
3862:
3839:
3838:
3826:
3823:
3818:
3815:
3812:
3807:
3804:
3801:
3753:
3748:
3747:
3736:
3731:
3728:
3725:
3720:
3717:
3713:
3707:
3703:
3698:
3692:
3689:
3685:
3679:
3675:
3670:
3665:
3661:
3658:
3613:
3610:
3607:
3602:
3599:
3596:
3579:
3565:
3562:
3559:
3556:
3553:
3548:
3545:
3542:
3537:
3534:
3529:
3525:
3501:Main article:
3498:
3495:
3479:
3474:
3471:
3468:
3465:
3462:
3459:
3446:
3430:
3429:
3418:
3415:
3412:
3409:
3406:
3403:
3400:
3397:
3394:
3391:
3388:
3385:
3382:
3379:
3376:
3373:
3370:
3367:
3364:
3361:
3358:
3355:
3352:
3349:
3346:
3343:
3340:
3337:
3334:
3331:
3328:
3325:
3322:
3319:
3316:
3313:
3310:
3307:
3304:
3301:
3298:
3295:
3292:
3289:
3264:
3259:
3254:
3249:
3244:
3239:
3236:
3233:
3230:
3227:
3224:
3203:
3199:
3195:
3190:
3186:
3181:
3176:
3152:
3147:
3142:
3137:
3132:
3117:
3100:
3097:
3076:
3073:
3066:
3052:
3043:
3020:
3019:
3008:
3003:
2998:
2994:
2990:
2987:
2984:
2981:
2976:
2973:
2970:
2967:
2958:
2947:
2936:
2933:
2928:
2923:
2919:
2916:
2911:
2906:
2902:
2898:
2895:
2892:
2889:
2883:
2878:
2875:
2872:
2869:
2860:
2826:
2825:
2814:
2807:
2802:
2798:
2794:
2789:
2785:
2779:
2776:
2773:
2770:
2767:
2734:
2710:
2698:
2678:
2665:
2644:
2636:
2635:
2624:
2619:
2614:
2610:
2606:
2603:
2600:
2597:
2594:
2589:
2586:
2583:
2580:
2577:
2574:
2571:
2566:
2562:
2558:
2555:
2552:
2546:
2543:
2512:
2501:
2490:
2475:
2443:
2440:
2436:
2435:
2424:
2421:
2418:
2415:
2406:
2402:
2399:
2396:
2393:
2390:
2387:
2384:
2381:
2378:
2375:
2372:
2363:
2339:
2336:
2262:
2257:
2252:
2249:
2240:of the vector
2234:
2233:
2220:
2216:
2212:
2207:
2201:
2196:
2192:
2186:
2181:
2178:
2175:
2171:
2166:
2161:
2156:
2152:
2148:
2145:
2131:
2130:
2119:
2111:
2107:
2103:
2100:
2093:
2089:
2085:
2082:
2079:
2071:
2068:
2065:
2062:
2059:
2056:
2053:
2049:
2045:
2042:
2016:
2015:
2004:
2000:
1994:
1990:
1985:
1981:
1977:
1971:
1967:
1962:
1958:
1955:
1952:
1949:
1926:
1890:
1830:
1813:
1808:
1803:
1800:
1773:
1770:
1765:
1761:
1755:
1752:
1749:
1745:
1720:
1717:
1713:
1707:
1703:
1698:
1692:
1689:
1686:
1682:
1648:
1615:
1614:
1603:
1600:
1596:
1590:
1586:
1581:
1575:
1572:
1569:
1565:
1541:is bipartite.
1527:
1518:
1514:
1510:
1475:
1428:
1425:
1399:inner boundary
1386:
1383:
1380:
1371:
1359:
1358:
1347:
1340:
1336:
1332:
1325:
1321:
1318:
1315:
1306:
1301:
1290:
1287:
1282:
1278:
1274:
1270:
1266:
1263:
1259:
1255:
1252:
1249:
1246:
1237:
1224:is defined as
1211:
1179:
1148:outer boundary
1137:
1132:
1131:
1120:
1113:
1109:
1105:
1098:
1094:
1091:
1088:
1079:
1074:
1063:
1060:
1055:
1051:
1047:
1043:
1039:
1036:
1032:
1028:
1025:
1022:
1019:
1010:
997:is defined as
976:
965:
962:
961:
960:
949:
943:
939:
933:
930:
924:
920:
916:
912:
908:
904:
901:
896:
891:
888:
883:
879:
875:
872:
864:
861:
858:
855:
852:
849:
846:
843:
839:
835:
832:
829:
826:
823:
768:
765:
762:
757:
754:
749:
746:
743:
740:
735:
732:
727:
724:
721:
718:
659:
658:
647:
642:
639:
634:
630:
626:
623:
620:
617:
612:
608:
605:
601:
596:
584:Intuitively,
520:
519:
508:
505:
502:
499:
496:
493:
490:
487:
481:
475:
472:
469:
466:
463:
460:
457:
454:
451:
448:
445:
442:
439:
436:
433:
430:
427:
424:
364:
363:
352:
349:
346:
343:
340:
337:
334:
331:
328:
322:
316:
313:
310:
307:
304:
301:
298:
295:
292:
289:
286:
283:
280:
277:
266:
255:
248:
244:
240:
233:
229:
226:
222:
211:
208:
203:
199:
195:
191:
187:
184:
180:
176:
173:
170:
167:
164:
123:edge expansion
118:
117:Edge expansion
115:
107:complete graph
88:edge expanders
75:
72:
36:expander graph
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
7725:
7714:
7711:
7710:
7708:
7699:
7696:
7694:
7691:
7689:
7686:
7684:
7680:
7677:
7674:
7672:
7669:
7668:
7664:
7657:
7653:
7648:
7647:
7643:
7638:
7634:
7630:
7626:
7622:
7618:
7617:
7611:
7608:
7604:
7600:
7596:
7592:
7588:
7587:
7582:
7578:
7575:
7569:
7565:
7561:
7556:
7551:
7544:
7543:
7537:
7534:
7530:
7526:
7522:
7517:
7513:
7509:
7504:
7499:
7495:
7491:
7487:
7483:
7479:
7475:
7471:
7467:
7462:
7457:
7453:
7449:
7442:
7437:
7433:
7429:
7425:
7421:
7417:
7413:
7412:Combinatorica
7405:
7400:
7397:
7393:
7389:
7383:
7379:
7375:
7370:
7365:
7361:
7356:
7353:
7349:
7345:
7339:
7334:
7329:
7325:
7320:
7317:
7313:
7309:
7303:
7299:
7295:
7291:
7287:
7286:Szemerédi, E.
7283:
7279:
7275:
7274:
7270:
7265:
7259:
7255:
7250:
7246:
7241:
7237:
7233:
7226:
7222:
7218:
7213:
7210:
7204:
7200:
7196:
7195:
7189:
7186:
7180:
7176:
7172:
7167:
7163:
7159:
7155:
7151:
7150:
7146:
7140:
7132:
7128:
7123:
7118:
7114:
7110:
7106:
7099:
7096:
7091:
7087:
7082:
7077:
7073:
7069:
7068:
7063:
7059:
7055:
7051:
7045:
7042:
7037:
7033:
7029:
7025:
7021:
7017:
7013:
7009:
7005:
7001:
6997:
6990:
6987:
6982:
6978:
6974:
6970:
6966:
6959:
6956:
6950:
6945:
6941:
6940:
6932:
6929:
6924:
6920:
6915:
6910:
6906:
6902:
6901:
6893:
6890:
6885:
6881:
6876:
6871:
6867:
6860:
6857:
6852:
6848:
6844:
6840:
6836:
6832:
6828:
6824:
6823:
6822:Combinatorica
6815:
6812:
6806:
6801:
6794:
6791:
6786:
6782:
6778:
6776:0-7695-0850-2
6772:
6768:
6764:
6760:
6756:
6749:
6747:
6745:
6741:
6733:
6732:
6727:
6723:
6719:
6713:
6711:
6707:
6699:
6698:
6693:
6689:
6685:
6679:
6677:
6673:
6668:
6664:
6660:
6656:
6651:
6646:
6642:
6638:
6637:
6629:
6626:
6621:
6617:
6613:
6609:
6605:
6601:
6597:
6593:
6588:
6583:
6579:
6575:
6574:
6566:
6563:
6558:
6554:
6550:
6546:
6542:
6538:
6533:
6528:
6524:
6520:
6513:
6510:
6507:
6501:
6498:
6492:
6487:
6480:
6477:
6472:
6468:
6464:
6460:
6456:
6452:
6448:
6444:
6443:Combinatorica
6437:
6434:
6431:
6425:
6422:
6419:
6413:
6410:
6407:
6401:
6398:
6395:
6389:
6386:
6381:
6377:
6373:
6369:
6364:
6359:
6355:
6351:
6350:Combinatorica
6344:
6341:
6338:
6332:
6329:
6319:
6306:
6300:
6297:
6291:
6288:
6285:
6279:
6276:
6272:
6267:
6264:
6260:
6255:
6252:
6249:
6243:
6240:
6234:
6231:
6228:
6222:
6219:
6216:
6211:
6208:
6205:
6200:
6198:
6194:
6191:
6185:
6182:
6179:
6174:
6172:
6170:
6166:
6160:
6156:
6153:
6151:
6148:
6146:
6143:
6141:
6138:
6137:
6133:
6131:
6111:
6078:registers in
6076:
6069:
6061:
6041:
6024:
6018:
5982:to obtain an
5966:rounds, take
5960:
5915:
5908:
5900:
5891:has at least
5863:
5858:
5813:
5807:
5792:
5779:-halvers. An
5773:
5769:
5765:
5757:
5749:
5747:
5745:
5741:
5737:
5732:
5726:
5718:
5714:
5701:
5697:
5687:
5683:
5679:
5673:
5670:
5666:
5661:
5658:
5654:
5642:
5638:
5632:
5628:
5626:
5613:
5609:
5600:
5596:
5592:
5589:
5586:
5580:
5577:
5573:
5568:
5564:
5561:
5555:
5549:
5533:
5526:
5519:
5509:
5500:
5490:
5486:
5480:
5474:
5464:
5460:
5454:
5450:
5449:
5448:
5444:
5440:
5419:
5409:
5401:
5393:
5383:
5380:
5376:
5370:
5361:
5353:
5345:
5337:
5334:
5328:
5322:
5319:
5316:
5310:
5306:
5298:
5297:
5296:
5279:
5273:
5267:
5264:
5261:
5255:
5252:
5246:
5243:
5240:
5234:
5228:
5225:
5211:
5208:
5205:
5199:
5193:
5185:
5182:
5176:
5173:
5170:
5164:
5157:
5156:
5155:
5143:
5139:
5135:
5129:
5116:
5110:
5103:
5097:
5087:
5081:
5074:
5049:
5045:
5041:
5034:
5030:
5022:
5014:
5012:
5010:
5009:random graphs
5006:
5002:
4997:
4995:
4991:
4987:
4983:
4979:
4975:
4972: =
4971:
4967:
4963:
4960:) and robust
4959:
4955:
4951:
4947:
4943:
4939:
4935:
4930:
4923:
4921:
4918:
4904:
4897:
4893:
4874:
4870:
4863:
4855:
4851:
4834:
4825:
4815:
4810:
4804:
4800:
4793:
4776:
4774:
4768:
4765:
4761:
4757:
4753:
4749:
4731:
4728:
4725:
4720:
4695:
4692:
4687:
4683:
4679:
4671:
4662:
4652:
4631:
4628:
4623:
4619:
4615:
4607:
4595:
4579:
4567:
4556:
4545:
4541:
4533:
4529:
4523:
4520:
4515:
4511:
4497:
4488:
4484:
4476:
4472:
4466:
4463:
4462:
4461:
4457:
4453:
4445:
4441:
4433:
4429:
4421:
4417:
4389:
4385:
4370:
4353:
4346:
4341:
4337:
4333:
4330:
4325:
4320:
4316:
4310:
4300:
4295:
4291:
4287:
4284:
4274:
4271:
4266:
4261:
4257:
4248:
4243:
4239:
4235:
4232:
4224:
4221:
4216:
4208:
4204:
4200:
4195:
4191:
4184:
4177:
4176:
4175:
4152:
4148:
4135:
4114:
4113:
4112:
4107:-graph where
4096:
4092:
4088:
4081:
4077:
4066:
4062:
4046:
4042:
4031:
4027:
4023:
4018:
4010:
4008:
4006:
4002:
3998:
3994:
3990:
3986:
3969:
3965:
3960:
3956:
3953:
3948:
3945:
3942:
3934:
3930:
3927:
3920:
3919:
3918:
3914:
3910:
3902:
3885:
3882:
3877:
3874:
3871:
3866:
3863:
3860:
3852:
3824:
3821:
3816:
3813:
3810:
3805:
3802:
3799:
3792:
3791:
3790:
3786:
3768:
3766:
3762:
3758:
3734:
3729:
3726:
3723:
3718:
3715:
3705:
3701:
3690:
3687:
3677:
3673:
3659:
3656:
3649:
3648:
3647:
3641:
3635:
3631:
3611:
3608:
3605:
3600:
3597:
3594:
3560:
3554:
3551:
3546:
3543:
3540:
3535:
3532:
3527:
3523:
3510:
3504:
3496:
3493:
3477:
3472:
3469:
3463:
3457:
3438:
3433:
3416:
3407:
3404:
3401:
3398:
3392:
3389:
3386:
3383:
3377:
3371:
3368:
3365:
3362:
3359:
3356:
3350:
3344:
3341:
3335:
3332:
3329:
3326:
3320:
3317:
3311:
3305:
3302:
3299:
3296:
3293:
3290:
3280:
3279:
3278:
3262:
3252:
3247:
3237:
3231:
3228:
3225:
3197:
3193:
3184:
3179:
3150:
3140:
3135:
3109:
3108:Cayley graphs
3105:
3098:
3096:
3094:
3090:
3086:
3082:
3075:Constructions
3074:
3072:
3064:
3060:
3051:
3042:
3034:
3028:
3006:
2996:
2992:
2988:
2985:
2979:
2974:
2968:
2956:
2948:
2934:
2931:
2926:
2921:
2917:
2914:
2904:
2900:
2896:
2893:
2887:
2881:
2876:
2870:
2858:
2850:
2849:
2848:
2845:
2843:
2839:
2835:
2834:Markov chains
2831:
2830:Cheeger bound
2812:
2805:
2800:
2796:
2792:
2787:
2783:
2777:
2771:
2765:
2758:
2757:
2756:
2752:
2748:
2732:
2724:
2708:
2696:
2689:
2685:
2681:
2674:
2663:
2656:
2652:
2641:
2622:
2612:
2608:
2604:
2601:
2595:
2592:
2587:
2581:
2575:
2572:
2564:
2560:
2556:
2553:
2544:
2541:
2531:
2530:
2529:
2527:
2523:
2518:
2496:
2473:
2466:
2462:
2441:
2439:
2422:
2416:
2404:
2400:
2397:
2394:
2388:
2382:
2379:
2373:
2361:
2353:
2352:
2351:
2337:
2335:
2332:
2329:
2320:
2316:
2312:
2305:of the graph
2304:
2299:
2292:
2276:
2260:
2250:
2247:
2239:
2218:
2214:
2210:
2205:
2199:
2194:
2190:
2184:
2179:
2176:
2173:
2169:
2164:
2159:
2154:
2146:
2136:
2135:
2134:
2117:
2109:
2101:
2091:
2083:
2080:
2069:
2066:
2063:
2060:
2057:
2054:
2051:
2043:
2040:
2033:
2032:
2031:
2029:
2021:
1992:
1988:
1979:
1969:
1965:
1950:
1947:
1940:
1939:
1938:
1935:
1924:
1915:
1914:
1905:
1896:
1882:
1873:
1869:
1860:
1855:
1851:
1843:
1833:
1811:
1801:
1798:
1785:
1771:
1768:
1763:
1759:
1753:
1750:
1747:
1734:
1718:
1715:
1705:
1701:
1690:
1687:
1684:
1671:
1666:
1664:
1658:
1651:
1642:
1638:
1632:
1626:
1622:
1601:
1598:
1588:
1584:
1573:
1570:
1567:
1555:
1554:
1553:
1542:
1535:
1530:
1521:
1499:implies that
1498:
1494:
1465:
1461:
1457:
1453:
1449:
1445:
1441:
1426:
1424:
1421:
1417:
1413:
1400:
1381:
1345:
1334:
1316:
1288:
1285:
1280:
1272:
1264:
1261:
1253:
1247:
1235:
1227:
1226:
1225:
1217:
1210:
1206:
1201:
1195:
1185:
1175:
1166:
1162:
1158:
1149:
1143:
1118:
1107:
1089:
1061:
1058:
1053:
1045:
1037:
1034:
1026:
1020:
1008:
1000:
999:
998:
993:) of a graph
992:
991:magnification
988:
982:
975:
971:
963:
947:
928:
918:
910:
886:
881:
877:
870:
859:
853:
850:
847:
844:
833:
827:
821:
814:
813:
812:
808:
804:
796:
787:
783:
763:
760:
752:
744:
741:
730:
725:
722:
716:
701:
694:
684:
675:
637:
632:
628:
621:
615:
606:
587:
586:
585:
582:
572:
571:edge boundary
567:
562:vertices and
554:
542:
538:
534:
530:
526:
503:
500:
497:
494:
491:
488:
485:
479:
470:
464:
461:
455:
452:
449:
440:
434:
431:
428:
422:
415:
414:
413:
406:
402:
398:
393:
384:
379:
375:
371:
350:
344:
341:
338:
335:
332:
329:
326:
320:
311:
305:
302:
296:
293:
290:
281:
278:
267:
253:
242:
227:
209:
206:
201:
193:
185:
182:
174:
168:
162:
155:
154:
153:
141:
137:
132:
128:
124:
116:
114:
112:
108:
104:
99:
97:
93:
89:
85:
81:
73:
71:
69:
65:
61:
57:
53:
49:
45:
41:
37:
33:
19:
7655:
7623:(3): 67–84,
7620:
7614:
7590:
7584:
7541:
7524:
7520:
7493:
7489:
7454:(3): 12–es,
7451:
7447:
7415:
7411:
7359:
7323:
7289:
7253:
7235:
7231:
7193:
7170:
7161:
7112:
7108:
7098:
7074:(1): 73–82.
7071:
7070:. Series B.
7065:
7044:
7003:
6999:
6989:
6972:
6968:
6958:
6937:
6931:
6904:
6898:
6892:
6865:
6859:
6826:
6820:
6814:
6805:math/0312022
6793:
6758:
6730:
6696:
6640:
6634:
6628:
6577:
6571:
6565:
6522:
6518:
6512:
6500:
6479:
6449:(2): 83–96.
6446:
6442:
6436:
6424:
6412:
6400:
6388:
6353:
6349:
6343:
6331:
6317:
6307:. Note that
6299:
6290:
6278:
6266:
6259:Dodziuk 1984
6254:
6242:
6233:
6221:
6210:
6184:
6109:
6074:
6067:
6059:
6039:
6022:
6016:
5961:
5916:
5906:
5898:
5859:
5833:and at most
5811:
5805:
5790:
5774:
5767:
5763:
5759:
5728:
5646:
5640:
5636:
5542:
5531:
5524:
5517:
5507:
5498:
5478:
5472:
5462:
5458:
5442:
5438:
5434:
5294:
5141:
5137:
5133:
5130:
5114:
5108:
5101:
5095:
5091:, we expect
5085:
5079:
5047:
5043:
5039:
5032:
5028:
5024:
4998:
4990:cryptography
4986:Dinur (2007)
4931:
4927:
4916:
4902:
4895:
4891:
4872:
4868:
4861:
4853:
4849:
4828:
4823:
4813:
4808:
4802:
4798:
4786:vertex left
4780:
4663:
4560:
4543:
4539:
4531:
4527:
4524:- Move from
4521:
4513:
4509:
4486:
4482:
4474:
4470:
4467:- Move from
4464:
4455:
4451:
4443:
4439:
4431:
4427:
4419:
4415:
4387:
4383:
4371:
4368:
4173:
4150:
4133:
4094:
4090:
4086:
4079:
4075:
4064:
4060:
4044:
4040:
4020:
3987:
3984:
3912:
3908:
3900:
3840:
3784:
3769:
3759:
3749:
3633:
3629:
3506:
3443:, the graph
3436:
3435:
3431:
3102:
3078:
3062:
3058:
3049:
3040:
3032:
3026:
3021:
2846:
2827:
2750:
2746:
2722:
2701:= 2 – 2cos(2
2694:
2687:
2683:
2676:
2672:
2661:
2654:
2650:
2637:
2528:states that
2516:
2494:
2471:
2469:and the gap
2464:
2460:
2445:
2437:
2341:
2330:
2327:
2297:
2290:
2277:
2235:
2132:
2017:
1936:
1922:
1913:spectral gap
1911:
1894:
1871:
1867:
1853:
1849:
1841:
1828:
1786:
1732:
1669:
1667:
1656:
1649:
1640:
1636:
1630:
1624:
1620:
1616:
1543:
1533:
1528:
1519:
1463:
1459:
1455:
1430:
1419:
1415:
1411:
1398:
1360:
1215:
1208:
1204:
1202:
1193:
1183:
1173:
1164:
1160:
1156:
1147:
1141:
1133:
990:
986:
980:
973:
969:
967:
806:
802:
794:
785:
781:
699:
692:
682:
676:
660:
583:
570:
565:
552:
543:
536:
532:
528:
524:
521:
404:
400:
396:
391:
382:
377:
373:
369:
365:
139:
135:
126:
122:
120:
100:
95:
91:
87:
77:
44:connectivity
40:sparse graph
35:
32:graph theory
29:
7593:(4): 1–24,
6907:: 367–410.
6718:Adam Marcus
6684:Adam Marcus
6643:: 269–282.
6335:see, e.g.,
6126:must be an
5914:neighbors.
5845:. The sets
5491:of a graph
4982:PCP theorem
4920:-expander.
4408:th edge of
4053:-graph and
1881:eigenvector
1448:eigenvalues
1220:of a graph
548:of at most
144:of a graph
74:Definitions
7406:(2000), "λ
7404:Tetali, P.
7282:Komlós, J.
7141:References
7050:Alon, Noga
6914:1506.02335
6875:1604.03544
6650:2006.13605
6491:cs/0405020
6130:-halving.
6106:is not in
5962:After all
5864:, a depth
5860:Following
5857:-halving.
4980:) and the
4968:, such as
4946:extractors
4938:algorithms
4811:– 2)|
4807:| ≥ (
4760:Srivastava
4506:to get to
3997:Srivastava
3898:for every
2020:orthogonal
1937:If we set
1645:-graph on
1487:. Because
690:0 ≤ |
679:min |
80:multigraph
7607:207168478
7550:CiteSeerX
7456:CiteSeerX
7364:CiteSeerX
7278:Ajtai, M.
7131:0894-0347
7090:0095-8956
7028:1749-6632
6944:CiteSeerX
6843:0209-9683
6667:220042379
6612:0020-9910
6587:1212.5216
6557:253743928
6532:1212.5216
6463:1439-6912
6358:CiteSeerX
5688:λ
5674:
5662:
5601:λ
5581:
5562:≤
5550:χ
5402:⋅
5384:λ
5381:≤
5354:⋅
5338:⋅
5329:−
5271:∖
5238:∖
5209:∩
4881:of order
4827:| ≤
4764:bipartite
4729:−
4693:
4629:
4338:λ
4317:λ
4292:λ
4288:−
4258:λ
4240:λ
4236:−
4205:λ
4192:λ
4185:ϕ
4030:Wigderson
4001:bipartite
3946:−
3928:τ
3886:ε
3875:−
3864:≤
3861:λ
3825:ε
3814:−
3803:≤
3800:λ
3727:−
3716:≤
3702:λ
3674:λ
3657:λ
3638:-graphs.
3609:−
3595:λ
3552:−
3544:−
3533:≥
3524:λ
3470:≤
3458:λ
3393:±
3366:±
3321:±
3294:±
3253:×
3238:∈
3141:×
3104:Algebraic
3089:Noga Alon
2993:λ
2989:−
2975:≤
2932:−
2901:λ
2897:−
2877:≤
2797:λ
2793:−
2778:≤
2733:π
2709:π
2640:hypercube
2609:λ
2605:−
2588:≤
2573:≤
2561:λ
2557:−
2401:⋅
2395:≤
2380:≤
2251:∈
2170:∑
2151:‖
2144:‖
2106:‖
2099:‖
2088:‖
2078:‖
2067:≠
2055:⊥
2041:λ
1989:λ
1966:λ
1948:λ
1802:∈
1772:λ
1769:≤
1760:λ
1751:≠
1733:one-sided
1719:λ
1716:≤
1702:λ
1688:≠
1670:two-sided
1602:λ
1599:≤
1585:λ
1571:≠
1548:-vertex,
1493:symmetric
1370:∂
1305:∂
1281:≤
1078:∂
1054:≤
932:¯
890:¯
851:⊊
845:⊊
842:∅
756:¯
734:¯
696:| ≤
641:¯
604:∂
501:∈
489:∈
462:∈
395: :=
342:∉
330:∈
303:∈
276:∂
225:∂
202:≤
7707:Category
7679:Archived
7637:18098370
7478:53244523
7352:15323404
7316:15311122
7223:(2006),
7154:Alon, N.
7036:85243045
6942:. SIAM.
6851:14422668
6728:(2015).
6694:(2013).
6620:16411939
6471:41083612
6134:See also
5821:at most
5698:⌉
5655:⌈
5631:diameter
5106:• |
4875:) > 0
4847:that is
4790:regular
4756:Spielman
4144:) < 1
4022:Reingold
3993:Spielman
3966:⌉
3935:⌈
3917:, where
3761:Lubotzky
3576:, where
3439:For all
3437:Theorem.
3165:, where
2749:) = Θ(1/
2648:, where
1898:, where
1852:= 1, …,
1847:for all
1787:Because
1472:, where
1440:-regular
666:and add
84:boundary
56:spectral
7512:1999107
7432:1173532
7396:6364755
7008:Bibcode
6592:Bibcode
6537:Bibcode
6380:8666466
6108:(1, …,
6072:
6055:
6044:are in
6038:(1, …,
6026:⁄
5911:
5894:
5853:are an
5837:of the
5825:of the
5815:⁄
5789:(1, …,
5535:⁄
5511:⁄
5476:⁄
5099:⁄
5083:⁄
4860:1 >
4131:, then
3847:random
3085:zig-zag
3030:⁄
2295:
2281:
2236:is the
2133:where
1902:is the
1857:is the
1839:⁄
1735:, with
1517:≥ … ≥ λ
1450:of the
1397:is the
1194:exactly
1146:is the
703:⁄
569:is the
556:⁄
7635:
7605:
7570:
7552:
7510:
7476:
7458:
7430:
7394:
7384:
7366:
7350:
7340:
7314:
7304:
7260:
7205:
7181:
7129:
7088:
7034:
7026:
6946:
6849:
6841:
6785:420651
6783:
6773:
6665:
6618:
6610:
6555:
6469:
6461:
6378:
6360:
5541:, then
5118:|
4988:). In
4864:> 0
4821:|
4817:|
4796:|
4752:Marcus
4594:Linial
4392:where
4161:) ≤ λ
4129:< 1
4121:< 1
4057:is an
4028:, and
4026:Vadhan
3989:Marcus
3903:> 0
3787:> 0
3765:Sarnak
3047:, and
2725:) ≈ (2
2686:= Θ(1/
2682:) = 4/
2526:Milman
2313:. For
2238:2-norm
1910:. The
1904:degree
1879:is an
1875:, and
1617:as an
1495:, the
1361:where
1134:where
985:(also
798:|
792:|
686:|
483:
477:
324:
318:
268:where
125:(also
111:degree
94:, and
48:vertex
7633:S2CID
7603:S2CID
7546:(PDF)
7508:JSTOR
7474:S2CID
7444:(PDF)
7428:S2CID
7392:S2CID
7348:S2CID
7312:S2CID
7228:(PDF)
7032:S2CID
6909:arXiv
6870:arXiv
6847:S2CID
6800:arXiv
6781:S2CID
6735:(PDF)
6701:(PDF)
6663:S2CID
6645:arXiv
6616:S2CID
6582:arXiv
6553:S2CID
6527:arXiv
6486:arXiv
6467:S2CID
6376:S2CID
6161:Notes
5766:(log
5527:<
4999:In a
4898:) log
4889:with
4566:-lift
4557:Lifts
4083:is a
4037:is a
4005:lifts
3853:have
3507:By a
2657:) = 1
2515:<
2505:. If
2446:When
1826:with
1631:graph
1431:When
1192:with
412:and
388:with
38:is a
34:, an
7568:ISBN
7382:ISBN
7338:ISBN
7302:ISBN
7258:ISBN
7203:ISBN
7179:ISBN
7127:ISSN
7086:ISSN
7024:ISSN
6839:ISSN
6771:ISBN
6608:ISSN
6459:ISSN
6122:and
6058:1 –
5994:and
5974:and
5897:1 –
5883:and
5849:and
5799:and
5738:and
5729:The
5643:, λ)
5629:The
5516:≤ χ(
5487:The
5465:, λ)
5445:, λ)
5150:and
5124:and
5055:and
5035:, λ)
4758:and
4424:and
4400:and
4123:and
3995:and
3907:1 –
3688:<
3642:are
3636:, λ)
3598:<
3587:and
2832:for
2692:and
2659:and
2524:and
2522:Alon
1654:for
1643:, λ)
1627:, λ)
1503:has
1483:and
1442:, a
1418:) \
1265:<
1203:The
1163:) \
1038:<
968:The
403:) \
186:<
121:The
52:edge
7625:doi
7595:doi
7560:doi
7529:doi
7498:doi
7494:284
7466:doi
7420:doi
7374:doi
7328:doi
7294:doi
7240:doi
7117:doi
7076:doi
7016:doi
7004:175
6977:doi
6919:doi
6905:323
6880:doi
6831:doi
6763:doi
6655:doi
6641:256
6600:doi
6578:201
6545:doi
6523:201
6451:doi
6368:doi
6320:− λ
6098:in
6090:in
5998:in
5990:in
5671:log
5659:log
5578:log
5451:An
4794:,
4684:log
4620:log
4561:An
4536:to
4532:l'
4522:Zag
4514:l'
4502:in
4487:k'
4479:to
4465:Zig
4448:to
4165:+ λ
4157:, λ
4140:, λ
4115:If
4101:, λ
4067:, λ
4047:, λ
3664:max
3065:– λ
3044:out
2863:out
2840:in
2697:– λ
2668:= 2
2664:– λ
2474:− λ
2450:is
2409:out
2366:out
2048:max
2022:to
1954:max
1925:− λ
1916:of
1883:of
1861:of
1744:max
1681:max
1659:≠ 1
1564:max
1532:= −
1513:≥ λ
1491:is
1468:of
1435:is
1401:of
1258:min
1180:out
1150:of
1138:out
1082:out
1031:min
1013:out
989:or
977:out
900:min
838:min
619:min
595:min
573:of
179:min
148:on
129:or
54:or
30:In
7709::
7654:,
7631:,
7621:43
7619:,
7601:,
7591:55
7589:,
7566:,
7558:,
7525:27
7523:,
7506:,
7492:,
7472:,
7464:,
7452:54
7450:,
7446:,
7426:,
7416:20
7414:,
7390:,
7380:,
7372:,
7346:,
7336:,
7310:,
7300:,
7284:;
7280:;
7236:43
7230:,
7219:;
7201:,
7177:,
7156:;
7125:.
7111:.
7107:.
7084:.
7072:77
7064:.
7056:;
7052:;
7030:.
7022:.
7014:.
7002:.
6998:.
6971:.
6967:.
6917:.
6903:.
6878:.
6845:.
6837:.
6827:26
6825:.
6779:.
6769:.
6757:.
6743:^
6724:;
6720:;
6709:^
6690:;
6686:;
6675:^
6661:.
6653:.
6639:.
6614:.
6606:.
6598:.
6590:.
6576:.
6551:.
6543:.
6535:.
6521:.
6465:.
6457:.
6445:.
6374:.
6366:.
6352:.
6316:2(
6196:^
6168:^
6034:εk
6019:≤
6004:uv
5889:εn
5835:εk
5823:εk
5808:≤
5639:,
5497:χ(
5495:,
5461:,
5441:,
5140:,
5128:.
5046:⊆
5042:,
5031:,
4996:.
4970:SL
4952:,
4948:,
4944:,
4940:,
4754:,
4661:.
4542:,
4530:,
4512:,
4500:k'
4485:,
4473:,
4454:,
4442:,
4418:,
4386:,
4153:(λ
4136:(λ
4105:))
4097:(λ
4093:,
4089:,
4087:nm
4078:◦
4063:,
4043:,
4024:,
4007:.
3991:,
3632:,
3071:.
3053:in
3038:,
2961:in
2844:.
2493:=
2350:,
2334:.
2275:.
2030::
1934:.
1893:=
1872:du
1870:=
1868:Au
1834:=
1665:.
1639:,
1623:,
1476:ij
1458:=
1423:.
1374:in
1309:in
1240:in
1212:in
1200:.
1176:)
581:.
541:.
531:⊆
380:,
372:=
282::=
133:)
90:,
70:.
50:,
7627::
7597::
7562::
7531::
7515:.
7500::
7481:.
7468::
7435:.
7422::
7408:∞
7376::
7330::
7296::
7242::
7133:.
7119::
7113:2
7092:.
7078::
7038:.
7018::
7010::
6983:.
6979::
6973:5
6952:.
6925:.
6921::
6911::
6886:.
6882::
6872::
6853:.
6833::
6808:.
6802::
6787:.
6765::
6669:.
6657::
6647::
6622:.
6602::
6594::
6584::
6559:.
6547::
6539::
6529::
6494:.
6488::
6473:.
6453::
6447:6
6382:.
6370::
6354:6
6324:)
6322:2
6318:d
6311:2
6309:λ
6273:.
6261:.
6128:ε
6124:B
6120:A
6116:B
6112:)
6110:k
6104:A
6100:Y
6096:B
6092:X
6088:A
6084:k
6080:X
6075:k
6068:ε
6064:/
6060:ε
6050:Y
6046:B
6042:)
6040:k
6028:2
6023:n
6017:k
6012:v
6008:u
6000:Y
5996:v
5992:X
5988:u
5984:ε
5980:Y
5976:B
5972:X
5968:A
5964:d
5957:d
5953:Y
5949:X
5945:Y
5941:X
5936:Y
5932:X
5928:d
5924:Y
5920:X
5907:ε
5903:/
5899:ε
5885:Y
5881:X
5877:d
5873:n
5869:ε
5866:d
5855:ε
5851:B
5847:A
5843:A
5839:k
5831:B
5827:k
5817:2
5812:n
5806:k
5801:B
5797:A
5793:)
5791:n
5785:n
5781:ε
5777:ε
5770:)
5768:n
5764:O
5702:.
5691:)
5684:/
5680:d
5677:(
5667:n
5641:d
5637:n
5635:(
5614:.
5610:)
5604:)
5597:/
5593:d
5590:+
5587:1
5584:(
5574:d
5569:(
5565:O
5559:)
5556:G
5553:(
5537:3
5532:n
5530:2
5525:d
5520:)
5518:G
5513:λ
5508:d
5501:)
5499:G
5493:G
5484:.
5479:d
5473:n
5471:λ
5463:d
5459:n
5457:(
5443:d
5439:n
5437:(
5420:.
5414:|
5410:T
5406:|
5398:|
5394:S
5390:|
5377:|
5371:n
5366:|
5362:T
5358:|
5350:|
5346:S
5342:|
5335:d
5326:)
5323:T
5320:,
5317:S
5314:(
5311:E
5307:|
5280:.
5277:)
5274:S
5268:T
5265:,
5262:S
5259:(
5256:E
5253:+
5250:)
5247:T
5244:,
5241:T
5235:S
5232:(
5229:E
5226:+
5222:|
5218:)
5215:]
5212:T
5206:S
5203:[
5200:G
5197:(
5194:E
5190:|
5186:2
5183:=
5180:)
5177:T
5174:,
5171:S
5168:(
5165:E
5152:T
5148:S
5144:)
5142:T
5138:S
5136:(
5134:E
5126:T
5122:S
5115:T
5109:S
5102:n
5096:d
5086:n
5080:d
5069:d
5065:λ
5061:d
5057:T
5053:S
5048:V
5044:T
5040:S
5033:d
5029:n
5027:(
4984:(
4976:(
4974:L
4956:(
4917:ε
4912:n
4908:G
4903:n
4900:2
4896:ε
4894:(
4892:c
4887:G
4883:n
4879:G
4873:ε
4871:(
4869:c
4862:ε
4856:)
4854:d
4852:(
4850:O
4845:d
4840:d
4838:c
4833:n
4831:d
4829:c
4824:S
4814:S
4809:d
4805:)
4803:S
4801:(
4799:N
4788:d
4784:n
4771:r
4732:1
4726:d
4721:2
4701:)
4696:d
4688:3
4680:d
4675:(
4672:O
4659:d
4655:d
4637:)
4632:d
4624:3
4616:d
4611:(
4608:O
4598:d
4580:r
4570:r
4564:r
4552:.
4550:H
4546:)
4544:l
4540:w
4538:(
4534:)
4528:w
4526:(
4518:.
4516:)
4510:w
4508:(
4504:G
4495:.
4493:H
4489:)
4483:v
4481:(
4477:)
4475:k
4471:v
4469:(
4458:)
4456:l
4452:w
4450:(
4446:)
4444:k
4440:v
4438:(
4434:)
4432:l
4430:,
4428:w
4426:(
4422:)
4420:k
4416:v
4414:(
4410:v
4406:k
4402:k
4398:G
4394:v
4390:)
4388:k
4384:v
4382:(
4378:m
4374:G
4354:.
4347:2
4342:2
4334:4
4331:+
4326:2
4321:1
4311:2
4307:)
4301:2
4296:2
4285:1
4282:(
4275:2
4272:1
4267:+
4262:2
4254:)
4249:2
4244:2
4233:1
4230:(
4225:2
4222:1
4217:=
4214:)
4209:2
4201:,
4196:1
4188:(
4170:.
4167:2
4163:1
4159:2
4155:1
4151:φ
4146:;
4142:2
4138:1
4134:φ
4127:2
4125:λ
4119:1
4117:λ
4109:φ
4103:2
4099:1
4095:φ
4091:d
4085:(
4080:H
4076:G
4071:)
4069:2
4065:d
4061:m
4059:(
4055:H
4051:)
4049:1
4045:m
4041:n
4039:(
4035:G
3970:.
3961:2
3957:1
3954:+
3949:1
3943:d
3931:=
3915:)
3913:n
3911:(
3909:O
3901:ε
3883:+
3878:1
3872:d
3867:2
3849:d
3843:d
3837:.
3822:+
3817:1
3811:d
3806:2
3785:ε
3780:n
3776:n
3772:d
3754:2
3752:λ
3735:.
3730:1
3724:d
3719:2
3712:|
3706:i
3697:|
3691:d
3684:|
3678:i
3669:|
3660:=
3644:d
3634:d
3630:n
3628:(
3612:1
3606:d
3601:2
3585:d
3580:2
3578:λ
3564:)
3561:1
3558:(
3555:o
3547:1
3541:d
3536:2
3528:2
3513:d
3492:.
3478:2
3473:5
3467:)
3464:G
3461:(
3447:n
3445:G
3441:n
3417:.
3414:)
3411:)
3408:1
3405:+
3402:x
3399:2
3396:(
3390:y
3387:,
3384:x
3381:(
3378:,
3375:)
3372:x
3369:2
3363:y
3360:,
3357:x
3354:(
3351:,
3348:)
3345:y
3342:,
3339:)
3336:1
3333:+
3330:y
3327:2
3324:(
3318:x
3315:(
3312:,
3309:)
3306:y
3303:,
3300:y
3297:2
3291:x
3288:(
3263:n
3258:Z
3248:n
3243:Z
3235:)
3232:y
3229:,
3226:x
3223:(
3202:Z
3198:n
3194:/
3189:Z
3185:=
3180:n
3175:Z
3151:n
3146:Z
3136:n
3131:Z
3118:n
3116:G
3112:n
3069:)
3067:2
3063:d
3061:(
3059:O
3050:h
3041:h
3033:d
3027:h
3007:.
3002:)
2997:2
2986:d
2983:(
2980:8
2972:)
2969:G
2966:(
2957:h
2935:1
2927:2
2922:)
2918:1
2915:+
2910:)
2905:2
2894:d
2891:(
2888:4
2882:(
2874:)
2871:G
2868:(
2859:h
2813:.
2806:2
2801:2
2788:2
2784:d
2775:)
2772:G
2769:(
2766:h
2753:)
2751:n
2747:n
2745:/
2723:n
2721:/
2699:2
2695:d
2690:)
2688:n
2684:n
2679:n
2677:C
2675:(
2673:h
2666:2
2662:d
2655:G
2653:(
2651:h
2645:n
2643:Q
2623:.
2618:)
2613:2
2602:d
2599:(
2596:d
2593:2
2585:)
2582:G
2579:(
2576:h
2570:)
2565:2
2554:d
2551:(
2545:2
2542:1
2517:d
2513:2
2511:λ
2507:G
2502:2
2500:λ
2495:d
2491:1
2489:λ
2485:d
2481:G
2476:2
2472:d
2467:)
2465:G
2463:(
2461:h
2456:d
2452:d
2448:G
2423:.
2420:)
2417:G
2414:(
2405:h
2398:d
2392:)
2389:G
2386:(
2383:h
2377:)
2374:G
2371:(
2362:h
2348:G
2344:d
2331:A
2328:A
2323:A
2307:G
2298:A
2291:d
2287:/
2284:1
2261:n
2256:R
2248:v
2219:2
2215:/
2211:1
2206:)
2200:2
2195:i
2191:v
2185:n
2180:1
2177:=
2174:i
2165:(
2160:=
2155:2
2147:v
2118:,
2110:2
2102:v
2092:2
2084:v
2081:A
2070:0
2064:v
2061:,
2058:u
2052:v
2044:=
2024:u
2003:}
1999:|
1993:n
1984:|
1980:,
1976:|
1970:2
1961:|
1957:{
1951:=
1932:G
1927:2
1923:d
1918:G
1908:G
1900:d
1895:d
1891:1
1889:λ
1885:A
1877:u
1863:G
1854:n
1850:i
1842:n
1837:1
1831:i
1829:u
1812:n
1807:R
1799:u
1789:G
1764:i
1754:1
1748:i
1712:|
1706:i
1697:|
1691:1
1685:i
1657:i
1650:i
1647:λ
1641:d
1637:n
1635:(
1629:-
1625:d
1621:n
1619:(
1595:|
1589:i
1580:|
1574:1
1568:i
1550:d
1546:n
1539:G
1534:d
1529:n
1526:λ
1520:n
1515:2
1511:1
1509:λ
1505:n
1501:A
1489:A
1485:j
1481:i
1474:A
1470:G
1466:)
1464:G
1462:(
1460:A
1456:A
1438:d
1433:G
1420:S
1416:G
1414:(
1412:V
1407:S
1403:S
1385:)
1382:S
1379:(
1346:,
1339:|
1335:S
1331:|
1324:|
1320:)
1317:S
1314:(
1300:|
1289:2
1286:n
1277:|
1273:S
1269:|
1262:0
1254:=
1251:)
1248:G
1245:(
1236:h
1222:G
1218:)
1216:G
1214:(
1209:h
1198:S
1190:V
1186:)
1184:S
1182:(
1178:∂
1170:S
1165:S
1161:G
1159:(
1157:V
1152:S
1144:)
1142:S
1140:(
1136:∂
1119:,
1112:|
1108:S
1104:|
1097:|
1093:)
1090:S
1087:(
1073:|
1062:2
1059:n
1050:|
1046:S
1042:|
1035:0
1027:=
1024:)
1021:G
1018:(
1009:h
995:G
983:)
981:G
979:(
974:h
948:.
942:}
938:|
929:S
923:|
919:,
915:|
911:S
907:|
903:{
895:)
887:S
882:,
878:S
874:(
871:E
863:)
860:G
857:(
854:V
848:S
834:=
831:)
828:G
825:(
822:h
809:)
807:G
805:(
803:h
795:S
788:)
786:G
784:(
782:h
767:)
764:S
761:,
753:S
748:(
745:E
742:=
739:)
731:S
726:,
723:S
720:(
717:E
705:2
700:n
693:S
683:S
681:∂
672:n
668:n
664:n
646:)
638:S
633:,
629:S
625:(
622:E
616:=
611:|
607:S
600:|
579:S
575:S
566:S
564:∂
558:2
553:n
546:S
539:)
537:G
535:(
533:V
529:B
527:,
525:A
507:}
504:B
498:v
495:,
492:A
486:u
480::
474:)
471:G
468:(
465:E
459:}
456:v
453:,
450:u
447:{
444:{
441:=
438:)
435:B
432:,
429:A
426:(
423:E
410:S
405:S
401:G
399:(
397:V
392:S
386:)
383:S
378:S
376:(
374:E
370:S
368:∂
351:,
348:}
345:S
339:v
336:,
333:S
327:u
321::
315:)
312:G
309:(
306:E
300:}
297:v
294:,
291:u
288:{
285:{
279:S
254:,
247:|
243:S
239:|
232:|
228:S
221:|
210:2
207:n
198:|
194:S
190:|
183:0
175:=
172:)
169:G
166:(
163:h
150:n
146:G
142:)
140:G
138:(
136:h
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.