# User:Richard Pinch/sandbox-12

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} \ .$$

# 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:

# Poisson ratio

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

#### 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.

#### 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=51399