User:Richard Pinch/sandbox-12

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:

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

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 element 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 0343.05002