Dowling geometry
Encyclopedia
In combinatorial
mathematics
, a Dowling geometry, named after Thomas A. Dowling, is a matroid
associated with a group
. There is a Dowling geometry of each rank for each group. If the rank is at least 3, the Dowling geometry uniquely determines the group. Dowling geometries have a role in matroid theory as universal objects (Kahn and Kung, 1982); in that respect they are analogous to projective geometries
, but based on groups instead of field
s like the latter.
A Dowling lattice is the lattice of closed sets
associated with a Dowling geometry. The lattice and the geometry are mathematically equivalent: knowing either one determines the other. Dowling lattices, and by implication Dowling geometries, were introduced by Dowling (1973a,b).
A Dowling lattice or geometry of rank n of a group G is often denoted Qn(G).
F. It is the set of all those subspaces of the vector space
F n that are generated by subsets of the set E that consists of vectors with at most two nonzero coordinates. The corresponding Dowling geometry is the set of 1-dimensional vector subspaces generated by the elements of E.
In his second paper (1973b) Dowling gave an intrinsic definition of the rank-n Dowling lattice of any finite group G. Let S be the set {1,...,n}. A G-labelled set (T, α) is a set T together with a function
α: T --> G. Two G-labelled sets, (T, α) and (T, β), are equivalent if there is a group element, g, such that β = gα.
An equivalence class is denoted [T, α].
A partial G-partition of S is a set γ = {[B1,α1], ..., [Bk,αk]} of equivalence classes of G-labelled sets such that B1, ..., Bk are nonempty subsets of S that are pairwise disjoint. (k may equal 0.)
A partial G-partition γ is said to be ≤ another one, γ*, if
This gives a partial ordering
of the set of all partial G-partitions of S. The resulting partially ordered set is the Dowling lattice Qn(G).
The definitions are valid even if F or G is infinite, though Dowling mentioned only finite fields and groups.
s.
Take n vertices, and between each pair of vertices, v and w, take edges labelled by all possible elements of the group G. The edges are oriented, in that, if the label in the direction from v to w is the group element g, then the label of the same edge in the opposite direction, from w to v, is g−1. The label of an edge therefore depends on the direction of the edge; such labels are called gains. Also add to each vertex a loop whose gain is any value other than 1. (1 is the group identity element
.) This gives a graph which is called GKno (note the raised circle).
A cycle
in the graph then has a gain. The cycle is a sequence of edges, e1e2···ek. Suppose the gains of these edges, in a fixed direction around the cycle, are g1, g2, ..., gk. Then the gain of the cycle is the product, g1g2···gk. The value of this gain is not completely well defined, since it depends on the direction chosen for the cycle and on which is called the "first" edge of the cycle. What is independent of these choices is the answer to the following question: is the gain equal to 1 or not? If it equals 1 under one set of choices, then it is also equal to 1 under all sets of choices.
To define the Dowling geometry, we specify the circuits (minimal dependent sets). The circuits of the matroid are
Thus, the Dowling geometry Qn(G) is the frame matroid
or (bias matroid) of the gain graph GKno (the raised circle denotes the presence of loops).
Other, equivalent definitions are described in the article on gain graph
s.
an exceptionally simple formula for any geometric lattice.
; see Dowling (1973b). This does not generalize in a straightforward way to higher ranks. There is a generalization due to Zaslavsky (t.a.) that involves n-ary quasigroups.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a Dowling geometry, named after Thomas A. Dowling, is a matroid
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
associated with a group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
. There is a Dowling geometry of each rank for each group. If the rank is at least 3, the Dowling geometry uniquely determines the group. Dowling geometries have a role in matroid theory as universal objects (Kahn and Kung, 1982); in that respect they are analogous to projective geometries
Projective geometry
In mathematics, projective geometry is the study of geometric properties that are invariant under projective transformations. This means that, compared to elementary geometry, projective geometry has a different setting, projective space, and a selective set of basic geometric concepts...
, but based on groups instead of field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
s like the latter.
A Dowling lattice is the lattice of closed sets
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
associated with a Dowling geometry. The lattice and the geometry are mathematically equivalent: knowing either one determines the other. Dowling lattices, and by implication Dowling geometries, were introduced by Dowling (1973a,b).
A Dowling lattice or geometry of rank n of a group G is often denoted Qn(G).
The original definitions
In his first paper (1973a) Dowling defined the rank-n Dowling lattice of the multiplicative group of a finite fieldFinite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
F. It is the set of all those subspaces of the vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
F n that are generated by subsets of the set E that consists of vectors with at most two nonzero coordinates. The corresponding Dowling geometry is the set of 1-dimensional vector subspaces generated by the elements of E.
In his second paper (1973b) Dowling gave an intrinsic definition of the rank-n Dowling lattice of any finite group G. Let S be the set {1,...,n}. A G-labelled set (T, α) is a set T together with a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
α: T --> G. Two G-labelled sets, (T, α) and (T, β), are equivalent if there is a group element, g, such that β = gα.
An equivalence class is denoted [T, α].
A partial G-partition of S is a set γ = {[B1,α1], ..., [Bk,αk]} of equivalence classes of G-labelled sets such that B1, ..., Bk are nonempty subsets of S that are pairwise disjoint. (k may equal 0.)
A partial G-partition γ is said to be ≤ another one, γ*, if
- every block of the second is a union of blocks of the first, and
- for each Bi contained in B*j , αi is equivalent to the restriction of α*j to domain Bi .
This gives a partial ordering
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
of the set of all partial G-partitions of S. The resulting partially ordered set is the Dowling lattice Qn(G).
The definitions are valid even if F or G is infinite, though Dowling mentioned only finite fields and groups.
Graphical definitions
A graphical definition was then given by Doubilet, Rota, and Stanley (1972). We give the slightly simpler (but essentially equivalent) graphical definition of Zaslavsky (1991), expressed in terms of gain graphGain graph
A gain graph is a graph whose edges are labelled "invertibly", or "orientably", by elements of a group G. This means that, if an edge e in one direction has label g , then in the other direction it has label g −1...
s.
Take n vertices, and between each pair of vertices, v and w, take edges labelled by all possible elements of the group G. The edges are oriented, in that, if the label in the direction from v to w is the group element g, then the label of the same edge in the opposite direction, from w to v, is g−1. The label of an edge therefore depends on the direction of the edge; such labels are called gains. Also add to each vertex a loop whose gain is any value other than 1. (1 is the group identity element
Identity element
In mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...
.) This gives a graph which is called GKno (note the raised circle).
A cycle
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
in the graph then has a gain. The cycle is a sequence of edges, e1e2···ek. Suppose the gains of these edges, in a fixed direction around the cycle, are g1, g2, ..., gk. Then the gain of the cycle is the product, g1g2···gk. The value of this gain is not completely well defined, since it depends on the direction chosen for the cycle and on which is called the "first" edge of the cycle. What is independent of these choices is the answer to the following question: is the gain equal to 1 or not? If it equals 1 under one set of choices, then it is also equal to 1 under all sets of choices.
To define the Dowling geometry, we specify the circuits (minimal dependent sets). The circuits of the matroid are
- the cycles whose gain is 1,
- the pairs of cycles with both gains not equal to 1, and which intersect in a single vertex and nothing else, and
- the theta graphs in which none of the three cycles has gain equal to 1.
Thus, the Dowling geometry Qn(G) is the frame matroid
Biased graph
In mathematics, a biased graph is a graph with a list of distinguished circles , such that if two circles in the list are contained in a theta graph, then so is the third circle of the theta graph...
or (bias matroid) of the gain graph GKno (the raised circle denotes the presence of loops).
Other, equivalent definitions are described in the article on gain graph
Gain graph
A gain graph is a graph whose edges are labelled "invertibly", or "orientably", by elements of a group G. This means that, if an edge e in one direction has label g , then in the other direction it has label g −1...
s.
Characteristic polynomial
One reason for interest in Dowling lattices is that the characteristic polynomial is very simple. If L is the Dowling lattice of rank n of a finite group G having m elements, thenan exceptionally simple formula for any geometric lattice.
Generalizations
There is also a Dowling geometry, of rank 3 only, associated with each quasigroupQuasigroup
In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure resembling a group in the sense that "division" is always possible...
; see Dowling (1973b). This does not generalize in a straightforward way to higher ranks. There is a generalization due to Zaslavsky (t.a.) that involves n-ary quasigroups.