# User:Richard Pinch/sandbox-12

## Contents

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

- Bernoulli excursion
- Dyck paths
- Parenthesised sequences; words of the Dyck language
- Complete binary rooted plane trees

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