Main Page: Difference between revisions

Revision as of 13:09, 8 August 2014

In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.^[1]

Definitions

Intuitively, an expander is a finite, undirected multigraph in which every subset of the vertices "which is not too large" has a "large" boundary. Different formalisations of these notions give rise to different notions of expanders: edge expanders, vertex expanders, and spectral expanders, as defined below.

A disconnected graph is not an expander, since the boundary of a connected component is empty. Every connected graph is an expander; however, different connected graphs have different expansion parameters. The complete graph has the best expansion property, but it has largest possible degree. Informally, a graph is a good expander if it has low degree and high expansion parameters.

Edge expansion

The edge expansion (also isoperimetric number or Cheeger constant) $h(G)$ of a graph $G$ is defined as

h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial (S)|}{|S|}}\,,

where the minimum is over all nonempty sets $S$ of at most $n/2$ vertices and $\partial (S)$ is the edge boundary of $S$ , i.e., the set of edges with exactly one endpoint in $S$ .^[2]

Vertex expansion

The vertex isoperimetric number $h_{\text{out}}(G)$ (also vertex expansion or magnification) of a graph $G$ is defined as

h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}}\,,

where $\partial _{\text{out}}(S)$ is the outer boundary of $S$ , i.e., the set of vertices in $V(G)\setminus S$ with at least one neighbor in $S$ .^[3] In a variant of this definition (called unique neighbor expansion) $\partial _{\text{out}}(S)$ is replaced by the set of vertices in $V$ with exactly one neighbor in $S$ .^[4]

The vertex isoperimetric number $h_{\text{in}}(G)$ of a graph $G$ is defined as

h_{\text{in}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{in}}(S)|}{|S|}}\,,

where $\partial _{\text{in}}(S)$ is the inner boundary of $S$ , i.e., the set of vertices in $S$ with at least one neighbor in $V(G)\setminus S$ .^[3]

Spectral expansion

When $G$ is regular, a linear algebraic definition of expansion is possible based on the eigenvalues of the adjacency matrix $A=A(G)$ of $G$ , where $A_{ij}$ is the number of edges between vertices $i$ and $j$ .^[5] Because $A$ is symmetric, the spectral theorem implies that $A$ has $n$ real-valued eigenvalues $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$ . It is known that all these eigenvalues are in $[-d,d]$ .

Because $G$ is regular, the uniform distribution $u\in \mathbb {R} ^{n}$ with $u_{i}=1/n$ for all $i=1,\dots ,n$ is the stationary distribution of $G$ . That is, we have $Au=du$ , and $u$ is an eigenvector of $A$ with eigenvalue $\lambda _{1}=d$ , where $d$ is the degree of the vertices of $G$ . The spectral gap of $G$ is defined to be $d-\lambda _{2}$ , and it measures the spectral expansion of the graph $G$ .^[6]

It is known that $\lambda _{n}=-d$ if and only if $G$ is bipartite. In many context, for example in the expander mixing lemma, it is necessary to bound from below not only the gap between $\lambda _{1}$ and $\lambda _{2}$ , but also the gap between $\lambda _{1}$ and the second-largest eigenvalue in absolute value: $\lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}$ . Since this is the largest eigenvalue corresponding to an eigenvector orthogonal to $u$ , it can be equivalently defined using the Rayleigh quotient:

\lambda =\max _{0\neq v\perp u}{\frac {\|Av\|_{2}}{\|v\|_{2}}}\,,

where $\|v\|_{2}=\left(\sum _{i=1}^{n}v_{i}^{2}\right)^{1/2}$ is the 2-norm of the vector $v\in \mathbb {R} ^{n}$ .

The normalized versions of these definitions are also widely used and more convenient in stating some results. Here one considers the matrix ${\frac {1}{d}}A$ , which is the Markov transition matrix of the graph $G$ . 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 Laplacian matrix. For directed graphs, one considers the singular values of the adjacency matrix $A$ , which are equal to the roots of the eigenvalues of the symmetric matrix $A^{T}A$ .

Relationships between different expansion properties

The expansion parameters defined above are related to each other. In particular, for any $d$ -regular graph $G$ ,

h_{\text{out}}(G)\leq h(G)\leq d\cdot h_{\text{out}}(G)\,.

Consequently, for constant degree graphs, vertex and edge expansion are qualitatively the same.

Cheeger inequalities

When $G$ is $d$ -regular, there is a relationship between $h(G)$ and the spectral gap $d-\lambda _{2}$ of $G$ . An inequality due to Tanner and independently Alon and Milman Template:Sfn states that

{\frac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}\,.

^[7]

This inequality is closely related to the Cheeger bound for Markov chains and can be seen as a discrete version of Cheeger's inequality in Riemannian geometry.

Similar connections between vertex isoperimetric numbers and the spectral gap have also been studied:^[8]

h_{\text{out}}(G)\leq \left({\sqrt {4(d-\lambda _{2})}}+1\right)^{2}-1

h_{\text{in}}(G)\leq {\sqrt {8(d-\lambda _{2})}}.

Asymptotically speaking, the quantities ${\frac {h^{2}}{d}}$ , $h_{\text{out}}$ , and $h_{\text{in}}^{2}$ are all bounded above by the spectral gap $O(d-\lambda _{2})$ .

Examples of expanders

Petersen graph

Consider the 3-regular graph G on 10 vertices (n = 10, d = 3) shown.

If we number the vertices by going around twice, starting with the outside pentagon and then the inside pentagon, G has the following adjacency matrix:

${\begin{pmatrix}0&1&0&0&1&1&0&0&0&0\\1&0&1&0&0&0&1&0&0&0\\0&1&0&1&0&0&0&1&0&0\\0&0&1&0&1&0&0&0&1&0\\1&0&0&1&0&0&0&0&0&1\\1&0&0&0&0&0&0&1&1&0\\0&1&0&0&0&0&0&0&1&1\\0&0&1&0&0&1&0&0&0&1\\0&0&0&1&0&1&1&0&0&0\\0&0&0&0&1&0&1&1&0&0\\\end{pmatrix}}$

One can calculate that the two largest eigenvalues of this matrix are 3 and 1. From this, one may deduce that

${\frac {d-\lambda _{2}}{2}}={\frac {3-1}{2}}=1$

${\sqrt {2d(d-\lambda _{2})}}={\sqrt {2\cdot 3(3-1)}}=2{\sqrt {3}}$ and consequently that $1\leq h(G)\leq 2{\sqrt {3}}\approx 3.46$ .

In fact, $h(G)=1$ . To persuade oneself of this, it suffices to consider the five vertices in the central star: there are five edges that touch exactly one of these vertices, giving an edge expansion for this set of 5/5 = 1.

Ramanujan graphs

By a theorem of Alon and Boppana, all large enough $d$ -regular graphs satisfy $\lambda \geq 2{\sqrt {d-1}}-o(1)$ .^[9] Ramanujan graphs are $d$ -regular graphs that meet this bound, that is, they satisfy $\lambda \leq 2{\sqrt {d-1}}$ .^[10] Hence Ramanujan graphs have an asymptotically smallest possible second-largest eigenvalue $\lambda$ (in absolute value).

Lubotzky, Phillips, and Sarnak (1988), Margulis (1988), and Morgenstern (1994) show how Ramanujan graphs can be constructed explicitly.^[11] By a theorem of Friedman (2003), random d-regular graphs on $n$ vertices are almost Ramanujan, that is, they satisfy $\lambda \leq 2{\sqrt {d-1}}+\epsilon$ with probability $1-o(1)$ as $n$ tends to infinity.^[12]

Other examples

Algebraic constructions based on Cayley graphs are known for various variants of expander graphs. Most recently, combinatorial constructions of expanders have also been discovered.

Applications and useful properties

The original motivation for expanders is to build economical robust networks (phone or computer): an expander with bounded valence is precisely an asymptotic robust graph with number of edges growing linearly with size (number of vertices), for all subsets.

Expander graphs have found extensive applications in computer science, in designing algorithms, error correcting codes, extractors, pseudorandom generators, sorting networks (Template:Harvtxt) and robust computer networks. They have also been used in proofs of many important results in computational complexity theory, such as SL=L (Template:Harvtxt) and the PCP theorem (Template:Harvtxt). In cryptography, expander graphs are used to construct hash functions.

The following are some properties of expander graphs that have proven useful in many areas.

Expander mixing lemma

Mining Engineer (Excluding Oil ) Truman from Alma, loves to spend time knotting, largest property developers in singapore developers in singapore and stamp collecting. Recently had a family visit to Urnes Stave Church. The expander mixing lemma states that, for any two subsets of the vertices $S,T\subseteq V$ , the number of edges between $S$ and $T$ is approximately what you would expect in a random $d$ -regular graph. The approximation is better, the smaller $\lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}$ is. In a random $d$ -regular graph, as well as in an Erdős–Rényi random graph with edge probability $d/n$ , we expect ${\frac {d}{n}}\cdot |S|\cdot |T|$ edges between $S$ and $T$ .

More formally, let $E(S,T)$ denote the number of edges between $S$ and $T$ . If the two sets are not disjoint, edges in their intersection are counted twice, that is, $E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S)$ .

Then the expander mixing lemma says that the following inequality holds:

\left|E(S,T)-{\frac {d\cdot |S|\cdot |T|}{n}}\right|\leq d\lambda {\sqrt {|S|\cdot |T|}}\,.

where $\lambda$ is the absolute value of the normalized second largest eigenvalue.

Expander walk sampling

Mining Engineer (Excluding Oil ) Truman from Alma, loves to spend time knotting, largest property developers in singapore developers in singapore and stamp collecting. Recently had a family visit to Urnes Stave Church. The Chernoff bound states that, when sampling many independent samples from a random variables in the range $[-1,1]$ , with high probability the average of our samples is close to the expectation of the random variable. The expander walk sampling lemma, due to Template:Harvtxt and Template:Harvtxt, states that this also holds true when sampling from a walk on an expander graph. This is particularly useful in the theory of derandomization, since sampling according to an expander walk uses many fewer random bits than sampling independently.

Notes

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

References

Template:Refbegin Textbooks and surveys

20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

My blog: http://www.primaboinca.com/view_profile.php?userid=5889534
Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010
Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010
Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010
Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010

Research articles

Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010
Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010
Template:Cite doi
Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010}.
Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010.
Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010
Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010

Template:Refend

External links

cs:Expander (graf) fr:Graphe expanseur he:גרף מרחיב pl:Ekspander

↑ Template:Harvtxt
↑ Definition 2.1 in Template:Harvtxt
↑ ^3.0 ^3.1 Template:Harvtxt
↑ Template:Harvtxt
↑ cf. Section 2.3 in Template:Harvtxt
↑ This definition of the spectral gap is from Section 2.3 in Template:Harvtxt
↑ Theorem 2.4 in Template:Harvtxt
↑ See Theorem 1 and p.156, l.1 in Template:Harvtxt. Note that λ₂ there corresponds to 2(d − λ₂) of the current article (see p.153, l.5)
↑ Theorem 2.7 of Template:Harvtxt
↑ Definition 5.11 of Template:Harvtxt
↑ Theorem 5.12 of Template:Harvtxt
↑ Theorem 7.10 of Template:Harvtxt

[1] Template:Harvtxt

[2] Definition 2.1 in Template:Harvtxt

[BobkovHoudre-3] 3.0 ^3.1 Template:Harvtxt

[AlonCapalbo-4] Template:Harvtxt

[5] . Section 2.3 in Template:Harvtxt

[6] This definition of the spectral gap is from Section 2.3 in Template:Harvtxt

[7] Theorem 2.4 in Template:Harvtxt

[8] See Theorem 1 and p.156, l.1 in Template:Harvtxt. Note that λ₂ there corresponds to 2(d − λ₂) of the current article (see p.153, l.5)

[9] Theorem 2.7 of Template:Harvtxt

[10] Definition 5.11 of Template:Harvtxt

[11] Theorem 5.12 of Template:Harvtxt

[12] Theorem 7.10 of Template:Harvtxt

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Main Page: Difference between revisions

Revision as of 13:09, 8 August 2014

Contents

Definitions

Edge expansion

Vertex expansion

Spectral expansion

Relationships between different expansion properties

Cheeger inequalities

Examples of expanders

Petersen graph

Ramanujan graphs

Other examples

Applications and useful properties

Expander mixing lemma

Expander walk sampling

See also

Notes

References

External links

Navigation menu

@@ Line 1: / Line 1: @@
-{{about|the general aspects of dynamical systems|technical details|Dynamical system (definition)|the study|Dynamical systems theory}}
+In [[combinatorics]], an '''expander graph''' is a [[sparse graph]] that has strong [[connectivity (graph theory)|connectivity]] properties, quantified using [[vertex (graph theory)|vertex]], [[edge (graph theory)|edge]] or spectral expansion as described below. Expander constructions have spawned research in pure and applied mathematics, with several applications to [[Computational complexity theory|complexity theory]], design of robust [[computer network]]s, and the theory of [[error-correcting code]]s.<ref>{{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
-{{Redirect|Dynamical}}
-{{Refimprove|date=July 2011}}
-[[File:Lorenz attractor yb.svg|thumb|200px|right||The [[Lorenz attractor]] arises in the study of the Lorenz Oscillator, a dynamical system.]]
+==Definitions==
-A '''dynamical system''' is a concept in mathematics where a [[Function (mathematics)|fixed rule]] describes the time dependence of a point in a [[configuration space|geometrical space]].  Examples include the [[mathematical model]]s that describe the swinging of a clock pendulum, the flow of water in a pipe, and the number of fish each springtime in a lake.
+Intuitively, an expander is a finite, undirected [[multigraph]] in which every subset of the vertices "which is not too large" has a "large" boundary. Different formalisations of these notions give rise to different notions of expanders: ''edge expanders'', ''vertex expanders'', and ''spectral expanders'', as defined below.
-At any given time a dynamical system has a ''[[State (controls)|state]]'' given by a set of [[real numbers]] (a [[vector space|vector]]) that can be represented by a [[Point (geometry)|point]] in an appropriate ''[[state space]]'' (a geometrical [[manifold]]).  Small changes in the state of the system create small changes in the numbers. The ''evolution rule'' of the dynamical system is a [[function (mathematics)|fixed rule]] that describes what future states follow from the current state.  The rule is [[Deterministic system (mathematics)|deterministic]]; in other words, for a given time interval only one future state follows from the current state.
+A disconnected graph is not an expander, since the boundary of a connected component is empty. Every connected graph is an expander; however, different connected graphs have different expansion parameters. The [[complete graph]] has the best expansion property, but it has largest possible degree. Informally, a graph is a good expander if it has low degree and high expansion parameters.
-==Overview==
+===Edge expansion===
-The concept of a dynamical system has its origins in [[Newtonian mechanics]].  There, as in other natural sciences and engineering disciplines, the evolution rule of dynamical systems is given implicitly by a relation that gives the state of the system only a short time into the future.  (The relation is either a [[differential equation]], [[Recurrence relation|difference equation]] or other [[Time scale calculus|time scale]].)  To determine the state for all future times requires iterating the relation many times&mdash;each advancing time a small step.  The iteration procedure is referred to as ''solving the system'' or ''integrating the system''. Once the system can be solved, given an initial point it is possible to determine all its future positions, a collection of points known as a ''[[trajectory]]'' or ''[[orbit (dynamics)|orbit]]''.
+The ''edge expansion'' (also ''isoperimetric number'' or [[Cheeger constant (graph theory)|Cheeger constant]]) <math>h(G)</math> of a graph <math>G</math> is defined as
+: <math>h(G) = \min_{0 < |S| \le \frac{n}{2} } \frac{|\partial(S)|}{|S|}\,,</math>
+where the minimum is over all nonempty sets <math>S</math> of at most <math>n/2</math> vertices and <math>\partial(S)</math> is the ''edge boundary'' of <math>S</math>, i.e., the set of edges with exactly one endpoint in <math>S</math>.<ref>Definition 2.1 in {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
-Before the advent of [[computer|fast computing machines]], solving a dynamical system required sophisticated mathematical techniques and could be accomplished only for a small class of dynamical systems.  Numerical methods implemented on electronic computing machines have simplified the task of determining the orbits of a dynamical system.
+===Vertex expansion===
+The ''vertex isoperimetric number'' <math>h_{\text{out}}(G)</math> (also ''vertex expansion'' or ''magnification'') of a graph <math>G</math> is defined as
+: <math>h_{\text{out}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|}\,,</math>
+where <math>\partial_{\text{out}}(S)</math> is the ''outer boundary'' of <math>S</math>, i.e., the set of vertices in <math>V(G)\setminus S</math> with at least one neighbor in <math>S</math>.<ref name="BobkovHoudre">{{harvtxt|Bobkov|Houdré|Tetali|2000}}</ref>
+In a variant of this definition (called ''unique neighbor expansion'') <math>\partial_{\text{out}}(S)</math> is replaced by the set of vertices in <math>V</math> with ''exactly'' one neighbor in <math>S</math>.<ref name="AlonCapalbo">{{harvtxt|Alon|Capalbo|2002}}</ref>
-For simple dynamical systems, knowing the trajectory is often sufficient, but most dynamical systems are too complicated to be understood in terms of individual trajectories.  The difficulties arise because:
+The ''vertex isoperimetric number'' <math>h_{\text{in}}(G)</math> of a graph <math>G</math> is defined as
-* The systems studied may only be known approximately&mdash;the parameters of the system may not be known precisely or terms may be missing from the equations.  The approximations used bring into question the validity or relevance of numerical solutions.  To address these questions several notions of stability have been introduced in the study of dynamical systems, such as [[Lyapunov stability]] or [[structural stability]].  The stability of the dynamical system implies that there is a class of models or initial conditions for which the trajectories would be equivalent. The operation for comparing orbits to establish their [[Equivalence relation|equivalence]] changes with the different notions of stability.
+: <math>h_{\text{in}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{in}}(S)|}{|S|}\,,</math>
-* The type of trajectory may be more important than one particular trajectory.  Some trajectories may be periodic, whereas others may wander through many different states of the system. Applications often require enumerating these classes or maintaining the system within one class.  Classifying all possible trajectories has led to the qualitative study of dynamical systems, that is, properties that do not change under coordinate changes. [[Linear dynamical system]]s and [[Poincaré–Bendixson theorem|systems that have two numbers describing a state]] are examples of dynamical systems where the possible classes of orbits are understood.
+where <math>\partial_{\text{in}}(S)</math> is the ''inner boundary'' of <math>S</math>, i.e., the set of vertices in <math>S</math> with at least one neighbor in <math>V(G)\setminus S</math>.<ref name="BobkovHoudre" />
-* The behavior of trajectories as a function of a parameter may be what is needed for an application. As a parameter is varied, the dynamical systems may have [[bifurcation theory|bifurcation points]] where the qualitative behavior of the dynamical system changes.  For example, it may go from having only periodic motions to apparently erratic behavior, as in the [[Turbulence|transition to turbulence of a fluid]].
-* The trajectories of the system may appear erratic, as if random.  In these cases it may be necessary to compute averages using one very long trajectory or many different trajectories.  The averages are well defined for [[ergodic theory|ergodic systems]] and a more detailed understanding has been worked out for [[Anosov diffeomorphism|hyperbolic systems]]. Understanding the probabilistic aspects of dynamical systems has helped establish the foundations of [[statistical mechanics]] and of [[chaos theory|chaos]].
-It was in the work of [[Henri Poincaré|Poincaré]] that these dynamical systems themes developed.{{citation needed|date=July 2012}}
-==Basic definitions==
+===Spectral expansion===
-{{Main|Dynamical system (definition)}}
+When <math>G</math> is [[regular graph|regular]], a [[linear algebra]]ic definition of expansion is possible based on the [[Eigenvalue#Eigenvalues of matrices|eigenvalues]] of the [[adjacency matrix]] <math>A=A(G)</math> of <math>G</math>, where <math>A_{ij}</math> is the number of edges between vertices <math>i</math> and <math>j</math>.<ref>cf. Section 2.3 in {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
+Because <math>A</math> is [[symmetric matrix|symmetric]], the [[spectral theorem]] implies that <math>A</math> has <math>n</math> real-valued eigenvalues <math>\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_{n}</math>.
+It is known that all these eigenvalues are in <math>[-d,d]</math>.
-A dynamical system is a [[manifold]] ''M'' called the phase (or state) space endowed with a family of smooth evolution functions Φ<sup>''t''</sup> that for any element of ''t'' ∈ ''T'', the time, map a point of the phase space back into the phase space.  The notion of smoothness changes with applications and the type of manifold.  There are several choices for the set&nbsp;''T''.  When ''T'' is taken to be the reals, the dynamical system is called a ''[[Flow (mathematics)|flow]]''; and if ''T'' is restricted to the non-negative reals, then the dynamical system is  a ''semi-flow''.   When ''T'' is taken to be the integers, it is a ''cascade'' or a ''map''; and the restriction to the non-negative integers is  a ''semi-cascade''.
+Because <math>G</math> is regular, the uniform distribution <math>u\in\R^n</math> with <math>u_i=1/n</math> for all <math>i=1,\dots,n</math> is the [[stationary distribution]] of <math>G</math>.
+That is, we have <math>Au=du</math>, and <math>u</math> is an eigenvector of <math>A</math> with eigenvalue <math>\lambda_1=d</math>, where <math>d</math> is the [[degree (graph theory)|degree]] of the vertices of <math>G</math>.
+The ''[[spectral gap]]'' of <math>G</math> is defined to be <math>d-\lambda_2</math>, and it measures the spectral expansion of the graph <math>G</math>.<ref>This definition of the spectral gap is from Section 2.3 in {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
-=== Examples ===
+It is known that <math>\lambda_n=-d</math> if and only if <math>G</math> is bipartite.
+In many context, for example in the [[expander mixing lemma]], it is necessary to bound from below not only the gap between <math>\lambda_1</math> and <math>\lambda_2</math>, but also the gap between <math>\lambda_1</math> and
+the second-largest eigenvalue in absolute value:
+<math>\lambda=\max\{|\lambda_2|, |\lambda_{n}|\}</math>.
+Since this is the largest eigenvalue corresponding to an eigenvector orthogonal to <math>u</math>, it can be equivalently defined using the [[Rayleigh quotient]]:
+:<math>\lambda=\max_{0\neq v\perp u} \frac{\|Av\|_2}{\|v\|_2}\,,</math>
+where <math>\|v\|_2=\left(\sum_{i=1}^n v_i^2\right)^{1/2}</math> is the [[2-norm]] of the vector <math>v\in\R^n</math>.
-The evolution function Φ<sup>&nbsp;''t''</sup> is often the solution of a ''differential equation of motion''
+The normalized versions of these definitions are also widely used and more convenient in stating some results.
+Here one considers the matrix <math>\frac{1}{d} A</math>, which is the [[Markov transition matrix]] of the graph <math>G</math>.
+Its eigenvalues are between <math>-1</math> and <math>1</math>.
+For not necessarily regular graphs, the spectrum of a graph can be defined similarly using the eigenvalues of the [[Laplacian matrix]].
+For directed graphs, one considers the [[singular values]] of the adjacency matrix <math>A</math>, which are equal to the roots of the eigenvalues of the symmetric matrix <math>A^T A</math>.
-:  <math> \dot{x} = v(x). \, </math>
+==Relationships between different expansion properties==
+The expansion parameters defined above are related to each other.
+In particular, for any <math>d</math>-regular graph <math>G</math>,
+:<math>h_{\text{out}}(G) \le h(G) \le d \cdot h_{\text{out}}(G)\,.</math>
-The equation gives the time derivative, represented by the dot, of  a trajectory ''x''(''t'') on the phase space starting at some point&nbsp;''x''<sub>0</sub>.  The ''vector field'' ''v''(''x'') is a smooth function that at every point of the phase space ''M'' provides the velocity vector of the dynamical system at that point. (These vectors are not vectors in the phase space&nbsp;''M'', but in the [[tangent space]] ''T<sub>x</sub>M'' of the point&nbsp;''x''.)  Given a smooth Φ<sup>&nbsp;''t''</sup>, an autonomous vector field can be derived from it.
+Consequently, for constant degree graphs, vertex and edge expansion are qualitatively the same.
-There is no need for higher order derivatives in the equation, nor for time dependence in ''v''(''x'') because these can be eliminated by considering systems of higher dimensions.  Other types of differential equations can be used to define the evolution rule:
+===Cheeger inequalities===
+When <math>G</math> is <math>d</math>-regular, there is a relationship between <math>h(G)</math> and the spectral gap <math>d - \lambda_2</math> of <math>G</math>.  An inequality due to Tanner and independently [[Noga Alon|Alon]] and [[Vitali Milman|Milman]]{{Sfn|Alon|Spencer|2011}} states that
-: <math> G(x, \dot{x}) = 0 \, </math>
+: <math>\frac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}\,.</math><ref>Theorem 2.4 in {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
-is an example of an equation that arises from the modeling of mechanical systems with complicated constraints.
+This inequality is closely related to the [[Cheeger bound]] for [[Markov chains]] and can be seen as a discrete version of [[Cheeger_constant#Cheeger.27s_inequality|Cheeger's inequality]] in [[Riemannian geometry]].
-The differential equations determining the evolution function Φ<sup>&nbsp;''t''</sup> are often [[ordinary differential equation]]s: in this case the phase space ''M'' is a finite dimensional manifold.  Many of the concepts in dynamical systems can be extended to infinite-dimensional manifolds&mdash;those that are locally [[Banach space]]s&mdash;in which case the differential equations are [[partial differential equation]]s.  In the late 20th century the dynamical system perspective to partial differential equations started gaining popularity.
+Similar connections between vertex isoperimetric numbers and the spectral gap have also been studied:<ref>See Theorem 1 and p.156, l.1 in {{harvtxt|Bobkov|Houdré|Tetali|2000}}. Note that ''&lambda;''<sub>2</sub> there corresponds to 2(''d''&nbsp;&minus;&nbsp;''&lambda;''<sub>2</sub>) of the current article (see p.153, l.5)</ref>
+: <math>h_{\text{out}}(G)\le \left(\sqrt{4 (d-\lambda_2)} + 1\right)^2 -1</math>
+: <math>h_{\text{in}}(G) \le \sqrt{8(d-\lambda_2)}.</math>
+Asymptotically speaking, the quantities
+<math>\frac{h^2}{d}</math>, <math>h_{\text{out}}</math>, and <math>h_{\text{in}}^2</math> are all bounded above by the spectral gap <math>O(d-\lambda_2)</math>.
-=== Further examples ===
+==Examples of expanders==
-<div style="-moz-column-count:3; column-count:3;">
+===Petersen graph===
-* [[Logistic map]]
+[[image:Petersen graph blue.svg|thumb|The [[Petersen graph]]]]
-* [[Complex quadratic polynomial]]
+Consider the 3-regular graph ''G'' on 10 vertices (''n'' = 10, ''d'' = 3) shown.
-* [[Dyadic transformation]]
-* [[Tent map]]
-* [[Double pendulum]]
-* [[Arnold's cat map]]
-* [[Horseshoe map]]
-* [[Baker's map]] is an example of a chaotic [[piecewise linear function|piecewise linear]] map
-* [[Dynamical billiards|Billiards]] and [[Dynamical outer billiards|outer billiards]]
-* [[Hénon map]]
-* [[Lorenz attractor|Lorenz system]]
-* [[Circle map]]
-* [[Rössler map]]
-* [[Kaplan-Yorke map]]
-* [[List of chaotic maps]]
-* [[Swinging Atwood's machine]]
-* [[Quadratic Map Simulation System|Quadratic map simulation system]]
-* [[Bouncing ball dynamics]]
-</div>
-==Linear dynamical systems==
+If we number the vertices by going around twice, starting with the outside pentagon and then the inside pentagon, ''G'' has the following adjacency matrix:
-{{Main|Linear dynamical system}}
+<math>
+\begin{pmatrix}
+& 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\
+& 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
+& 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0\\
+& 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0\\
+& 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1\\
+& 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0\\
+& 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1\\
+& 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\
+& 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0\\
+& 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0\\
+\end{pmatrix}
+</math>
-Linear dynamical systems can be solved in terms of simple functions and the behavior of all orbits classified.  In a linear system the phase space is the ''N''-dimensional Euclidean space, so any point in phase space can be represented by a vector with ''N'' numbers.  The analysis of linear systems is possible because they satisfy a superposition principle: if ''u''(''t'') and ''w''(''t'') satisfy the differential equation for the vector field (but not necessarily the initial condition), then so will ''u''(''t'')&nbsp;+&nbsp;''w''(''t'').
+One can calculate that the two largest eigenvalues of this matrix are 3 and 1.  From this, one may deduce that
-===Flows===
+<math>\frac{d - \lambda_2}{2} = \frac{3 - 1}{2} = 1</math>
-For a [[flow (mathematics)|flow]], the vector field Φ(''x'') is a linear function of the position in the phase space, that is,
-:  <math> \phi(x) = A x + b,\,</math>
-with ''A'' a matrix, ''b'' a vector of numbers and ''x'' the position vector.  The solution to this system can be found by using the superposition principle (linearity).
-The case ''b''&nbsp;≠&nbsp;0 with ''A''&nbsp;=&nbsp;0 is just a straight line in the direction of&nbsp;''b'':
-: <math>\Phi^t(x_1) = x_1 + b t. \, </math>
+<math>\sqrt{2 d (d - \lambda_2)} = \sqrt{2 \cdot 3 (3 - 1)} = 2 \sqrt{3}</math>
+and consequently that <math>1 \leq h(G) \leq 2 \sqrt{3} \approx 3.46 </math>.
-When ''b'' is zero and ''A''&nbsp;≠&nbsp;0 the origin is an equilibrium (or singular) point of the flow, that is, if ''x''<sub>0</sub>&nbsp;=&nbsp;0, then the orbit remains there.
+In fact, <math>h(G) = 1</math>. To persuade oneself of this, it suffices to consider the five vertices in the central star: there are five edges that touch exactly one of these vertices, giving an edge expansion for this set of 5/5 = 1.
-For other initial conditions, the equation of motion is given by the [[matrix exponential|exponential of a matrix]]: for an initial point ''x''<sub>0</sub>,
-:  <math>\Phi^t(x_0) = e^{t A} x_0. \,</math>
+===Ramanujan graphs===
+By a theorem of Alon and Boppana, all large enough <math>d</math>-regular graphs satisfy <math>\lambda \ge 2\sqrt{d-1} - o(1)</math>.<ref>Theorem 2.7 of {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
+[[Ramanujan graph]]s are <math>d</math>-regular graphs that meet this bound, that is, they satisfy <math>\lambda \le 2\sqrt{d-1}</math>.<ref>Definition 5.11 of {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
+Hence Ramanujan graphs have an asymptotically smallest possible second-largest eigenvalue <math>\lambda</math> (in absolute value).
-When ''b'' = 0, the [[eigenvalue]]s of ''A'' determine the structure of the phase space.  From the eigenvalues and the [[eigenvector]]s of ''A'' it is possible to determine if an initial point will converge or diverge to the equilibrium point at the origin.
+[[Alexander Lubotzky|Lubotzky]], Phillips, and Sarnak (1988), Margulis (1988), and Morgenstern (1994) show how Ramanujan graphs can be constructed explicitly.<ref>Theorem 5.12 of {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
+By a theorem of Friedman (2003), [[Random regular graph|random d-regular graphs]] on <math>n</math> vertices are almost Ramanujan, that is, they satisfy <math>\lambda \le 2\sqrt{d-1}+\epsilon</math> with probability <math>1-o(1)</math> as <math>n</math> tends to infinity.<ref>Theorem 7.10 of {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
-The distance between two different initial conditions in the case ''A''&nbsp;≠&nbsp;0 will change exponentially in most cases, either converging exponentially fast towards a point, or diverging exponentially fast.  Linear systems display sensitive dependence on initial conditions in the case of divergence. For nonlinear systems this is one of the (necessary but not sufficient) conditions for [[chaos theory|chaotic behavior]].
+==Other examples==
+[[Abstract algebra|Algebraic]] constructions based on [[Cayley graph]]s are known for various variants of expander graphs.
+Most recently, combinatorial constructions of expanders have also been discovered.
-[[File:LinearFields.png|thumb|500px|center|Linear vector fields and a few trajectories.]]
+==Applications and useful properties==
-<br style="clear:both" />
+The original motivation for expanders is to build economical robust networks (phone or computer): an expander with bounded valence is precisely an asymptotic robust graph with number of edges growing linearly with size (number of vertices), for all subsets.
-===Maps===
+Expander graphs have found extensive applications in [[computer science]], in designing [[algorithm]]s, [[Expander code|error correcting codes]], [[Extractor (mathematics)|extractors]], [[pseudorandom generator]]s, [[sorting network]]s ({{harvtxt|Ajtai|Komlós|Szemerédi|1983}}) and robust [[computer network]]s. They have also been used in proofs of many important results in [[computational complexity theory]], such as [[SL (complexity)|SL]]=[[L (complexity)|L]] ({{harvtxt|Reingold|2008}}) and the [[PCP theorem]] ({{harvtxt|Dinur|2007}}). In [[cryptography]], expander graphs are used to construct [[hash function]]s.
-A [[Discrete-time dynamical system|discrete-time]], [[Affine transformation|affine]] dynamical system has the form
-: <math> x_{n+1} =  A x_n + b, \, </math>
-with ''A'' a matrix and ''b'' a vector.  As in the continuous case, the change of coordinates ''x''&nbsp;→&nbsp;''x''&nbsp;+&nbsp;(1&nbsp;−&nbsp;''A'')<sup>&nbsp;&ndash;1</sup>''b'' removes the term ''b'' from the equation.   In the new coordinate system, the origin is a fixed point of the map and the solutions are of the linear system ''A''<sup>&nbsp;''n''</sup>''x''<sub>0</sub>.
-The solutions for the map are no longer curves, but points that hop in the phase space.  The orbits are organized in curves, or fibers, which are collections of points that map into themselves under the action of the map.
-As in the continuous case, the eigenvalues and eigenvectors of ''A'' determine the structure of phase space.  For example, if ''u''<sub>1</sub> is an eigenvector of ''A'', with a real eigenvalue smaller than one, then the straight lines given by the points along ''α''&nbsp;''u''<sub>1</sub>, with ''α''&nbsp;∈&nbsp;'''R''', is an invariant curve of the map. Points in this straight line run into the fixed point.
+The following are some properties of expander graphs that have proven useful in many areas.
-There are also many [[List of chaotic maps|other discrete dynamical systems]].
+===Expander mixing lemma===
+{{Main|Expander mixing lemma}}
+The expander mixing lemma states that, for any two subsets of the vertices <math>S, T \subseteq V</math>, the number of edges between <math>S</math> and <math>T</math> is approximately what you would expect in a random <math>d</math>-regular graph. The approximation is better, the smaller <math>\lambda=\max\{|\lambda_2|,|\lambda_n|\}</math> is.
+In a random <math>d</math>-regular graph, as well as in an [[Erdős–Rényi model|Erdős–Rényi random graph]] with edge probability <math>d/n</math>, we expect <math>\frac{d}{n} \cdot |S| \cdot |T|</math> edges between <math>S</math> and <math>T</math>.
-==Local dynamics==
+More formally, let <math>E(S, T)</math> denote the number of edges between <math>S</math> and <math>T</math>.
-The qualitative properties of dynamical systems do not change under a smooth change of coordinates (this is sometimes taken as a definition of qualitative):   a ''singular point'' of the vector field (a point where&nbsp;''v''(''x'')&nbsp;=&nbsp;0) will remain a singular point under smooth transformations; a ''periodic orbit'' is a loop in phase space and smooth deformations of the phase space cannot alter it being a loop.  It is in the neighborhood of singular points and periodic orbits that the structure of a phase space of a dynamical system can be well understood.   In the qualitative study of dynamical systems, the approach is to show that there is a change of coordinates (usually unspecified, but computable) that makes the dynamical system as simple as possible.
+If the two sets are not disjoint, edges in their intersection are counted twice, that is,
+<math>E(S,T)=2|E(G[S\cap T])| + E(S\setminus T,T) + E(S,T\setminus S)</math>.
-===Rectification===
+Then the expander mixing lemma says that the following inequality holds:
-A flow in most small patches of the phase space can be made very simple.  If ''y'' is a point where the vector field ''v''(''y'')&nbsp;≠&nbsp;0, then there is a  change of coordinates for a region around ''y'' where the vector field becomes a series of parallel vectors of the same magnitude.  This is known as the rectification theorem.
+:<math>\left|E(S, T) - \frac{d \cdot |S| \cdot |T|}{n}\right| \leq d\lambda  \sqrt{|S| \cdot |T|}\,.</math>
+where <math>\lambda</math> is the absolute value of the '''normalized''' second largest eigenvalue.
-The rectification theorem says that away from singular points the dynamics of a point in a small patch is a straight line.  The patch can sometimes be enlarged by stitching several patches together, and when this works out in the whole phase space ''M'' the dynamical system is ''integrable''.  In most cases the patch cannot be extended to the entire phase space.  There may be singular points in the vector field (where ''v''(''x'')&nbsp;=&nbsp;0); or the patches may become smaller and smaller as some point is approached.   The more subtle reason is a global constraint, where the trajectory starts out in a patch, and after visiting a series of other patches comes back to the original one. If the next time the orbit loops around phase space in a different way, then it is impossible to rectify the vector field in the whole series of patches.
+===Expander walk sampling===
+{{Main|Expander walk sampling}}
+The [[Chernoff bound]] states that, when sampling many independent samples from a random variables in the range <math>[-1, 1]</math>, with high probability the average of our samples is close to the expectation of the random variable.  The expander walk sampling lemma, due to {{harvtxt|Ajtai|Komlós|Szemerédi|1987}} and {{harvtxt|Gillman|1998}}, states that this also holds true when sampling from a walk on an expander graph. This is particularly useful in the theory of [[derandomization]], since sampling according to an expander walk uses many fewer random bits than sampling independently.
-===Near periodic orbits===
+==See also==
-In general, in the neighborhood of a periodic orbit the rectification theorem cannot be used.  Poincaré developed an approach that transforms the analysis near a periodic orbit to the analysis of a map.   Pick a point ''x''<sub>0</sub> in the orbit γ and consider the points in phase space in that neighborhood that are perpendicular to ''v''(''x''<sub>0</sub>).  These points are a [[Poincaré section]]  ''S''(''γ'',&nbsp;''x''<sub>0</sub>), of the orbit.   The flow now defines a map, the [[Poincaré map]] ''F''&nbsp;:&nbsp;''S''&nbsp;→&nbsp;''S'', for points starting in ''S'' and returning to&nbsp;''S''.  Not all these points will take the same amount of time to come back, but the times will be close to the time it takes&nbsp;''x''<sub>0</sub>.
+*[[Algebraic connectivity]]
+*[[Zig-zag product]]
-The intersection of the periodic orbit with the Poincaré section is a fixed point of the Poincaré map ''F''. By a translation, the point can be assumed to be at ''x''&nbsp;=&nbsp;0. The Taylor series of the map is ''F''(''x'')&nbsp;=&nbsp;''J''&nbsp;·&nbsp;''x''&nbsp;+&nbsp;O(''x''<sup>2</sup>), so a change of coordinates ''h'' can only be expected to simplify ''F'' to its linear part
+==Notes==
+{{Reflist|colwidth=25em}}
-: <math> h^{-1} \circ F \circ h(x) = J \cdot x.\, </math>
-This is known as the conjugation equation.  Finding conditions for this equation to hold has been one of the major tasks of research in dynamical systems.  Poincaré first approached it assuming all functions to be analytic and in the process discovered the non-resonant condition.  If ''λ''<sub>1</sub>,&nbsp;...,&nbsp;''λ''<sub>''ν''</sub> are the eigenvalues of ''J'' they will be resonant if one eigenvalue is an integer linear combination of two or more of the others.  As terms of the form ''λ''<sub>''i''</sub> &ndash; ∑ (multiples of other eigenvalues) occurs in the denominator of the terms for the function ''h'', the non-resonant condition is also known as the small divisor problem.
-===Conjugation results===
-The results on the existence of a solution to the conjugation equation depend on the eigenvalues of ''J'' and the degree of smoothness required from ''h''.  As ''J'' does not need to have any special symmetries, its eigenvalues will typically be complex numbers.  When the eigenvalues of ''J'' are not in the unit circle, the dynamics near the fixed point ''x''<sub>0</sub> of ''F'' is called ''[[Hyperbolic fixed point|hyperbolic]]'' and when the eigenvalues are on the unit circle and complex, the dynamics is called ''elliptic''.
-In the hyperbolic case the [[Hartman–Grobman theorem]] gives the conditions for the existence of a continuous function that maps the neighborhood of the fixed point of the map to the linear map ''J''&nbsp;·&nbsp;''x''.   The hyperbolic case is also ''structurally stable''.  Small changes in the vector field will only produce small changes in the Poincaré map and these small changes will reflect in small changes in the position of the eigenvalues of ''J'' in the complex plane, implying that the map is still hyperbolic.
-The [[Kolmogorov–Arnold–Moser theorem|Kolmogorov–Arnold–Moser (KAM)]] theorem gives the behavior near an elliptic point.
-==Bifurcation theory==
-{{Main|Bifurcation theory}}
-When the evolution map Φ<sup>''t''</sup> (or the [[vector field]] it is derived from) depends on a parameter μ, the structure of the phase space will also depend on this parameter.   Small changes may produce no qualitative changes in the [[phase space]] until a special value ''μ''<sub>0</sub> is reached.  At this point the phase space changes qualitatively and the dynamical system is said to have gone through a bifurcation.
-Bifurcation theory considers a structure in phase space (typically a [[Fixed point (mathematics)|fixed point]], a periodic orbit, or an invariant [[torus]]) and studies its behavior as a function of the parameter&nbsp;''μ''.   At the bifurcation point the structure may change its stability, split into new structures, or merge with other structures.  By using Taylor series approximations of the maps and an understanding of the differences that may be eliminated by a change of coordinates, it is possible to catalog the bifurcations of dynamical systems.
-The bifurcations of a hyperbolic fixed point ''x''<sub>0</sub> of a system family ''F<sub>μ</sub>'' can be characterized by the [[eigenvalues]] of the first derivative of the system ''DF''<sub>''μ''</sub>(''x''<sub>0</sub>) computed at the bifurcation point. For a map, the bifurcation will occur when there are eigenvalues of ''DF<sub>μ</sub>'' on the unit circle. For a flow, it will occur when there are eigenvalues on the imaginary axis. For more information, see the main article on [[Bifurcation theory]].
-Some bifurcations can lead to very complicated structures in phase space. For example, the [[Ruelle&ndash;Takens scenario]] describes how a periodic orbit bifurcates into a torus and the torus into a [[strange attractor]]. In another example, [[Bifurcation diagram|Feigenbaum period-doubling]] describes how a stable periodic orbit goes through a series of [[period-doubling bifurcation]]s.
-==Ergodic systems==
-{{Main|Ergodic theory}}
-In many dynamical systems it is possible to choose the coordinates of the system so that the volume (really a ν-dimensional volume) in phase space is invariant.  This happens for mechanical systems derived from Newton's laws as long as the coordinates are the position and the momentum and the volume is measured in units of (position)&nbsp;×&nbsp;(momentum).  The flow takes points of a subset ''A'' into the points Φ<sup>&nbsp;''t''</sub>(''A'') and invariance of the phase space means that
-: <math> \mathrm{vol} (A) = \mathrm{vol} ( \Phi^t(A) ). \, </math>
-In the [[Hamiltonian mechanics|Hamiltonian formalism]], given a coordinate it is possible to derive the appropriate (generalized) momentum such that the associated volume is preserved by the flow.  The volume is said to be computed by the [[Liouville's theorem (Hamiltonian)|Liouville measure]].
-In a Hamiltonian system not all possible configurations of position and momentum  can be reached from an initial condition. Because of energy conservation, only the states with the same energy as the initial condition are accessible.  The states with the same energy form an energy shell Ω, a sub-manifold of the phase space. The volume of the energy shell, computed using the Liouville measure, is preserved under evolution.
-For systems where the volume is preserved by the flow, Poincaré discovered the [[Poincaré recurrence theorem|recurrence theorem]]: Assume the phase space has a finite Liouville volume and let ''F'' be a phase space volume-preserving map and ''A'' a subset of the phase space.  Then almost every point of ''A'' returns to ''A'' infinitely often.  The Poincaré recurrence theorem was used by [[Zermelo]] to object to [[Boltzmann]]'s   derivation of the increase in entropy in a dynamical system of colliding atoms.
-One of the questions raised by Boltzmann's work was the possible equality between time averages and space averages, what he called the [[ergodic hypothesis]].  The hypothesis states that the length of time a typical trajectory spends in a region ''A'' is vol(''A'')/vol(Ω).
-The ergodic hypothesis turned out not to be the essential property needed for the development of [[statistical mechanics]] and a series of other ergodic-like properties were introduced to capture the relevant aspects of physical systems.  [[Bernard Koopman|Koopman]] approached the study of ergodic systems by the use of [[functional analysis]].  An observable ''a'' is a function that to each point of the phase space associates a number (say instantaneous pressure, or average height).  The value of an observable can be computed at another time by using the evolution function φ<sup>&nbsp;t</sup>.  This introduces an operator ''U''<sup>&nbsp;''t''</sup>, the [[transfer operator]],
-: <math> (U^t a)(x) = a(\Phi^{-t}(x)). \, </math>
-By studying the spectral properties of the linear operator ''U'' it becomes possible to classify the ergodic properties of&nbsp;Φ<sup>&nbsp;''t''</sup>.  In using the Koopman approach of considering the action of the flow on an observable function, the finite-dimensional nonlinear problem involving Φ<sup>&nbsp;''t''</sup> gets mapped into an infinite-dimensional linear problem involving&nbsp;''U''.
-The Liouville measure restricted to the energy surface Ω is the basis for the averages computed in [[Statistical mechanics|equilibrium statistical mechanics]].  An average in time along a trajectory is equivalent to an average in space computed with the  [[Statistical mechanics#Canonical ensemble|Boltzmann factor exp(&minus;β''H'')]].  This idea has been generalized by Sinai, Bowen, and Ruelle (SRB) to a larger class of dynamical systems that includes dissipative systems. [[SRB measure]]s replace the Boltzmann factor and they are defined on attractors of chaotic systems.
-===Nonlinear dynamical systems and chaos===
-{{Main|Chaos theory}}
-Simple nonlinear dynamical systems and even piecewise linear systems can exhibit a completely unpredictable behavior, which might seem to be random, despite the fact that they are fundamentally deterministic. This seemingly unpredictable behavior has been called ''[[chaos theory|chaos]]''.   [[Anosov diffeomorphism|Hyperbolic systems]] are precisely defined dynamical systems that exhibit the properties ascribed to chaotic systems.  In hyperbolic systems the tangent space perpendicular to a trajectory can be well separated into two parts: one with the points that converge towards the orbit (the ''stable manifold'') and another of the points that diverge from the orbit (the ''unstable manifold'').
-This branch of [[mathematics]] deals with the long-term qualitative behavior of dynamical systems. Here, the focus is not on finding precise solutions to the equations defining the dynamical system (which is often hopeless), but rather to answer questions like "Will the system settle down to a steady state in the long term, and if so, what are the possible [[attractor]]s?" or "Does the long-term behavior of the system depend on its initial condition?"
-Note that the chaotic behavior of complex systems is not the issue. [[Meteorology]] has been known for years to involve complex&mdash;even chaotic&mdash;behavior. Chaos theory has been so surprising because chaos can be found within almost trivial systems. The [[logistic map]] is only a second-degree polynomial; the [[horseshoe map]] is piecewise linear.
-=== Geometrical definition ===
-A dynamical system is the tuple <math> \langle \mathcal{M}, f , \mathcal{T}\rangle </math>, with <math>\mathcal{M}</math> a manifold (locally a Banach space or Euclidean space), <math>\mathcal{T}</math> the domain for time (non-negative reals, the integers, ...) and ''f'' an evolution rule ''t''&nbsp;→&nbsp;''f''<sup>&nbsp;''t''</sup> (with <math>t\in\mathcal{T}</math>) such that ''f<sup>&nbsp;t</sup>'' is a [[diffeomorphism]] of the manifold to itself. So, f is a mapping of the time-domain <math> \mathcal{T}</math> into the space of diffeomorphisms of the manifold to itself. In other terms, ''f''(''t'') is a diffeomorphism, for every time ''t'' in the domain <math> \mathcal{T}</math> .
-=== Measure theoretical definition ===
-:''See main article [[Measure-preserving dynamical system]].''
-A dynamical system may be defined formally, as a measure-preserving transformation of a [[sigma-algebra]], the quadruplet (''X'', Σ, μ, τ). Here, ''X'' is a [[set (mathematics)|set]], and Σ is a [[sigma-algebra]] on ''X'', so that the pair (''X'', Σ) is a measurable space. μ is a finite [[measure (mathematics)|measure]] on the sigma-algebra, so that the triplet (''X'', Σ, μ) is a [[measure space|probability space]]. A map τ: ''X'' → ''X'' is said to be [[measurable function|Σ-measurable]] if and only if, for every σ ∈ Σ, one has <math>\tau^{-1}\sigma \in \Sigma</math>. A map τ is said to '''preserve the measure''' if and only if, for every σ ∈ Σ, one has <math>\mu(\tau^{-1}\sigma ) = \mu(\sigma)</math>. Combining the above, a map τ is said to be a '''measure-preserving transformation of ''X'' ''', if it is a map from ''X'' to itself, it is Σ-measurable, and is measure-preserving. The quadruple (''X'', Σ, μ, τ), for such a τ, is then defined to be a '''dynamical system'''.
-The map τ embodies the time evolution of the dynamical system. Thus, for discrete dynamical systems the [[iterated function|iterates]] <math>\tau^n=\tau \circ \tau \circ \ldots\circ\tau</math> for integer ''n'' are studied. For continuous dynamical systems, the map τ is understood to be a finite time evolution map and the construction is more complicated.
-== Examples of dynamical systems ==
-===Internal links===
-* [[Arnold's cat map]]
-* [[Baker's map]] is an example of a chaotic piecewise linear map
-* [[Circle map]]
-* [[Double pendulum]]
-* [[Dynamical billiards|Billiards]] and [[Dynamical outer billiards|Outer Billiards]]
-* [[Hénon map]]
-* [[Horseshoe map]]
-* [[Irrational rotation]]
-* [[List of chaotic maps]]
-* [[Logistic map]]
-* [[Lorenz attractor|Lorenz system]]
-* [[Rossler map]]
-===External links===
-* [http://complexity.xozzox.de/nonlinmappings.html Interactive applet for the Standard and Henon Maps] by A. Luhn
-== Multidimensional generalization ==
-Dynamical systems are defined over a single independent variable, usually thought of as time. A more general class of systems are defined over multiple independent variables and are therefore called [[multidimensional systems]]. Such systems are useful for modeling, for example, [[image processing]].
-== See also ==
-{{Portal|Systems science}}
-* [[Behavioral modeling]]
-* [[Cognitive model#Dynamical Systems | Cognitive modeling]]
-* [[Dynamical systems theory]]
-* [[Feedback passivation]]
-* [[List of dynamical system topics]]
-* [[Oscillation]]
-* [[People in systems and control]]
-* [[Sharkovskii's theorem]]
-* [[System dynamics]]
-* [[Systems theory]]
-* [[Infinite compositions of analytic functions]]
 ==References==
-<references />
+{{Refbegin|colwidth=25em}}
-{{Refimprove|date=October 2007}}
+'''Textbooks and surveys'''
+* {{cite book|title=The Probabilistic Method|first1=N.|last1=Alon|author1-link=Noga Alon|first2=Joel H.|last2=Spencer|author2-link=Joel Spencer|publisher=John Wiley & Sons|year=2011|edition=3rd|chapter=9.2. Eigenvalues and Expanders|ref=harv}}
-== Further reading ==
+* {{Citation | last=Chung |first=Fan R. K. | title=Spectral Graph Theory | series=CBMS Regional Conference Series in Mathematics | volume=92 | publisher=[[American Mathematical Society]] | year=1997 | isbn=0-8218-0315-8}}
-Works providing a broad coverage:
+* {{Citation | first1=Guiliana |last1=Davidoff | first2=Peter | last2=Sarnak | first3=Alain | last3=Valette | title=Elementary number theory, group theory and Ramanjuan graphs | publisher=[[Cambridge University Press]] | series=LMS student texts | volume=55 | year=2003 | isbn=0-521-53143-8}}
-* {{cite book | author=[[Ralph Abraham]] and [[Jerrold E. Marsden]] | title= Foundations of mechanics | publisher= Benjamin–Cummings | year= 1978 | isbn=0-8053-0102-X}}  (available as a reprint: ISBN 0-201-40840-6)
+* {{Citation | first1=Shlomo | last1=Hoory | first2=Nathan | last2=Linial | author2-link = Nati Linial | first3=Avi | last3=Widgerson | author3-link = Avi Wigderson | title=Expander graphs and their applications | journal= Bulletin (New series) of the American Mathematical Society | volume=43 | issue=4 | pages=439–561 | url=http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf | year=2006 | doi = 10.1090/S0273-0979-06-01126-8}}
-* ''Encyclopaedia of Mathematical Sciences'' (ISSN 0938-0396) has a sub-series on dynamical systems with reviews of current research.
+* {{Citation | first1=Mike |last1=Krebs | first2=Anthony | last2=Shaheen | title=Expander families and Cayley graphs: A beginner's guide | publisher=Oxford University Press | year=2011 | isbn=0-19-976711-4}}
-* {{cite book | author=Christian Bonatti,  Lorenzo J. Díaz, Marcelo  Viana | title= Dynamics Beyond Uniform Hyperbolicity: A Global Geometric and Probabilistic Perspective| publisher= Springer | year= 2005 | isbn=3-540-22066-6}}
+'''Research articles'''
-* {{cite journal | doi=10.1090/S0002-9904-1967-11798-1 | author=[[Stephen Smale]] | title= Differentiable dynamical systems | journal= Bulletin of the American Mathematical Society | year= 1967 |volume= 73 |pages= 747–817 | issue=6}}
+* {{Citation|last1=Ajtai|first1=M.|author1-link=Miklós Ajtai|last2=Komlós|first2=J.|author2-link=János Komlós (mathematician)|last3=Szemerédi|first3=E.|author3-link=Endre Szemerédi|chapter=An O(n log n) sorting network|title=Proceedings of the 15th Annual ACM Symposium on Theory of Computing|pages=1–9|year=1983|doi=10.1145/800061.808726|isbn=0-89791-099-0}}
+* {{Citation
-Introductory texts with a unique perspective:
+ | first1=M. | last1=Ajtai
-* {{cite book | author=[[Vladimir Arnold|V. I. Arnold]] | title=Mathematical methods of classical mechanics | publisher=Springer-Verlag | year=1982 | isbn=0-387-96890-3}}
+ | first2=J. | last2=Komlós
-* {{cite book | author=[[Jacob Palis]] and Wellington de Melo | title=Geometric theory of dynamical systems: an introduction | publisher=Springer-Verlag | year=1982 | isbn=0-387-90668-1}}
+ | first3=E. | last3=Szemerédi
-* {{cite book | author=[[David Ruelle]] | title=Elements of Differentiable Dynamics and Bifurcation Theory | publisher=Academic Press | year=1989 | isbn=0-12-601710-7}}
+ | chapter=Deterministic simulation in LOGSPACE
-* {{cite book | author=Tim Bedford, Michael Keane and Caroline Series, ''eds.'' | title= Ergodic theory, symbolic dynamics and hyperbolic spaces | publisher= Oxford University Press | year= 1991 | isbn= 0-19-853390-X }}
+ | title=Proceedings of the 19th Annual ACM Symposium on Theory of Computing
-* {{cite book | author= [[Ralph Abraham|Ralph H. Abraham]] and [[Robert Shaw (Physicist)#Illustrations|Christopher D. Shaw]] | title= Dynamics&mdash;the geometry of behavior, 2nd edition | publisher= Addison-Wesley | year= 1992 | isbn= 0-201-56716-4 }}
+ | pages=132–140
+ | year=1987
-Textbooks
+ | work=ACM
-* {{cite book | author= Kathleen T. Alligood, Tim D. Sauer and [[James A. Yorke]] | title= Chaos.  An introduction to dynamical systems | publisher= Springer Verlag | year= 2000 | isbn=0-387-94677-2}}
+ | doi=10.1145/28395.28410
-* {{cite book | author= Oded Galor | title= ''Discrete Dynamical Systems'' | publisher= Springer | year= 2011 | isbn=978-3-642-07185-0}}
+ | isbn=0-89791-221-7
-* {{cite book | author= Anatole Katok and Boris Hasselblatt | title= Introduction to the modern theory of dynamical systems | publisher= Cambridge | year= 1996 | isbn=0-521-57557-5}}
+}}
-* {{cite book | author= Stephen Lynch | title= Dynamical Systems with Applications using Maple 2nd Ed.| publisher= Springer | year= 2010|isbn = 0-8176-4389-3 }}
+* {{cite doi|10.1109/SFCS.2002.1181884}}
-* {{cite book | author= Stephen Lynch | title= Dynamical Systems with Applications using Mathematica| publisher= Springer | year= 2007|isbn = 0-8176-4482-2 }}
+* {{Citation
-* {{cite book | author= Stephen Lynch | title= Dynamical Systems with Applications using MATLAB | publisher= Springer | year= 2004|isbn = 0-8176-4321-4 }}
+    |last1=Bobkov|first1=S.
-* {{cite book | author= James Meiss | title= Differential Dynamical Systems | publisher= SIAM | year= 2007|isbn = 0-89871-635-7 }}
+    |last2=Houdré|first2=C.
-* {{cite book | author= Morris W. Hirsch, [[Stephen Smale]] and Robert Devaney | title= Differential Equations, dynamical systems, and an introduction to chaos | publisher= Academic Press | year= 2003 | isbn=0-12-349703-5}}
+    |last3=Tetali|first3=P.
-* {{cite book | author= Julien Clinton Sprott | title= ''Chaos and time-series analysis'' | publisher= Oxford University Press | year= 2003 | isbn=0-19-850839-5}}
+    |title=λ<sub>∞</sub>, vertex isoperimetry and concentration|journal=Combinatorica|volume=20|issue=2|year=2000|doi=10.1007/s004930070018|pages = {153–172}}}.
-* {{cite book | author=[[Steven Strogatz|Steven H. Strogatz]] | title= Nonlinear dynamics and chaos: with applications to physics, biology chemistry and engineering | publisher= Addison Wesley | year= 1994|isbn = 0-201-54344-3 }}
+* {{Citation|last=Dinur|first=Irit|title=The PCP theorem by gap amplification|journal=Journal of the ACM|volume=54|issue=3|year=2007|doi=10.1145/1236457.1236459|pages=12}}.
-* {{cite book| last = Teschl| given = Gerald|authorlink=Gerald Teschl| title = Ordinary Differential Equations and Dynamical Systems| publisher=[[American Mathematical Society]]| place = [[Providence, Rhode Island|Providence]]| year = 2012| isbn= 978-0-8218-8328-0| url = http://www.mat.univie.ac.at/~gerald/ftp/book-ode/}}
+* {{Citation
+ | first=D. | last=Gillman
-Popularizations:
+ | title=A Chernoff Bound for Random Walks on Expander Graphs
-* {{cite book | author=[[Florin Diacu]] and [[Philip Holmes]] | title= Celestial Encounters | publisher= Princeton | year= 1996 | isbn= 0-691-02743-9}}
+ | journal=SIAM Journal on Computing
-* {{cite book | author=[[James Gleick]] | title= Chaos: Making a New Science | publisher= Penguin | year= 1988 | isbn= 0-14-009250-1}}
+ | volume=27
-* {{cite book | authorlink=Ivar Ekeland | author=Ivar Ekeland | title= Mathematics and the Unexpected (Paperback) | publisher= University Of Chicago Press | year= 1990 | isbn= 0-226-19990-8}}
+ | issue=4,
-* {{cite book | author=Ian Stewart | year = 1997 | title = Does God Play Dice? The New Mathematics of Chaos | publisher = Penguin | isbn = 0-14-025602-4}}
+ | pages=1203–1220
+  | year=1998
-==External links==
+  | publisher=Society for Industrial and Applied Mathematics
-* [http://vlab.infotech.monash.edu.au/simulations/non-linear/ A collection of dynamic and non-linear system models and demo applets] (in Monash University's Virtual Lab)
+  | doi=10.1137/S0097539794268765
-* [http://www.arxiv.org/list/math.DS/recent Arxiv preprint server]  has daily submissions of (non-refereed) manuscripts in dynamical systems.
+}}
-* [http://www.dynamicalsystems.org/ DSWeb] provides up-to-date information on dynamical systems and its applications.
+* {{Citation|first=Omer|last=Reingold|authorlink=Omer Reingold|title=Undirected connectivity in log-space|journal=[[Journal of the ACM]]|year=2008|
-* [http://www.scholarpedia.org/article/Encyclopedia_of_Dynamical_Systems Encyclopedia of dynamical systems] A part of [[Scholarpedia]] — peer reviewed and written by invited experts.
+volume=55|issue=4|pages=Article 17, 24 pages|doi=10.1145/1391289.1391291
-* [http://www.egwald.ca/nonlineardynamics/index.php Nonlinear Dynamics]. Models of bifurcation and chaos by Elmer G. Wiens
+}}
-* [http://www.dynamical-systems.org Oliver Knill] has a series of examples of dynamical systems with explanations and interactive controls.
+{{Refend}}
-* [http://amath.colorado.edu/faculty/jdm/faq-Contents.html  Sci.Nonlinear FAQ 2.0 (Sept 2003)] provides definitions, explanations and resources related to nonlinear science
-Online books or lecture notes:
-* [http://arxiv.org/pdf/math.HO/0111177 Geometrical theory of dynamical systems]. Nils Berglund's lecture notes for a course at [[ETH]] at the advanced undergraduate level.
-* [http://www.ams.org/online_bks/coll9/ Dynamical systems]. George D. Birkhoff's 1927 book already takes a modern approach to dynamical systems.
-* [http://chaosbook.org  Chaos: classical and quantum]. An introduction to dynamical systems from the periodic orbit point of view.
-* [http://www.embedded.com/2000/0008/0008feat2.htm Modeling Dynamic Systems]. An introduction to the development of mathematical models of dynamic systems.
-* [http://www.cs.brown.edu/research/ai/dynamics/tutorial/home.html Learning Dynamical Systems]. Tutorial on learning dynamical systems.
-* [http://www.mat.univie.ac.at/~gerald/ftp/book-ode/ Ordinary Differential Equations and Dynamical Systems]. Lecture notes by [[Gerald Teschl]]
-Research groups:
-* [http://www.math.rug.nl/~broer/ Dynamical Systems Group Groningen], IWI, University of Groningen.
-* [http://www-chaos.umd.edu/ Chaos @ UMD]. Concentrates on the applications of dynamical systems.
-* [http://www.math.sunysb.edu/dynamics/ Dynamical Systems], SUNY Stony Brook.  Lists of conferences, researchers, and some open problems.
-* [http://www.math.psu.edu/dynsys/ Center for Dynamics and Geometry], Penn State.
-* [http://www.cds.caltech.edu/ Control and Dynamical Systems], Caltech.
-* [http://lanoswww.epfl.ch/ Laboratory of Nonlinear Systems], Ecole Polytechnique Fédérale de Lausanne (EPFL).
-* [http://www.math.uni-bremen.de/ids.html/ Center for Dynamical Systems], University of Bremen
-* [http://www.eng.ox.ac.uk/samp/ Systems Analysis, Modelling and Prediction Group], University of Oxford
-* [http://sd.ist.utl.pt/ Non-Linear Dynamics Group], Instituto Superior Técnico, Technical University of Lisbon
-* [http://www.impa.br/ Dynamical Systems], IMPA, Instituto Nacional de Matemática Pura e Applicada.
-* [http://ndw.cs.cas.cz/ Nonlinear Dynamics Workgroup], Institute of Computer Science, Czech Academy of Sciences.
-Simulation software based on Dynamical Systems approach:
-* [http://fydik.kitnarf.cz/ FyDiK]
-* [http://idmc.googlecode.com iDMC], simulation and dynamical analysis of nonlinear models
-{{Systems}}
+== External links ==
+* [http://www.ams.org/notices/200407/what-is.pdf Brief introduction in Notices of the American Mathematical Society]
+* [http://michaelnielsen.org/blog/archive/notes/expander_graphs.pdf Introductory paper by Michael Nielsen]
+* [http://www.math.ias.edu/~boaz/ExpanderCourse/ Lecture notes from a course on expanders (by Nati Linial and Avi Wigderson)]
+* [http://ttic.uchicago.edu/~prahladh/teaching/spring05/index.html Lecture notes from a course on expanders (by Prahladh Harsha)]
+*[http://www.yann-ollivier.org/specgraph/specgraph.html Definition and application of spectral gap]
-{{DEFAULTSORT:Dynamical System}}
+{{DEFAULTSORT:Expander Graph}}
-[[Category:Dynamical systems| ]]
+[[Category:Graph families]]
-[[Category:Systems theory]]
-[[Category:Systems]]
-[[ar:نظام تحريكي]]
+[[cs:Expander (graf)]]
-[[de:Dynamisches System]]
+[[fr:Graphe expanseur]]
-[[es:Sistema dinámico]]
+[[he:גרף מרחיב]]
-[[fa:سیستم دینامیک]]
+[[pl:Ekspander]]
-[[fr:Système dynamique]]
-[[ko:동역학계]]
-[[hi:गतिकीय तन्त्र]]
-[[io:Dinamikala sistemo]]
-[[it:Sistema dinamico (fisica matematica)]]
-[[he:מערכת דינמית]]
-[[lt:Dinaminė sistema]]
-[[hu:Dinamikai rendszer]]
-[[mk:Динамичен систем]]
-[[nl:Dynamisch systeem]]
-[[ja:力学系]]
-[[pl:Układ dynamiczny]]
-[[pt:Sistemas dinâmicos]]
-[[ru:Динамическая система]]
-[[sl:Dinamični sistem]]
-[[fi:Dynaaminen systeemi]]
-[[sv:Dynamiskt system]]
-[[uk:Динамічна система]]
-[[vi:Hệ thống động lực]]
-[[zh:动力系统]]

Main Page: Difference between revisions

Revision as of 13:09, 8 August 2014

Definitions

Edge expansion

Vertex expansion

Spectral expansion

Relationships between different expansion properties

Cheeger inequalities

Examples of expanders

Petersen graph

Ramanujan graphs

Other examples

Applications and useful properties

Expander mixing lemma

Expander walk sampling

See also

Notes

References

External links

Navigation menu

Search