text:
Endocrine system

The endocrine system is a messenger system in an organism comprising feedback loops of hormones that are released by internal glands directly into the circulatory system and that target and regulate distant organs. In vertebrates, the hypothalamus is the neural control center for all endocrine systems.

In humans, the major endocrine glands are the thyroid, parathyroid, pituitary, pineal, and adrenal glands, and the (male) testus and (female) ovaries. The hypothalamus, pancreas, and thymus also function as endocrine glands, among other functions. (The hypothalamus and pituitary glands are organs of the neuroendocrine system. One of the most important functions of the hypothalamus—it is located in the brain adjacent to the pituitary gland—is to link the endocrine system to the nervous system via the pituitary gland.) Other organs, such as the kidneys, also have roles within the endocrine system by secreting certain hormones. The study of the endocrine system and its disorders is known as endocrinology. The thyroid secretes thyroxine, the pituitary secretes growth hormone, the pineal secretes melatonin, the testus secretes testosterone, and the ovaries secretes oestrogen and protestogen.

Glands that signal each other in sequence are often referred to as an axis, such as the hypothalamic–pituitary–adrenal axis. In addition to the specialized endocrine organs mentioned above, many other organs that are part of other body systems have secondary endocrine functions, including bone, kidneys, liver, heart and gonads. For example, the kidney secretes the endocrine hormone erythropoietin. Hormones can be amino acid complexes, steroids, eicosanoids, leukotrienes, or prostaglandins.

The endocrine system is contrasted both to exocrine glands, which secrete hormones to the outside of the body, and to the system known as paracrine signalling between cells over a relatively short distance. Endocrine glands have no ducts, are vascular, and commonly have intracellular vacuoles or granules that store their hormones. In contrast, exocrine glands, such as salivary glands, mammary glands, and submucosal glands within the gastrointestinal tract, tend to be much less vascular and have ducts or a hollow lumen. Endocrinology is a branch of internal medicine.

Major endocrine systems
The human endocrine system consists of several systems that operate via feedback loops. Several important feedback systems are mediated via the hypothalamus and pituitary.
 * TRH – TSH – T3/T4
 * GnRH – LH/FSH – sex hormones
 * CRH – ACTH – cortisol
 * Renin – angiotensin – aldosterone
 * Leptin vs. ghrelin

Glands
Endocrine glands are such type of glands that secrete their products, hormones, directly into interstitial spaces where they are absorbed into blood rather than through a duct. The major glands of the endocrine system include the pineal gland, pituitary gland, pancreas, ovaries, testes, thyroid gland, parathyroid gland, hypothalamus and adrenal glands. The hypothalamus and pituitary gland are neuroendocrine organs.

The hypothalamus and the anterior pituitary are two out of the three endocrine glands that are important in cell signaling. They are both part of the HPA axis which is known to play a role in cell signaling in the nervous system.

Hypothalamus: The hypothalamus is a key regulator of the autonomic nervous system. The endocrine system has three sets of endocrine outputs which include the magnocellular system, the parvocellular system, and autonomic intervention. The magnocellular is involved in the expression of oxytocin or vasopressin. The parvocellular is involved in controlling the secretion of hormones from the anterior pituitary.

Anterior Pituitary: The main role of the anterior pituitary gland is to produce and secrete tropic hormones. Some examples of tropic hormones secreted by the anterior pituitary gland include TSH, ACTH, GH, LH, and FSH.

Cells
There are many types of cells that make up the endocrine system and these cells typically make up larger tissues and organs that function within and outside of the endocrine system.
 * Hypothalamus
 * Anterior pituitary gland
 * Pineal gland
 * Posterior pituitary gland
 * The posterior pituitary gland is a section of the pituitary gland. This organ does not produce any hormone but stores and secretes hormones such as antidiuretic hormone (ADH) which is synthesized by supraoptic nucleus of hypothalamus and oxytocin which is synthesized by paraventricular nucleus of hypothalamus. ADH functions to help the body to retain water; this is important in maintaining a homeostatic balance between blood solutions and water. Oxytocin functions to induce uterine contractions, stimulate lactation, and allows for ejaculation.
 * Thyroid gland
 * follicular cells of the thyroid gland produce and secrete T3 and T4 in response to elevated levels of TRH, produced by the hypothalamus, and subsequent elevated levels of TSH, produced by the anterior pituitary gland, which further regulates the metabolic activity and rate of all cells, including cell growth and tissue differentiation.
 * Parathyroid gland The endocrine system can control all emotions and can control temperature.
 * Epithelial cells of the parathyroid glands are richly supplied with blood from the inferior and superior thyroid arteries and secrete parathyroid hormone (PTH). PTH acts on bone, the kidneys, and the GI tract to increase calcium reabsorption and phosphate excretion. In addition, PTH stimulates the conversion of Vitamin D to its most active variant, 1,25-dihydroxyvitamin D3, which further stimulates calcium absorption in the GI tract.
 * Thymus Gland
 * Adrenal glands
 * Adrenal cortex
 * Adrenal medulla
 * Pancreas
 * Pancreas contain nearly 1 to 2 million islets of Langerhans (a tissue which consists cells that secrete hormones) and acini. Acini secretes digestive enzymes.
 * Alpha cells
 * The alpha cells of the pancreas secrete hormones to maintain homeostatic blood sugar. Insulin is produced and excreted to lower blood sugar to normal levels. Glucagon, another hormone produced by alpha cells, is secreted in response to low blood sugar levels; glucagon stimulates glycogen stores in the liver to release sugar into the bloodstream to raise blood sugar to normal levels.
 * Beta cells
 * 60% of the cells present in islet of Langerhans are beta cells. Beta cells secrete insulin. Along with glucagon, insulin helps in maintaining glucose levels in our body. Insulin decreases blood glucose level ( a hypoglycemic hormone) whereas glucagon increases blood glucose level.
 * Delta cells
 * F Cells
 * Ovaries
 * Granulosa cells
 * Testis
 * Leydig cells

Development
The fetal endocrine system is one of the first systems to develop during prenatal development.

Adrenal glands
The fetal adrenal cortex can be identified within four weeks of gestation. The adrenal cortex originates from the thickening of the intermediate mesoderm. At five to six weeks of gestation, the mesonephros differentiates into a tissue known as the genital ridge. The genital ridge produces the steroidogenic cells for both the gonads and the adrenal cortex. The adrenal medulla is derived from ectodermal cells. Cells that will become adrenal tissue move retroperitoneally to the upper portion of the mesonephros. At seven weeks of gestation, the adrenal cells are joined by sympathetic cells that originate from the neural crest to form the adrenal medulla. At the end of the eighth week, the adrenal glands have been encapsulated and have formed a distinct organ above the developing kidneys. At birth, the adrenal glands weigh approximately eight to nine grams (twice that of the adult adrenal glands) and are 0.5% of the total body weight. At 25 weeks, the adult adrenal cortex zone develops and is responsible for the primary synthesis of steroids during the early postnatal weeks.

Thyroid gland
The thyroid gland develops from two different clusterings of embryonic cells. One part is from the thickening of the pharyngeal floor, which serves as the precursor of the thyroxine (T4) producing follicular cells. The other part is from the caudal extensions of the fourth pharyngobranchial pouches which results in the parafollicular calcitonin-secreting cells. These two structures are apparent by 16 to 17 days of gestation. Around the 24th day of gestation, the foramen cecum, a thin, flask-like diverticulum of the median anlage develops. At approximately 24 to 32 days of gestation the median anlage develops into a bilobed structure. By 50 days of gestation, the medial and lateral anlage have fused together. At 12 weeks of gestation, the fetal thyroid is capable of storing iodine for the production of TRH, TSH, and free thyroid hormone. At 20 weeks, the fetus is able to implement feedback mechanisms for the production of thyroid hormones. During fetal development, T4 is the major thyroid hormone being produced while triiodothyronine (T3) and its inactive derivative, reverse T3, are not detected until the third trimester.

Parathyroid glands
A lateral and ventral view of an embryo showing the third (inferior) and fourth (superior) parathyroid glands during the 6th week of embryogenesis

Once the embryo reaches four weeks of gestation, the parathyroid glands begins to develop. The human embryo forms five sets of endoderm-lined pharyngeal pouches. The third and fourth pouch are responsible for developing into the inferior and superior parathyroid glands, respectively. The third pharyngeal pouch encounters the developing thyroid gland and they migrate down to the lower poles of the thyroid lobes. The fourth pharyngeal pouch later encounters the developing thyroid gland and migrates to the upper poles of the thyroid lobes. At 14 weeks of gestation, the parathyroid glands begin to enlarge from 0.1 mm in diameter to approximately 1 – 2 mm at birth. The developing parathyroid glands are physiologically functional beginning in the second trimester.

Studies in mice have shown that interfering with the HOX15 gene can cause parathyroid gland aplasia, which suggests the gene plays an important role in the development of the parathyroid gland. The genes, TBX1, CRKL, GATA3, GCM2, and SOX3 have also been shown to play a crucial role in the formation of the parathyroid gland. Mutations in TBX1 and CRKL genes are correlated with DiGeorge syndrome, while mutations in GATA3 have also resulted in a DiGeorge-like syndrome. Malformations in the GCM2 gene have resulted in hypoparathyroidism. Studies on SOX3 gene mutations have demonstrated that it plays a role in parathyroid development. These mutations also lead to varying degrees of hypopituitarism.

Pancreas
The human fetal pancreas begins to develop by the fourth week of gestation. Five weeks later, the pancreatic alpha and beta cells have begun to emerge. Reaching eight to ten weeks into development, the pancreas starts producing insulin, glucagon, somatostatin, and pancreatic polypeptide. During the early stages of fetal development, the number of pancreatic alpha cells outnumbers the number of pancreatic beta cells. The alpha cells reach their peak in the middle stage of gestation. From the middle stage until term, the beta cells continue to increase in number until they reach an approximate 1:1 ratio with the alpha cells. The insulin concentration within the fetal pancreas is 3.6 pmol/g at seven to ten weeks, which rises to 30 pmol/g at 16–25 weeks of gestation. Near term, the insulin concentration increases to 93 pmol/g. The endocrine cells have dispersed throughout the body within 10 weeks. At 31 weeks of development, the islets of Langerhans have differentiated.

While the fetal pancreas has functional beta cells by 14 to 24 weeks of gestation, the amount of insulin that is released into the bloodstream is relatively low. In a study of pregnant women carrying fetuses in the mid-gestation and near term stages of development, the fetuses did not have an increase in plasma insulin levels in response to injections of high levels of glucose. In contrast to insulin, the fetal plasma glucagon levels are relatively high and continue to increase during development. At the mid-stage of gestation, the glucagon concentration is 6 μg/g, compared to 2 μg/g in adult humans. Just like insulin, fetal glucagon plasma levels do not change in response to an infusion of glucose. However, a study of an infusion of alanine into pregnant women was shown to increase the cord blood and maternal glucagon concentrations, demonstrating a fetal response to amino acid exposure.

As such, while the fetal pancreatic alpha and beta islet cells have fully developed and are capable of hormone synthesis during the remaining fetal maturation, the islet cells are relatively immature in their capacity to produce glucagon and insulin. This is thought to be a result of the relatively stable levels of fetal serum glucose concentrations achieved via maternal transfer of glucose through the placenta. On the other hand, the stable fetal serum glucose levels could be attributed to the absence of pancreatic signaling initiated by incretins during feeding. In addition, the fetal pancreatic islets cells are unable to sufficiently produce cAMP and rapidly degrade cAMP by phosphodiesterase necessary to secrete glucagon and insulin.

During fetal development, the storage of glycogen is controlled by fetal glucocorticoids and placental lactogen. Fetal insulin is responsible for increasing glucose uptake and lipogenesis during the stages leading up to birth. Fetal cells contain a higher amount of insulin receptors in comparison to adults cells and fetal insulin receptors are not downregulated in cases of hyperinsulinemia. In comparison, fetal haptic glucagon receptors are lowered in comparison to adult cells and the glycemic effect of glucagon is blunted. This temporary physiological change aids the increased rate of fetal development during the final trimester. Poorly managed maternal diabetes mellitus is linked to fetal macrosomia, increased risk of miscarriage, and defects in fetal development. Maternal hyperglycemia is also linked to increased insulin levels and beta cell hyperplasia in the post-term infant. Children of diabetic mothers are at an increased risk for conditions such as: polycythemia, renal vein thrombosis, hypocalcemia, respiratory distress syndrome, jaundice, cardiomyopathy, congenital heart disease, and improper organ development.

Gonads
The reproductive system begins development at four to five weeks of gestation with germ cell migration. The bipotential gonad results from the collection of the medioventral region of the urogenital ridge. At the five-week point, the developing gonads break away from the adrenal primordium. Gonadal differentiation begins 42 days following conception.

Male gonadal development
For males, the testes form at six fetal weeks and the sertoli cells begin developing by the eight week of gestation. SRY, the sex-determining locus, serves to differentiate the Sertoli cells. The Sertoli cells are the point of origin for anti-Müllerian hormone. Once synthesized, the anti-Müllerian hormone initiates the ipsilateral regression of the Müllerian tract and inhibits the development of female internal features. At 10 weeks of gestation, the Leydig cells begin to produce androgen hormones. The androgen hormone dihydrotestosterone is responsible for the development of the male external genitalia.

The testicles descend during prenatal development in a two-stage process that begins at eight weeks of gestation and continues through the middle of the third trimester. During the transabdominal stage (8 to 15 weeks of gestation), the gubernacular ligament contracts and begins to thicken. The craniosuspensory ligament begins to break down. This stage is regulated by the secretion of insulin-like 3 (INSL3), a relaxin-like factor produced by the testicles, and the INSL3 G-coupled receptor, LGR8. During the transinguinal phase (25 to 35 weeks of gestation), the testicles descend into the scrotum. This stage is regulated by androgens, the genitofemoral nerve, and calcitonin gene-related peptide. During the second and third trimester, testicular development concludes with the diminution of the fetal Leydig cells and the lengthening and coiling of the seminiferous cords.

Female gonadal development
For females, the ovaries become morphologically visible by the 8th week of gestation. The absence of testosterone results in the diminution of the Wolffian structures. The Müllerian structures remain and develop into the fallopian tubes, uterus, and the upper region of the vagina. The urogenital sinus develops into the urethra and lower region of the vagina, the genital tubercle develops into the clitoris, the urogenital folds develop into the labia minora, and the urogenital swellings develop into the labia majora. At 16 weeks of gestation, the ovaries produce FSH and LH/hCG receptors. At 20 weeks of gestation, the theca cell precursors are present and oogonia mitosis is occurring. At 25 weeks of gestation, the ovary is morphologically defined and folliculogenesis can begin.

Studies of gene expression show that a specific complement of genes, such as follistatin and multiple cyclin kinase inhibitors are involved in ovarian development. An assortment of genes and proteins - such as WNT4, RSPO1, FOXL2, and various estrogen receptors - have been shown to prevent the development of testicles or the lineage of male-type cells.

Pituitary gland
The pituitary gland is formed within the rostral neural plate. The Rathke's pouch, a cavity of ectodermal cells of the oropharynx, forms between the fourth and fifth week of gestation and upon full development, it gives rise to the anterior pituitary gland. By seven weeks of gestation, the anterior pituitary vascular system begins to develop. During the first 12 weeks of gestation, the anterior pituitary undergoes cellular differentiation. At 20 weeks of gestation, the hypophyseal portal system has developed. The Rathke's pouch grows towards the third ventricle and fuses with the diverticulum. This eliminates the lumen and the structure becomes Rathke's cleft. The posterior pituitary lobe is formed from the diverticulum. Portions of the pituitary tissue may remain in the nasopharyngeal midline. In rare cases this results in functioning ectopic hormone-secreting tumors in the nasopharynx.

The functional development of the anterior pituitary involves spatiotemporal regulation of transcription factors expressed in pituitary stem cells and dynamic gradients of local soluble factors. The coordination of the dorsal gradient of pituitary morphogenesis is dependent on neuroectodermal signals from the infundibular bone morphogenetic protein 4 (BMP4). This protein is responsible for the development of the initial invagination of the Rathke's pouch. Other essential proteins necessary for pituitary cell proliferation are Fibroblast growth factor 8 (FGF8), Wnt4, and Wnt5. Ventral developmental patterning and the expression of transcription factors is influenced by the gradients of BMP2 and sonic hedgehog protein (SHH). These factors are essential for coordinating early patterns of cell proliferation.

Six weeks into gestation, the corticotroph cells can be identified. By seven weeks of gestation, the anterior pituitary is capable of secreting ACTH. Within eight weeks of gestation, somatotroph cells begin to develop with cytoplasmic expression of human growth hormone. Once a fetus reaches 12 weeks of development, the thyrotrophs begin expression of Beta subunits for TSH, while gonadotrophs being to express beta-subunits for LH and FSH. Male fetuses predominately produced LH-expressing gonadotrophs, while female fetuses produce an equal expression of LH and FSH expressing gonadotrophs. At 24 weeks of gestation, prolactin-expressing lactotrophs begin to emerge.

Hormones
A hormone is any of a class of signaling molecules produced by cells in glands in multicellular organisms that are transported by the circulatory system to target distant organs to regulate physiology and behaviour. Hormones have diverse chemical structures, mainly of 3 classes: eicosanoids, steroids, and amino acid/protein derivatives (amines, peptides, and proteins). The glands that secrete hormones comprise the endocrine system. The term hormone is sometimes extended to include chemicals produced by cells that affect the same cell (autocrine or intracrine signalling) or nearby cells (paracrine signalling).

Hormones are used to communicate between organs and tissues for physiological regulation and behavioral activities, such as digestion, metabolism, respiration, tissue function, sensory perception, sleep, excretion, lactation, stress, growth and development, movement, reproduction, and mood.

Hormones affect distant cells by binding to specific receptor proteins in the target cell resulting in a change in cell function. This may lead to cell type-specific responses that include rapid changes to the activity of existing proteins, or slower changes in the expression of target genes. Amino acid–based hormones (amines and peptide or protein hormones) are water-soluble and act on the surface of target cells via signal transduction pathways; steroid hormones, being lipid-soluble, move through the plasma membranes of target cells to act within their nuclei.

Cell signalling
The typical mode of cell signalling in the endocrine system is endocrine signaling, that is, using the circulatory system to reach distant target organs. However, there are also other modes, i.e., paracrine, autocrine, and neuroendocrine signaling. Purely neurocrine signaling between neurons, on the other hand, belongs completely to the nervous system.

Autocrine
Autocrine signaling is a form of signaling in which a cell secretes a hormone or chemical messenger (called the autocrine agent) that binds to autocrine receptors on the same cell, leading to changes in the cells.

Paracrine
Some endocrinologists and clinicians include the paracrine system as part of the endocrine system, but there is not consensus. Paracrines are slower acting, targeting cells in the same tissue or organ. An example of this is somatostatin which is released by some pancreatic cells and targets other pancreatic cells.

Juxtacrine
Juxtacrine signaling is a type of intercellular communication that is transmitted via oligosaccharide, lipid, or protein components of a cell membrane, and may affect either the emitting cell or the immediately adjacent cells.

It occurs between adjacent cells that possess broad patches of closely opposed plasma membrane linked by transmembrane channels known as connexons. The gap between the cells can usually be between only 2 and 4 nm.

Disease

Diseases of the endocrine system are common, including conditions such as diabetes mellitus, thyroid disease, and obesity. Endocrine disease is characterized by misregulated hormone release (a productive pituitary adenoma), inappropriate response to signaling (hypothyroidism), lack of a gland (diabetes mellitus type 1, diminished erythropoiesis in chronic kidney failure), or structural enlargement in a critical site such as the thyroid (toxic multinodular goitre). Hypofunction of endocrine glands can occur as a result of loss of reserve, hyposecretion, agenesis, atrophy, or active destruction. Hyperfunction can occur as a result of hypersecretion, loss of suppression, hyperplastic or neoplastic change, or hyperstimulation.

Endocrinopathies are classified as primary, secondary, or tertiary. Primary endocrine disease inhibits the action of downstream glands. Secondary endocrine disease is indicative of a problem with the pituitary gland. Tertiary endocrine disease is associated with dysfunction of the hypothalamus and its releasing hormones.

As the thyroid, and hormones have been implicated in signaling distant tissues to proliferate, for example, the estrogen receptor has been shown to be involved in certain breast cancers. Endocrine, paracrine, and autocrine signaling have all been implicated in proliferation, one of the required steps of oncogenesis.

Other common diseases that result from endocrine dysfunction include Addison's disease, Cushing's disease and Graves' disease. Cushing's disease and Addison's disease are pathologies involving the dysfunction of the adrenal gland. Dysfunction in the adrenal gland could be due to primary or secondary factors and can result in hypercortisolism or hypocortisolism. Cushing's disease is characterized by the hypersecretion of the adrenocorticotropic hormone (ACTH) due to a pituitary adenoma that ultimately causes endogenous hypercortisolism by stimulating the adrenal glands. Some clinical signs of Cushing's disease include obesity, moon face, and hirsutism. Addison's disease is an endocrine disease that results from hypocortisolism caused by adrenal gland insufficiency. Adrenal insufficiency is significant because it is correlated with decreased ability to maintain blood pressure and blood sugar, a defect that can prove to be fatal.

Graves' disease involves the hyperactivity of the thyroid gland which produces the T3 and T4 hormones. Graves' disease effects range from excess sweating, fatigue, heat intolerance and high blood pressure to swelling of the eyes that causes redness, puffiness and in rare cases reduced or double vision.

Other animals
A neuroendocrine system has been observed in all animals with a nervous system and all vertebrates have a hypothalamus–pituitary axis. All vertebrates have a thyroid, which in amphibians is also crucial for transformation of larvae into adult form. All vertebrates have adrenal gland tissue, with mammals unique in having it organized into layers. All vertebrates have some form of a renin–angiotensin axis, and all tetrapods have aldosterone as a primary mineralocorticoid.

title: Endocrine system


text:
Expander graph

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. 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.

Definitions
Intuitively, an expander graph is a finite, undirected multigraph in which every subset of the vertices that 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$ on $n$ vertices is defined as
 * $$h(G) = \min_{0 < |S| \le \frac{n}{2} } \frac{|\partial S|}{|S|},$$
 * where $$\partial S := \{ \{ u, v \} \in E(G) \ : \ u \in S, v \notin S \},$$

which can also be written as $∂S = E(S, \overline{S})$ with $\overline{S} := V(G) \ S$ the complement of $S$ and
 * $$ E(A,B) = \{ \{ u, v \} \in E(G) \ : \ u \in A, v \in B \}$$

the edges between the subsets of vertices $A,B ⊆ V(G)$.

In the equation, the minimum is over all nonempty sets $S$ of at most $n/2$ vertices and $∂S$ is the edge boundary of $S$, i.e., the set of edges with exactly one endpoint in $S$.

Intuitively,
 * $$\min {|\partial S|} = \min E({S}, \overline{S})$$

is the minimum number of edges that need to be cut in order to split the graph in two. The edge expansion normalizes this concept by dividing with smallest number of vertices among the two parts. To see how the normalization can drastically change the value, consider the following example. Take two complete graphs with the same number of vertices $n$ and add $n$ edges between the two graphs by connecting their vertices one-to-one. The minimum cut will be $n$ but the edge expansion will be 1.

Notice that in $min |∂S|$, the optimization can be equivalently done either over $0 ≤ |S| ≤ n/2$ or over any non-empty subset, since $$E(S, \overline{S}) = E(\overline{S}, S)$$. The same is not true for $h(G)$ because of the normalization by $|S|$. If we want to write $h(G)$ with an optimization over all non-empty subsets, we can rewrite it as
 * $$h(G) = \min_{\emptyset \subsetneq S\subsetneq V(G) } \frac{E({S}, \overline{S})}{\min\{|S|, |\overline{S}|\}}.$$

Vertex expansion
The vertex isoperimetric number $hout(G)$ (also vertex expansion or magnification) of a graph $G$ is defined as
 * $$h_{\text{out}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|},$$

where $∂out(S)$ is the outer boundary of $S$, i.e., the set of vertices in $V(G) \ S$ with at least one neighbor in $S$. In a variant of this definition (called unique neighbor expansion) $∂out(S)$ is replaced by the set of vertices in $V$ with exactly one neighbor in $S$.

The vertex isoperimetric number $hin(G)$ of a graph $G$ is defined as
 * $$h_{\text{in}}(G) = \min_{0 < |S|\le \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) \ S$.

Spectral expansion
When $G$ is $d$-regular, a linear algebraic definition of expansion is possible based on the eigenvalues of the adjacency matrix $A = A(G)$ of $G$, where $Aij$ is the number of edges between vertices $i$ and $j$. Because $A$ is symmetric, the spectral theorem implies that $A$ has $n$ real-valued eigenvalues $λ1 ≥ λ2 ≥ … ≥ λn$. It is known that all these eigenvalues are in $[−d, d]$ and more specifically, it is known that $λn = −d$ if and only if $G$ is bipartite.

More formally, we refer to an $n$-vertex, $d$-regular graph with
 * $$\max_{i \neq 1}|\lambda_i| \leq \lambda$$

as an $(n, d, λ)$-graph. The bound given by an $(n, d, λ)$-graph on $λi$ for $i ≠ 1$ is useful many contexts, including the expander mixing lemma.

Spectral expansion can be two-sided, as above, with $$\max_{i \neq 1}|\lambda_i| \leq \lambda$$, or it can be one-sided, with $$\max_{i \neq 1}\lambda_i \leq \lambda$$. The latter is a weaker notion that holds also for bipartite graphs and is still useful for many applications, such as the Alon-Chung lemma.

Because $G$ is regular, the uniform distribution $$u\in\R^n$$ with $ui = 1/n$ for all $i = 1, …, n$ is the stationary distribution of $G$. That is, we have $Au = du$, and $u$ is an eigenvector of $A$ with eigenvalue $λ1 = d$, where $d$ is the degree of the vertices of $G$. The spectral gap of $G$ is defined to be $d − λ2$, and it measures the spectral expansion of the graph $G$.

If we set
 * $$\lambda=\max\{|\lambda_2|, |\lambda_n|\}$$

as this is the largest eigenvalue corresponding to an eigenvector orthogonal to $u$, it can be equivalently defined using the Rayleigh quotient:
 * $$\lambda=\max_{v \perp u, v \neq 0} \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\R^n$$.

The normalized versions of these definitions are also widely used and more convenient in stating some results. Here one considers the matrix $1⁄dA$, 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 $ATA$.

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) \le h(G) \le 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, meaning each vertex is of degree $d$, there is a relationship between the isoperimetric constant $h(G)$ and the gap $d − λ2$ in the spectrum of the adjacency operator of $G$. By standard spectral graph theory, the trivial eigenvalue of the adjacency operator of a $d$-regular graph is $λ1 = d$ and the first non-trivial eigenvalue is $λ2$. If $G$ is connected, then $λ2 < d$. An inequality due to Dodziuk and independently Alon and Milman states that
 * $$\tfrac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}.$$

In fact, the lower bound is tight. The lower bound is achieved in limit for the hypercube $Qn$, where $h(G) = 1$ and $d – λ2 = 2$. The upper bound is (asymptotically) achieved for a cycle, where $h(Cn) = 4/n = Θ(1/n)$ and $d – λ2 = 2 – 2cos(2$\pi$/n) ≈ (2$\pi$/n)2 = Θ(1/n2)$. A better bound is given in as
 * $$ h(G) \le \sqrt{d^2 - \lambda_2^2}.$$

These inequalities are 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:
 * $$h_{\text{out}}(G)\le \left(\sqrt{4 (d-\lambda_2)} + 1\right)^2 -1$$
 * $$h_{\text{in}}(G) \le \sqrt{8(d-\lambda_2)}.$$

Asymptotically speaking, the quantities $λ2$, $2(d − λ2)$, and $h2/d$ are all bounded above by the spectral gap $hout$.

Constructions
There are four general strategies for explicitly constructing families of expander graphs. The first strategy is algebraic and group-theoretic, the second strategy is analytic and uses additive combinatorics, the third strategy is combinatorial and uses the zig-zag and related graph products, and the fourth strategy is based on lifts. Noga Alon showed that certain graphs constructed from finite geometries are the sparsest examples of highly expanding graphs.

Margulis–Gabber–Galil
Algebraic constructions based on Cayley graphs are known for various variants of expander graphs. The following construction is due to Margulis and has been analysed by Gabber and Galil. For every natural number $n$, one considers the graph $Gn$ with the vertex set $$\mathbb Z_n \times \mathbb Z_n$$, where $$\mathbb Z_n=\mathbb Z/n\mathbb Z$$: For every vertex $$(x,y)\in\mathbb Z_n \times \mathbb Z_n$$, its eight adjacent vertices are

 * $$(x \pm 2y,y), (x \pm (2y+1),y), (x,y \pm 2x), (x,y \pm (2x+1)).$$

Then the following holds:

"Theorem. For all $n$, the graph $Gn$ has second-largest eigenvalue $\lambda(G)\leq 5 \sqrt{2}$."

Ramanujan graphs
By a theorem of Alon and Boppana, all sufficiently large $d$-regular graphs satisfy $$\lambda_2 \ge 2\sqrt{d-1} - o(1)$$, where $hin2$ is the second largest eigenvalue in absolute value. As a direct consequence, we know that for every fixed $d$ and $$\lambda< 2 \sqrt{d-1}$$, there are only finitely many $O(d – λ2)$-graphs. Ramanujan graphs are $d$-regular graphs for which this bound is tight, satisfying
 * $$\lambda = \max_{|\lambda_i| < d} |\lambda_i| \le 2\sqrt{d-1}.$$

Hence Ramanujan graphs have an asymptotically smallest possible value of $λ2$. This makes them excellent spectral expanders.

Lubotzky, Phillips, and Sarnak (1988), Margulis (1988), and Morgenstern (1994) show how Ramanujan graphs can be constructed explicitly.

In 1985, Alon, conjectured that most $d$-regular graphs on $n$ vertices, for sufficiently large $n$, are almost Ramanujan. That is, for $(n, d, λ)$, they satisfy

 * $$\lambda \le 2\sqrt{d-1}+\varepsilon$$.

In 2003, Joel Friedman both proved the conjecture and specified what is meant by "most $d$-regular graphs" by showing that random $d$-regular graphs have $$\lambda \le 2\sqrt{d-1}+\varepsilon$$ for every $λ2$ with probability $ε > 0$, where
 * $$\tau = \left\lceil\frac{\sqrt{d-1} +1}{2} \right\rceil.$$

A simpler proof of a slightly weaker result was given by Puder.

Marcus, Spielman and Srivastava, gave a construction of bipartite Ramanujan graphs based on lifts.

Zig-Zag product
Reingold, Vadhan, and Wigderson introduced the zig-zag product in 2003. Roughly speaking, the zig-zag product of two expander graphs produces a graph with only slightly worse expansion. Therefore, a zig-zag product can also be used to construct families of expander graphs. If $G$ is a $ε > 0$-graph and $H$ is an $1 – O(n-τ)$-graph, then the zig-zag product $(n, m, λ1)$ is a $(m, d, λ2)$-graph where $φ$ has the following properties.

Specifically,
 * 1) If $G ◦ H$ and $(nm, d2, φ(λ1, λ2))$, then $λ1 < 1$;
 * $$\phi(\lambda_1, \lambda_2)=\frac{1}{2}(1-\lambda^2_2)\lambda_2 +\frac{1}{2}\sqrt{(1-\lambda^2_2)^2\lambda_1^2 +4\lambda^2_2}.$$

Note that property (1) implies that the zig-zag product of two expander graphs is also an expander graph, thus zig-zag products can be used inductively to create a family of expander graphs.

Intuitively, the construction of the zig-zag product can be thought of in the following way. Each vertex of $G$ is blown up to a "cloud" of $m$ vertices, each associated to a different edge connected to the vertex. Each vertex is now labeled as $λ2 < 1$ where $v$ refers to an original vertex of $G$ and $k$ refers to the $k$th edge of $v$. Two vertices, $φ(λ1, λ2) < 1$ and $φ(λ1, λ2) ≤ λ1 + λ2$ are connected if it is possible to get from $(v, k)$ to $(v, k)$ through the following sequence of moves.

 * 1) Zig - Move from $(w,l)$ to $(v, k)$, using an edge of $H$.
 * 2) Jump across clouds using edge $k'$ in $G$ to get to $(w, l)$.
 * 3) Zag - Move from $(v, k)$ to $(v, k' )$ using an edge of $H$.

Lifts
An $r$-lift of a graph is formed by replacing each vertex by $r$ vertices, and each edge by a matching between the corresponding sets of $$r$$ vertices. The lifted graph inherits the eigenvalues of the original graph, and has some additional eigenvalues. Bilu and Linial showed that every $d$-regular graph has a 2-lift in which the additional eigenvalues are at most $$O(\sqrt{d\log^3 d})$$ in magnitude. They also showed that if the starting graph is a good enough expander, then a good 2-lift can be found in polynomial time, thus giving an efficient construction of $d$-regular expanders for every $d$.

Bilu and Linial conjectured that the bound $$O(\sqrt{d\log^3 d})$$ can be improved to $$2\sqrt{d-1}$$, which would be optimal due to the Alon-Boppana bound. This conjecture was proved in the bipartite setting by Marcus, Spielman and Srivastava, who used the method of interlacing polynomials. As a result, they obtained an alternative construction of bipartite Ramanujan graphs. The original non-constructive proof was turned into an algorithm by Michael B. Cohen. Later the method was generalized to $r$-lifts by Hall, Puder and Sawin.

Randomized constructions
There are many results that show the existence of graphs with good expansion properties through probabilistic arguments. In fact, the existence of expanders was first proved by Pinsker who showed that for a randomly chosen $n$ vertex left $d$ regular bipartite graph, $(w, l' )$ for all subsets of vertices $(w, l' )$ with high probability, where $cd$ is a constant depending on $d$ that is $(w, l)$. Alon and Roichman showed that for every $|N(S)| ≥ (d – 2)|S|$, there is some $|S| ≤ cdn$ such that the following holds: For a group $G$ of order $n$, consider the Cayley graph on $G$ with $O(d-4)$ randomly chosen elements from $G$. Then, in the limit of $n$ getting to infinity, the resulting graph is almost surely an $1 > ε > 0$-expander.

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

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

In a 2006 survey of expander graphs, Hoory, Linial, and Wigderson split the study of expander graphs into four categories: extremal problems, typical behavior, explicit constructions, and algorithms. Extremal problems focus on the bounding of expansion parameters, while typical behavior problems characterize how the expansion parameters are distributed over random graphs. Explicit constructions focus on constructing graphs that optimize certain parameters, and algorithmic questions study the evaluation and estimation of parameters.

Expander mixing lemma
The expander mixing lemma states that for an $c(ε) > 0$-graph, for any two subsets of the vertices $c(ε) log2 n$, 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 $ε$ is. In a random $d$-regular graph, as well as in an Erdős–Rényi random graph with edge probability $(n, d, λ)$, we expect $S, T ⊆ V$ edges between $S$ and $T$.

More formally, let $λ$ 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 \lambda \sqrt{|S| \cdot |T|}.$$

Many properties of $d/n$-graphs are corollaries of the expander mixing lemmas, including the following.

 * An independent set of a graph is a subset of vertices with no two vertices adjacent. In an $d/n • |S| • |T|$-graph, an independent set has size at most $E(S, T)$.
 * The chromatic number of a graph $G$, $(n, d, λ)$, is the minimum number of colors needed such that adjacent vertices have different colors. Hoffman showed that $(n, d, λ)$, while Alon, Krivelevich, and Sudakov showed that if $λn/d$, then $$\chi(G) \leq O \left( \frac{d}{\log(1+d/\lambda)} \right).$$
 * The diameter of a graph is the maximum distance between two vertices, where the distance between two vertices is defined to be the shortest path between them. Chung showed that the diameter of an $χ(G)$-graph is at most $$\left\lceil \log \frac{n}{ \log(d/\lambda)} \right\rceil.$$

Expander walk sampling
The Chernoff bound states that, when sampling many independent samples from a random variable in the range $d/λ ≤ χ(G)$, with high probability the average of our samples is close to the expectation of the random variable. The expander walk sampling lemma, due to and, 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.

AKS sorting network and approximate halvers
Sorting networks take a set of inputs and perform a series of parallel steps to sort the inputs. A parallel step consists of performing any number of disjoint comparisons and potentially swapping pairs of compared inputs. The depth of a network is given by the number of parallel steps it takes. Expander graphs play an important role in the AKS sorting network, which achieves depth $d < 2n/3$. While this is asymptotically the best known depth for a sorting network, the reliance on expanders makes the constant bound too large for practical use.

Within the AKS sorting network, expander graphs are used to construct bounded depth $ε$-halvers. An $ε$-halver takes as input a length $n$ permutation of $(n, d, λ)$ and halves the inputs into two disjoint sets $A$ and $B$ such that for each integer $[−1, 1]$ at most $εk$ of the $k$ smallest inputs are in $B$ and at most $εk$ of the $k$ largest inputs are in $A$. The sets $A$ and $B$ are an $ε$-halving.

Following, a depth $d$ $ε$-halver can be constructed as follows. Take an $n$ vertex, degree $d$ bipartite expander with parts $X$ and $Y$ of equal size such that every subset of vertices of size at most $εn$ has at least $O(log n)$ neighbors.

The vertices of the graph can be thought of as registers that contain inputs and the edges can be thought of as wires that compare the inputs of two registers. At the start, arbitrarily place half of the inputs in $X$ and half of the inputs in $Y$ and decompose the edges into $d$ perfect matchings. The goal is to end with $X$ roughly containing the smaller half of the inputs and $Y$ containing roughly the larger half of the inputs. To achieve this, sequentially process each matching by comparing the registers paired up by the edges of this matching and correct any inputs that are out of order. Specifically, for each edge of the matching, if the larger input is in the register in $X$ and the smaller input is in the register in $Y$, then swap the two inputs so that the smaller one is in $X$ and the larger one is in $Y$. It is clear that this process consists of $d$ parallel steps.

After all $d$ rounds, take $A$ to be the set of inputs in registers in $X$ and $B$ to be the set of inputs in registers in $Y$ to obtain an $ε$-halving. To see this, notice that if a register $u$ in $X$ and $v$ in $Y$ are connected by an edge $uv$ then after the matching with this edge is processed, the input in $u$ is less than that of $v$. Furthermore, this property remains true throughout the rest of the process. Now, suppose for some $(1, …, n)$ that more than $εk$ of the inputs $k ≤ n/2$ are in $B$. Then by expansion properties of the graph, the registers of these inputs in $Y$ are connected with at least $1 – ε⁄ε$ registers in $X$. Altogether, this constitutes more than $k$ registers so there must be some register $A$ in $X$ connected to some register $B$ in $Y$ such that the final input of $A$ is not in $k ≤ n/2$, while the final input of $B$ is. This violates the previous property however, and thus the output sets $A$ and $B$ must be an $ε$-halving.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Expander graph