formulasearchengine - User contributions [en]

V-Cube 7

2014-01-22T16:09:12Z

86.17.134.115:

In [[mathematical morphology]], '''hit-or-miss transform''' is an operation that detects a given configuration (or pattern) in a [[binary image]], using the morphological [[erosion (morphology)|erosion]] operator and a pair of [[Disjoint sets|disjoint]] [[structuring element]]s. The result of the hit-or-miss transform is the set of positions, where the first [[structuring element]] fits in the foreground of the input image, and the second structuring element misses it completely.

== Mathematical definition ==

In binary morphology, an image is viewed as a [[subset]] of an [[Euclidean space]] <math>\mathbb{R}^d</math> or the integer grid <math>\mathbb{Z}^d</math>, for some dimension ''d''. Let us denote this space or grid by ''E''.

A structuring element is a simple, pre-defined shape, represented as a binary image, used to probe another binary image, in morphological operations such as [[erosion (morphology)|erosion]], [[dilation (morphology)|dilation]], [[opening (morphology)|opening]], and [[closing (morphology)|closing]].

Let <math>C</math> and <math>D</math> be two structuring elements satisfying <math>C\cap D=\emptyset</math>. The pair (''C'',''D'') is sometimes called ''composite structuring element''. The hit-or-miss transform of a given image ''A'' by ''B''=(''C'',''D'') is given by:

::<math>A\odot B=(A\ominus C)\cap(A^c\ominus D)</math>,

where <math>A^c</math> is the [[set complement]] of ''A''.

That is, a point ''x'' in ''E'' belongs to the hit-or-miss transform output if ''C'' translated to ''x'' fits in ''A'', and ''D'' translated to ''x'' misses ''A'' (fits the background of ''A'').

== Some applications ==

===Thinning===

Let <math>E=Z^2</math>, and consider the eight composite structuring elements, composed by:

:<math>C_1=\{(0,0),(-1,-1),(0,-1),(1,-1)\}</math> and <math>D_1=\{(-1,1),(0,1),(1,1)\}</math>,
:<math>C_2=\{(-1,0),(0,0),(-1,-1),(0,-1)\}</math> and <math>D_2=\{(0,1),(1,1),(1,0)\}</math>
and the three rotations of each by <math>90^o</math>, <math>180^o</math>, and <math>270^o</math>. The corresponding composite structuring elements are denoted <math>B_1,\ldots,B_8</math>.

For any ''i'' between 1 and 8, and any binary image ''X'', define
::<math>X\otimes B_i=X\setminus (X\odot B_i)</math>,
where <math>\setminus</math> denotes the [[set minus|set-theoretical difference]].

The thinning of an image ''A'' is obtained by cyclically iterating until convergence:

:<math>A\otimes B_1\otimes B_2\otimes\ldots\otimes B_8\otimes B_1\otimes B_2\otimes\ldots</math>.

===Other applications===

* '''[[Pattern detection]]'''. By definition, the hit-or-miss transform indicates the positions where a certain pattern (characterized by the composite structuring element ''B'') occurs in the input image.

* '''[[Pruning (morphology)|Pruning]]'''. The hit-or-miss transform can be used to identify the end-points of a line to allow this line to be shrunk from each end to remove unwanted branches.

* Computing the '''[[Euler number (topology)|Euler number]]'''.

==Bibliography==
* ''An Introduction to Morphological Image Processing'' by Edward R. Dougherty, ISBN 0-8194-0845-X (1992)

[[Category:Mathematical morphology]]
[[Category:Digital geometry]]

Rank (differential topology)

2013-04-17T20:20:26Z

86.17.79.159:

The '''Stanley–Wilf conjecture''', formulated independently by [[Richard P. Stanley]] and [[Herbert Wilf]] in the late 1980s, states that every [[permutation pattern]] defines a set of permutations whose growth rate is [[Exponential growth|singly exponential]]. It was proved by {{harvs|first1=Adam|last1=Marcus|author1-link=Adam Marcus (mathematician)|first2=Gábor|last2=Tardos|author2-link=Gábor Tardos|year=2004|txt}} and is no longer a conjecture. Marcus and Tardos actually proved a different conjecture, due to {{harvs|first1=Zoltán|last1=Füredi|author1-link=Zoltán Füredi|first2=Péter|last2=Hajnal|year=1992|txt}}, which had been shown to imply the Stanley–Wilf conjecture by {{harvtxt|Klazar|2000}}.

==Statement==
The Stanley–Wilf conjecture states that for every permutation ''β'', there is a constant ''C'' such that the number |''S''''n''(''β'')| of permutations of length ''n'' which avoid ''β'' as a [[permutation pattern]] is at most ''C''''n''. As {{harvtxt|Arratia|1999}} observed, this is equivalent to the convergence of the [[Limit (mathematics) |limit]]
:<math>\lim_{n\to\infty} |S_n(\beta)|^{1/n}.</math>

The upper bound given by Marcus and Tardos for ''C'' is [[Exponential function|exponential]] in the length of ''β''. A stronger conjecture of {{harvtxt|Arratia|1999}} had stated that one could take ''C'' to be {{Nowrap|(''k'' − 1)2}}, where ''k'' denotes the length of ''β'', but this conjecture was disproved for the permutation {{Nowrap|1=''β'' = 4231}} by {{harvtxt|Albert|Elder|Rechnitzer|Westcott|2006}}. Indeed, {{harvtxt|Fox|preprint}} has shown that ''C'' is, in fact, exponential in ''k'' for [[almost all]] permutations.

==Allowable growth rates==
Not every growth rate of the form ''C''''n'' may be achieved by a permutation class, regardless of whether it is defined by a single forbidden permutation pattern or a set of forbidden patterns. If the number of permutations in a permutation class grows at more than a polynomial rate, it must grow at least as quickly as the [[Fibonacci number]]s. More specifically, define the growth constant (or Stanley–Wilf limit) of a permutation class ''P'', with ''f''''P''(''n'') permutations of length ''n'', to be
:<math>\limsup_{n\to\infty} f_P(n)^{1/n}.</math>
If the growth constant is zero, then ''f''''P''(''n'') must be a polynomial. If it is not zero, then it must be the largest root of a polynomial of the form
:<math>1+x+x^2+x^3+\cdots x^{k-1}=x^k,</math>
for an integer ''k'' ≥ 2.
For ''k'' = 2, ''C'' is the [[golden ratio]], the base of the growth rate of the Fibonacci numbers. In general, as ''k'' grows larger, these roots approach 2. Thus, in this range, there are only a countably infinite number of growth rates possible.<ref>{{harvtxt|Klazar|2010}}; {{harvtxt|Kaiser|Klazar|2003}}.</ref> However, for every ''C'' > 2.48188 there exists a permutation class (possibly with infinitely many forbidden patterns) whose growth constant is ''C''.<ref>{{harvtxt|Klazar|2010}}; {{harvtxt|Vatter|2010}}.</ref>

==See also==
*[[Enumerations of specific permutation classes]] for the growth rates of specific sets defined by permutation patterns

==Notes==
{{reflist}}

== References ==
*{{Citation | last1=Albert | first1=Michael H. | author1-link=Michael H. Albert | last2=Elder | first2=Murray | last3=Rechnitzer | first3=Andrew | last4=Westcott | first4=P. | last5=Zabrocki | first5=Mike | title=On the Stanley–Wilf limit of 4231-avoiding permutations and a conjecture of Arratia | mr = 2199982 | year=2006 | journal=[[Advances in Applied Mathematics]] | volume=36 | issue=2 | pages=96–105 | doi=10.1016/j.aam.2005.05.007}}.
*{{Citation | last1=Arratia | first1=Richard | authorlink=Richard Arratia | title=On the Stanley–Wilf conjecture for the number of permutations avoiding a given pattern | mr = 1710623 | year=1999 | journal=[[Electronic Journal of Combinatorics]] | volume=6 | page = N1 | url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/v6i1n1}}.
*{{Citation | last1=Fox | first1=Jacob | year=preprint | title=Stanley-Wilf limits are typically exponential | id = {{arxiv | id = 1310.8378}}
}}.
*{{Citation | last1=Füredi | first1=Zoltán | author1-link=Zoltán Füredi | last2=Hajnal | first2=Péter | title=Davenport–Schinzel theory of matrices | mr = 1171777 | year=1992 | journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] | volume=103 | issue=3 | pages=233–251 | doi=10.1016/0012-365X(92)90316-8}}.
*{{citation
| last1 = Kaiser | first1 = Tomáš
| last2 = Klazar | first2 = Martin
| date = March 2002
| issue = 2
| journal = Electronic Journal of Combinatorics
| mr = 2028280
| page = Research paper 10, 20
| title = On growth rates of closed permutation classes
| url = http://www.combinatorics.org/Volume_9/Abstracts/v9i2r10.html
| volume = 9}}.
*{{Citation | last1=Klazar | first1=Martin | contribution=The Füredi–Hajnal conjecture implies the Stanley–Wilf conjecture | mr = 1798218 | year=2000 | title=Formal Power Series and Algebraic Combinatorics (Moscow, 2000) | publisher = Springer | pages=250–255}}.
*{{citation
| last = Klazar | first = Martin
| contribution = Some general results in combinatorial enumeration
| doi = 10.1017/CBO9780511902499.002
| location = Cambridge
| mr = 2732822
| pages = 3–40
| publisher = Cambridge Univ. Press
| series = London Math. Soc. Lecture Note Ser.
| title = Permutation patterns
| volume = 376
| year = 2010}}.
*{{Citation | last1=Marcus | first1=Adam | last2=Tardos | first2= Gábor | author2-link=Gábor Tardos | title=Excluded permutation matrices and the Stanley–Wilf conjecture | mr = 2063960 | year=2004 | journal=[[Journal of Combinatorial Theory]] | series= Series A | volume=107 | issue=1 | pages=153–160 | doi=10.1016/j.jcta.2004.04.002}}.
*{{citation
| last = Vatter | first = Vincent
| doi = 10.1112/S0025579309000503
| issue = 1
| journal = Mathematika
| mr = 2604993
| pages = 182–192
| title = Permutation classes of every growth rate above 2.48188
| volume = 56
| year = 2010}}.

==External links==
* [http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/paramath.pdf A Description of The Stanley–Wilf Conjecture] – by [[Doron Zeilberger]].
* {{mathworld|urlname=Stanley-WilfConjecture|title=Stanley-Wilf conjecture}}

{{DEFAULTSORT:Stanley-Wilf conjecture}}
[[Category:Enumerative combinatorics]]
[[Category:Theorems in discrete mathematics]]
[[Category:Permutation patterns]]

Gossip (video game)

2013-03-18T01:14:09Z

86.17.246.0:

In [[differential geometry]] and [[theoretical physics]], the '''classification of electromagnetic fields''' is a pointwise classification of [[bivector]]s at each point of a [[Lorentzian manifold]]. It is used in the study of solutions of [[Maxwell's equations]] and has applications in Einstein's theory of [[general relativity]].

==The classification theorem==

A (real) bivector field may be viewed, at any given event in a spacetime, as a ''skew-symmetric'' [[linear operator]] on a four-dimensional (real) [[vector space]], ''r''''a'' → ''F''''a''''b''''r''''b''. Here, the vector space is the tangent space at the given event, and thus isomorphic as a (real) inner product space to E1,3. That is, it has the same notion of vector [[magnitude (mathematics)|magnitude]] and [[angle]] (or inner product) as [[Minkowski spacetime]].

In the remainder of this section (and in the next section), we'll assume our spacetime ''is'' Minkowski spacetime. This simplifies the mathematics (but tends to blur the distinction between the tangent space at an event and the underlying manifold). Fortunately, nothing will be lost by this apparently drastic specialization, for reasons we discuss as the end of the article.

In studying any linear operator, we confront the ''eigenvalue problem'', that is, the problem of finding [[eigenvalues]] ''λ'' and [[eigenvectors]] ''r'' which satisfy the ''eigenvalue equation''
: <math>F^a{}_br^b \, =\lambda r^a</math>
The skew-symmetry of the operator we are interested in now implies that one of the following must hold:
*''r'' is a [[null vector (Minkowski space)|null vector]] belonging to a nonzero eigenvalue
*''r'' is a nonnull eigenvector belonging to the eigenvalue zero
*''r'' is a null eigenvector belonging to the eigenvalue zero
The linearly independent null [[eigenspace]]s are called the ''principal null directions'' of the bivector.

The classification theorem characterizes the possible principal null directions of a bivector. It states that one of the following must hold for any ''nonzero'' bivector:
* one ''repeated'' principal null direction, in this case, the bivector is said to be ''null'',
* two ''distinct'' principal null directions, in this case, the bivector is said to be ''non-null''.
Furthermore, for any non-null bivector, the two eigenvalues associated with the two distinct principal null directions have the same magnitude but opposite sign, ''λ'' = ±''ν'', so we have three subclasses of non-null bivectors:
:*''spacelike'': ''ν'' = 0
:*''timelike'' : ''ν'' ≠ 0 and rank ''F'' = 2
:*''non-simple'': ''ν'' ≠ 0 and rank ''F'' = 4
where the rank refers to the [[rank (linear algebra)|rank]] of the linear operator ''F''. Every nonsimple bivector can be written as a ''sum'' of at most two simple ones.

==Physical interpretation==

The algebraic classification of bivectors given above has an important application in [[relativistic physics]]: the [[electromagnetic field]] is represented by a skew-symmetric second rank tensor (the electromagnetic field tensor) so we immediately obtain an algebraic classification of electromagnetic fields.

Recall that for in a cartesian chart on Minkowski spacetime, the [[electromagnetic field tensor]] has components
:<math>F_{ab} = \left(
\begin{matrix}
0 & B_z & -B_y & E_x/c \\
-B_z & 0 & B_x & E_y/c \\
B_y & -B_x & 0 & E_z/c \\
-E_x/c & -E_y/c & -E_z/c & 0
\end{matrix}
\right) </math>
where <math>E_x, E_y, E_z</math> and <math>B_x, B_y, B_z</math> denote respectively the components of the electric and magnetic fields, as measured by an inertial observer (at rest in our coordinates). As usual in relativistic physics, we will find it convenient to work with [[geometrized unit system|geometrised units]] in which <math>c=1</math>. In the "tensor gymanastics" formalism of special relativity, the [[Minkowski metric]] <math>\eta</math> is used to raise and lower indices.

===Invariants===

The fundamental invariants of the electromagnetic field are:
:<math> P \equiv \frac{1}{2} F_{ab} \, F^{ab} = \| \vec{B} \|^2 - \| \vec{E} \|^2 = -\frac{1}{2}{}^* F_{ab} \, {}^* F^{ab}</math>
:<math>Q \equiv \frac{1}{4} F_{ab} \, {}^*F^{ab} =\frac{1}{4}\epsilon^{abcd}F_{ab}F_{cd}= \vec{E} \cdot \vec{B}</math>.
(Fundamental means that every other invariant can be expressed in terms of these two.)

A '''null electromagnetic field''' is characterised by <math>P = Q =0</math>. In this case, the invariants reveal that the electric and magnetic fields are perpendicular and that they are of the same magnitude (in geometrised units). An example of a null field is a [[plane wave|plane electromagnetic wave]] in [[Minkowski space]].

A '''non-null field''' is characterised by <math>P^2+Q^2 \neq \, 0</math>. If <math>P \neq 0 = Q</math>, there exists an [[inertial frame]] for which either the electric or magnetic field vanishes. (These correspond respectively to ''magnetostatic'' and ''electrostatic'' fields.) If <math>Q \neq 0</math>, there exists an inertial frame in which electric and magnetic fields are proportional.

==Curved Lorentzian manifolds==

So far we have discussed only flat spacetime, i.e. the [[Minkowski spacetime|Minkowski vacuum]]. Fortunately, according to the (strong) equivalence principle, if we simply replace "inertial frame" above with a [[frame fields in general relativity|frame field]], everything works out exactly the same way on curved manifolds.

==See also==

*[[Electromagnetic peeling theorem]]
*[[Electrovacuum solution]]
*[[Lorentz group]]
*[[Petrov classification]]

==References==

*{{cite book | author=Landau, Lev D.; and Lifshitz, E. M. | title=The Classical Theory of Fields | location=New York | publisher=Pergamon | year=1973 | isbn=0-08-025072-6}} See ''section 25''.

[[Category:Mathematical physics]]
[[Category:Electromagnetism]]
[[Category:Lorentzian manifolds]]