Namespaces
Variants
Actions

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

From Encyclopedia of Mathematics
Jump to: navigation, search
(Start article: Weierstrass preparation theorem)
(Start article: Tutte matrix)
Line 1: Line 1:
 +
 +
=Tutte matrix=
 +
In [[graph theory]], the '''Tutte matrix''' <math>A</math> of a [[Graph (mathematics)|graph]] ''G'' = (''V'',''E'') is a matrix used to determine the existence of a [[perfect matching]]: that is, a set of edges which is incident with each vertex exactly once.
 +
 +
If the set of vertices ''V'' has 2''n'' elements then the Tutte matrix is a 2''n'' × 2''n'' matrix A with entries
 +
 +
::: <math>A_{ij} = \begin{cases} x_{ij}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } i<j\\
 +
-x_{ji}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } i>j\\
 +
0\;\;\;\;\mbox{otherwise} \end{cases}</math>
 +
 +
where the ''x''<sub>''ij''</sub> are indeterminates.  The [[determinant]] of this [[skew-symmetric]] matrix is then a polynomial (in the variables ''x<sub>ij</sub>'', ''i<j'' ): this coincides with the square of the [[pfaffian]] of the matrix ''A'' and is non-zero (as a polynomial) if and only if a perfect matching exists.  (It should be noted that this is not the [[Tutte polynomial]] of ''G''.)
 +
 +
The Tutte matrix is a generalisation of the [[Edmonds matrix]] for a balanced [[bipartite graph]].
 +
 +
==References==
 +
*{{cite book|author=R. Motwani, P. Raghavan |title=Randomized Algorithms|publisher=Cambridge University Press|year=1995|page=167}}
 +
*{{cite book|author=Allen B. Tucker|title=Computer Science Handbook|publisher=CRC Press|date=2004|isbn=158488360X|page=12.19}}
 +
* {{cite journal|url= http://jlms.oxfordjournals.org/cgi/reprint/s1-22/2/107.pdf|title= The factorization of linear graphs.
 +
|accessdate= 2008-06-15|author= W.T. Tutte|authorlink=W. T. Tutte|year= 1947|month= April|volume=22|journal=J. London Math. Soc.|pages=107-111|doi=10.1112/jlms/s1-22.2.107}}
 +
 +
 
=Weierstrass preparation theorem=
 
=Weierstrass preparation theorem=
 
In [[algebra]], the '''Weierstrass preparation theorem''' describes a canonical form for [[formal power series]] over a [[complete local ring]].
 
In [[algebra]], the '''Weierstrass preparation theorem''' describes a canonical form for [[formal power series]] over a [[complete local ring]].

Revision as of 06:44, 8 September 2013

Tutte matrix

In graph theory, the Tutte matrix \(A\) of a graph G = (V,E) is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once.

If the set of vertices V has 2n elements then the Tutte matrix is a 2n × 2n matrix A with entries

\[A_{ij} = \begin{cases} x_{ij}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } i<j\\ -x_{ji}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } i>j\\ 0\;\;\;\;\mbox{otherwise} \end{cases}\]

where the xij are indeterminates. The determinant of this skew-symmetric matrix is then a polynomial (in the variables xij, i<j ): this coincides with the square of the pfaffian of the matrix A and is non-zero (as a polynomial) if and only if a perfect matching exists. (It should be noted that this is not the Tutte polynomial of G.)

The Tutte matrix is a generalisation of the Edmonds matrix for a balanced bipartite graph.

References


Weierstrass preparation theorem

In algebra, the Weierstrass preparation theorem describes a canonical form for formal power series over a complete local ring.

Let O be a complete local ring and f a formal power series in O''X''. Then f can be written uniquely in the form

\[f = (X^n + b_{n-1}X^{n-1} + \cdots + b_0) u(x) , \,\]

where the bi are in the maximal ideal m of O and u is a unit of O''X''.

The integer n defined by the theorem is the Weierstrass degree of f.

References


Zipf distribution

In probability theory and statistics, the Zipf distribution and zeta distribution refer to a class of discrete probability distributions. They have been used to model the distribution of words in words in a text , of text strings and keys in databases, and of the sizes of businesses and towns.

The Zipf distribution with parameter n assigns probability proportional to 1/r to an integer rn and zero otherwise, with normalization factor Hn, the n-th harmonic number.

A Zipf-like distribution with parameters n and s assigns probability proportional to 1/rs to an integer rn and zero otherwise, with normalization factor \(\sum_{r=1}^n 1/r^s\).

The zeta distribution with parameter s assigns probability proportional to 1/rs to all integers r with normalization factor given by the Riemann zeta function 1/ζ(s).

References

How to Cite This Entry:
Richard Pinch/sandbox-CZ. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-CZ&oldid=30417