Namespaces
Variants
Actions

Difference between revisions of "User:Richard Pinch/sandbox-12"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Start article: Catalan number)
(→‎Regular graph: move text)
 
(37 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
=Radical-inverse function=
 +
A function which maps positive integers to real numbers in the unit interval by reversing the expansion in a given base $b$.  Let $n$ have the base $b$ expansion
 +
$$
 +
n = \sum_{i=0}^k d_i b^i
 +
$$
 +
where $0 \le d_i < b$ and $d_k \ne 0$; then the radical inverse
 +
$$
 +
\phi_b(n) = \sum_{i=0}^k d_i b^{-1-i} \ .
 +
$$
 +
 +
The radical inverse function is used to construct sequences with low [[discrepancy]]: these are of use in quasi-Monte-Carlo methods.
 +
 +
The '''van der Corput sequence''' is the sequence $\left({\phi_2(n)}\right)$.  The discrepancy $D_N$ of this sequence satisfies
 +
$$
 +
N D_N \le \frac{\log(N+1)}{\log 2} \ .
 +
$$
 +
 +
====References====
 +
* L. Kuipers,  H. Niederreiter,  "Uniform distribution of sequences" , Wiley  (1974) {{ZBL|0281.10001}}; repr. Dover (2006) ISBN 0-486-45019-8
 +
 +
=Dispersion=
 +
The dispersion of a sequence $x_n$ in a [[metric space]] $(X,d)$ is defined as the function
 +
$$
 +
D_N = \sup_{x \in X} \min_{n=1,\ldots,N} d(x,x_n) \ .
 +
$$
 +
The associated ''dispersion constant'' is $\limsup_{N\rightarrow\infty} N d_N$.
 +
 +
If a sequence has low [[discrepancy]] then its dispersion must also be low, but the converse does not hold.
 +
 +
Sequences with low dispersion play a part in quasi-Monte-Carlo methods for global optimisation problems.
 +
 +
====References====
 +
* Harald Niederreiter, "On a measure of denseness for sequences", ''Topics in classical number theory, Colloq. Budapest 1981, Vol. II'', Colloq. Math. Soc. János Bolyai '''34''' (1984) 1163-1208 {{ZBL|0547.10045}}
 +
 
=Dyck path=
 
=Dyck path=
 
A [[lattice path]] on the square lattice from the origin $(0,0)$ to some point $(n,n)$ consisting of $2n$ steps of the form $N : (x,y) \rightarrow (x,y+1)$ and $E : (x,y) \rightarrow (x+1,y)$ with the property that the path
 
A [[lattice path]] on the square lattice from the origin $(0,0)$ to some point $(n,n)$ consisting of $2n$ steps of the form $N : (x,y) \rightarrow (x,y+1)$ and $E : (x,y) \rightarrow (x+1,y)$ with the property that the path
Line 17: Line 51:
 
The [[generating function]] is given by
 
The [[generating function]] is given by
 
$$
 
$$
\sum_{n=1^\infty C_n z^n = \frac{1-\sqrt{1-4z}}{2z} \ .
+
\sum_{n=1}^\infty C_n z^n = \frac{1-\sqrt{1-4z}}{2z} \ .
 
$$
 
$$
 
The Catalan numbers appear in the enumeration of a number of combinatorially defined object:
 
The Catalan numbers appear in the enumeration of a number of combinatorially defined object:
 
* [[Bernoulli excursion]]
 
* [[Bernoulli excursion]]
 
* [[Dyck path]]s
 
* [[Dyck path]]s
 +
* Parenthesised sequences; words of the [[Dyck language]]
 +
* Complete [[Binary tree|binary]] [[rooted plane tree]]s
 +
 +
====References====
 +
 +
=Poisson ratio=
 +
The ratio of longitudinal extension to lateral compression when an elastic substance is put under tension.
 +
 +
See: [[Elasticity, mathematical theory of]]; [[Lamé constants]].
 +
 +
====References====
 +
* Horace Lamb, "Statics", Cambridge University Press (1960)
 +
 +
=Elastic modulus=
 +
''Young's modulus''
 +
 +
The ratio of longitudinal extension to force applied per unit area when an elastic substance is put under tension.
 +
 +
See: [[Elasticity, mathematical theory of]]; [[Lamé constants]].
 +
 +
====References====
 +
* Horace Lamb, "Statics", Cambridge University Press (1960)
 +
 +
=Partition symbol=
 +
A notation used to compactly express propositions of [[partition calculus]].  The symbol
 +
$$
 +
\alpha \rightarrow (\beta)_\gamma^r
 +
$$
 +
for cardinals $\alpha,\beta,\gamma$ and natural number $r$, denotes the following proposition.
 +
 +
Given a set $S$ and a colouring of $S^r$ into a set of $\gamma$ colours, there exists a subset $T$ of $S$ of cardinality $|T|=\beta$ such that the colouring restricted to $T^r$ is monochrome.
 +
 +
Here a colouring of a set $X$ by a set of colours $C$ is simply a partition of $X$ into parts indexed by the set $C$.
 +
 +
The symbol
 +
$$
 +
\alpha \rightarrow (\beta_1,\ldots,\beta_j)^r
 +
$$
 +
denotes the following proposition:
 +
 +
Given a set $S$ of cardinality $\alpha$ and a colouring of $S^r$ by $j$ colours, there exists an index $i$ subset $T$ of $S$ of cardinality $|T|=\beta_i$ such that the colouring restricted to $T^r$ is monochrome.
 +
 +
Examples.
 +
 +
* [[Ramsey theorem|Ramsey's theorem]]: $\omega \rightarrow (\omega)_n^r$.
 +
* Sierpinski's theorem: $c \not\rightarrow (\omega_1,\omega_2)^2$.
 +
 +
 +
====References====
 +
* M.E. Rudin, "Lectures on set theoretic topology", Amer. Math. Soc. (1975) ISBN 0-8218-1673-X  {{ZBL|0318.54001}}
 +
 +
=Isthmus=
 +
''bridge, co-loop''
 +
 +
An isthmus of a [[graph]] is an edge for which deletion increases the number of connected components of the graph. 
 +
 +
An isthmus of a [[matroid]] $M$ on a set $E$ is an element of $E$ which is in every basis for $M$.  An element of $E$ is a co-loop of $M$ if and only if it is a ''loop'' of the [[dual matroid]] $M^*$, that is, does not belong to any base of $M^*$.  If $M$ is a [[graphic matroid]], then the definitions coincide.
 +
 +
====References====
 +
* J. G. Oxley, "Matroid Theory" (2 ed) Oxford University Press (2011) ISBN 978-0-19-856694-6  {{ZBL|1254.05002}}
 +
* D. J. A. Welsh, "Matroid Theory", Dover (2010) [1976] ISBN 0486474399 {{ZBL|0343.05002}}
 +
 +
=Ordered topological space=
 +
A [[topological space]] $X$ with a [[partial order]] ${\le}$ related to the topology by the condition that if $x < y$ then there are neighbourhoods $N_x$, $N_y$ such that $x < y'$ for all $y' \in N_y$ and $x' < y$ for all $x' \in N_x$.  An ordered topological space is necessarily a [[Hausdorff space]]. 
 +
 +
An ordered topological space is ''totally order-disconnected'' if whenever $x \not\le y$ there exists a [[clopen]] down-set $D$ such that $x \not\in D$ and $y \in D$.
 +
 +
A '''Priestley space''' is a compact totally order-disconnected space.  An '''Ockham space''' is a Priestley space equipped with an order-reversing continuous mapping $g$: see also [[Ockham algebra]].
  
 
====References====
 
====References====
 +
* Samuel Eilenberg, "Ordered Topological Spaces", ''American Journal of Mathematics'' '''63''' (1941) 39-45  {{DOI|10.2307/2371274}}  {{ZBL|0024.19203}}
 +
* T.S. Blyth, "Lattices and ordered algebraic structures", Springer (2005) ISBN 1-85233-905-5  {{ZBL|1073.06001}}

Latest revision as of 09:27, 19 January 2021

Radical-inverse function

A function which maps positive integers to real numbers in the unit interval by reversing the expansion in a given base $b$. Let $n$ have the base $b$ expansion $$ n = \sum_{i=0}^k d_i b^i $$ where $0 \le d_i < b$ and $d_k \ne 0$; then the radical inverse $$ \phi_b(n) = \sum_{i=0}^k d_i b^{-1-i} \ . $$

The radical inverse function is used to construct sequences with low discrepancy: these are of use in quasi-Monte-Carlo methods.

The van der Corput sequence is the sequence $\left({\phi_2(n)}\right)$. The discrepancy $D_N$ of this sequence satisfies $$ N D_N \le \frac{\log(N+1)}{\log 2} \ . $$

References

  • L. Kuipers, H. Niederreiter, "Uniform distribution of sequences" , Wiley (1974) Zbl 0281.10001; repr. Dover (2006) ISBN 0-486-45019-8

Dispersion

The dispersion of a sequence $x_n$ in a metric space $(X,d)$ is defined as the function $$ D_N = \sup_{x \in X} \min_{n=1,\ldots,N} d(x,x_n) \ . $$ The associated dispersion constant is $\limsup_{N\rightarrow\infty} N d_N$.

If a sequence has low discrepancy then its dispersion must also be low, but the converse does not hold.

Sequences with low dispersion play a part in quasi-Monte-Carlo methods for global optimisation problems.

References

  • Harald Niederreiter, "On a measure of denseness for sequences", Topics in classical number theory, Colloq. Budapest 1981, Vol. II, Colloq. Math. Soc. János Bolyai 34 (1984) 1163-1208 Zbl 0547.10045

Dyck path

A lattice path on the square lattice from the origin $(0,0)$ to some point $(n,n)$ consisting of $2n$ steps of the form $N : (x,y) \rightarrow (x,y+1)$ and $E : (x,y) \rightarrow (x+1,y)$ with the property that the path never passes below the line $y=x$.

The number of Dyck paths of length $2n$ is given by the $n$-th Catalan number $$ C_n = \frac{1}{n+1}\binom{2n}{n} \ . $$

References

Catalan number

The $n$-th Catalan number $$ C_n = \frac{1}{n+1}\binom{2n}{n} \ . $$ The generating function is given by $$ \sum_{n=1}^\infty C_n z^n = \frac{1-\sqrt{1-4z}}{2z} \ . $$ The Catalan numbers appear in the enumeration of a number of combinatorially defined object:

References

Poisson ratio

The ratio of longitudinal extension to lateral compression when an elastic substance is put under tension.

See: Elasticity, mathematical theory of; Lamé constants.

References

  • Horace Lamb, "Statics", Cambridge University Press (1960)

Elastic modulus

Young's modulus

The ratio of longitudinal extension to force applied per unit area when an elastic substance is put under tension.

See: Elasticity, mathematical theory of; Lamé constants.

References

  • Horace Lamb, "Statics", Cambridge University Press (1960)

Partition symbol

A notation used to compactly express propositions of partition calculus. The symbol $$ \alpha \rightarrow (\beta)_\gamma^r $$ for cardinals $\alpha,\beta,\gamma$ and natural number $r$, denotes the following proposition.

Given a set $S$ and a colouring of $S^r$ into a set of $\gamma$ colours, there exists a subset $T$ of $S$ of cardinality $|T|=\beta$ such that the colouring restricted to $T^r$ is monochrome.

Here a colouring of a set $X$ by a set of colours $C$ is simply a partition of $X$ into parts indexed by the set $C$.

The symbol $$ \alpha \rightarrow (\beta_1,\ldots,\beta_j)^r $$ denotes the following proposition:

Given a set $S$ of cardinality $\alpha$ and a colouring of $S^r$ by $j$ colours, there exists an index $i$ subset $T$ of $S$ of cardinality $|T|=\beta_i$ such that the colouring restricted to $T^r$ is monochrome.

Examples.

  • Ramsey's theorem: $\omega \rightarrow (\omega)_n^r$.
  • Sierpinski's theorem: $c \not\rightarrow (\omega_1,\omega_2)^2$.


References

  • M.E. Rudin, "Lectures on set theoretic topology", Amer. Math. Soc. (1975) ISBN 0-8218-1673-X Zbl 0318.54001

Isthmus

bridge, co-loop

An isthmus of a graph is an edge for which deletion increases the number of connected components of the graph.

An isthmus of a matroid $M$ on a set $E$ is an element of $E$ which is in every basis for $M$. An element of $E$ is a co-loop of $M$ if and only if it is a loop of the dual matroid $M^*$, that is, does not belong to any base of $M^*$. If $M$ is a graphic matroid, then the definitions coincide.

References

  • J. G. Oxley, "Matroid Theory" (2 ed) Oxford University Press (2011) ISBN 978-0-19-856694-6 Zbl 1254.05002
  • D. J. A. Welsh, "Matroid Theory", Dover (2010) [1976] ISBN 0486474399 Zbl 0343.05002

Ordered topological space

A topological space $X$ with a partial order ${\le}$ related to the topology by the condition that if $x < y$ then there are neighbourhoods $N_x$, $N_y$ such that $x < y'$ for all $y' \in N_y$ and $x' < y$ for all $x' \in N_x$. An ordered topological space is necessarily a Hausdorff space.

An ordered topological space is totally order-disconnected if whenever $x \not\le y$ there exists a clopen down-set $D$ such that $x \not\in D$ and $y \in D$.

A Priestley space is a compact totally order-disconnected space. An Ockham space is a Priestley space equipped with an order-reversing continuous mapping $g$: see also Ockham algebra.

References

  • Samuel Eilenberg, "Ordered Topological Spaces", American Journal of Mathematics 63 (1941) 39-45 DOI 10.2307/2371274 Zbl 0024.19203
  • T.S. Blyth, "Lattices and ordered algebraic structures", Springer (2005) ISBN 1-85233-905-5 Zbl 1073.06001
How to Cite This Entry:
Richard Pinch/sandbox-12. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-12&oldid=42597