|
Tutte–Coxeter Graph
In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eight-cage or Cremona–Richmond graph is a 3-regular graph with 30 vertices and 45 edges. As the unique smallest cubic graph of girth 8, it is a cage and a Moore graph. It is bipartite, and can be constructed as the Levi graph of the generalized quadrangle ''W''2 (known as the Cremona–Richmond configuration). The graph is named after William Thomas Tutte and H. S. M. Coxeter; it was discovered by Tutte (1947) but its connection to geometric configurations was investigated by both authors in a pair of jointly published papers (Tutte 1958; Coxeter 1958a). All the cubic distance-regular graphs are known. The Tutte–Coxeter is one of the 13 such graphs. It has crossing number 13, book thickness 3 and queue number 2.Wolz, Jessica; ''Engineering Linear Layouts with SAT.'' Master Thesis, University of Tübingen, 2018 Constructions and automorphisms A particularly simple combinatorial construction of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tutte Eight Cage
William Thomas Tutte Order of Canada, OC Royal Society, FRS Royal Society of Canada, FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian cryptanalysis, codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a major Nazi Germany, Nazi German cipher system which was used for top-secret communications within the Wehrmacht High Command. The high-level, strategic nature of the intelligence obtained from Tutte's crucial breakthrough, in the bulk decrypting of Lorenz-enciphered messages specifically, contributed greatly, and perhaps even decisively, to the defeat of Nazi Germany. He also had a number of significant mathematical accomplishments, including foundation work in the fields of graph theory and matroid theory. Tutte's research in the field of graph theory proved to be of remarkable importance. At a time when graph theory was still a primitive subject, Tutte commenced the study of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cremona–Richmond Configuration
In mathematics, the Cremona–Richmond configuration is a configuration of 15 lines and 15 points, having 3 points on each line and 3 lines through each point, and containing no triangles. It was studied by and . It is a generalized quadrangle with parameters (2,2). Its Levi graph is the Tutte–Coxeter graph. Symmetry The points of the Cremona–Richmond configuration may be identified with the 15=\tbinom unordered pairs of elements of a six-element set; these pairs are called ''duads''. Similarly, the lines of the configuration may be identified with the 15 ways of partitioning the same six elements into three pairs; these partitions are called ''synthemes''. Identified in this way, a point of the configuration is incident to a line of the configuration if and only if the duad corresponding to the point is one of the three pairs in the syntheme corresponding to the line. The symmetric group of all permutations of the six elements underlying this system of duads and synthemes act ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Symplectic Vector Space
In mathematics, a symplectic vector space is a vector space ''V'' over a field ''F'' (for example the real numbers R) equipped with a symplectic bilinear form. A symplectic bilinear form is a mapping that is ; Bilinear: Linear in each argument separately; ; Alternating: holds for all ; and ; Non-degenerate: for all implies that . If the underlying field has characteristic not 2, alternation is equivalent to skew-symmetry. If the characteristic is 2, the skew-symmetry is implied by, but does not imply alternation. In this case every symplectic form is a symmetric form, but not vice versa. Working in a fixed basis, ''ω'' can be represented by a matrix. The conditions above are equivalent to this matrix being skew-symmetric, nonsingular, and hollow (all diagonal entries are zero). This should not be confused with a symplectic matrix, which represents a symplectic transformation of the space. If ''V'' is finite-dimensional, then its dimension must necessarily be even since ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Building (mathematics)
In mathematics, a building (also Tits building, named after Jacques Tits) is a combinatorial and geometric structure which simultaneously generalizes certain aspects of flag manifolds, finite projective planes, and Riemannian symmetric spaces. Buildings were initially introduced by Jacques Tits as a means to understand the structure of exceptional groups of Lie type. The more specialized theory of Bruhat–Tits buildings (named also after François Bruhat) plays a role in the study of -adic Lie groups analogous to that of the theory of symmetric spaces in the theory of Lie groups. Overview The notion of a building was invented by Jacques Tits as a means of describing simple algebraic groups over an arbitrary field. Tits demonstrated how to every such group one can associate a simplicial complex with an action of , called the spherical building of . The group imposes very strong combinatorial regularity conditions on the complexes that can arise in this fashion. By tre ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Outer Automorphism
In mathematics, the outer automorphism group of a group, , is the quotient, , where is the automorphism group of and ) is the subgroup consisting of inner automorphisms. The outer automorphism group is usually denoted . If is trivial and has a trivial center, then is said to be complete. An automorphism of a group which is not inner is called an outer automorphism. The cosets of with respect to outer automorphisms are then the elements of ; this is an instance of the fact that quotients of groups are not, in general, (isomorphic to) subgroups. If the inner automorphism group is trivial (when a group is abelian), the automorphism group and outer automorphism group are naturally identified; that is, the outer automorphism group does act on the group. For example, for the alternating group, , the outer automorphism group is usually the group of order 2, with exceptions noted below. Considering as a subgroup of the symmetric group, , conjugation by any odd permutation is an oute ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Inner Automorphism
In abstract algebra an inner automorphism is an automorphism of a group, ring, or algebra given by the conjugation action of a fixed element, called the ''conjugating element''. They can be realized via simple operations from within the group itself, hence the adjective "inner". These inner automorphisms form a subgroup of the automorphism group, and the quotient of the automorphism group by this subgroup is defined as the outer automorphism group. Definition If is a group and is an element of (alternatively, if is a ring, and is a unit), then the function :\begin \varphi_g\colon G&\to G \\ \varphi_g(x)&:= g^xg \end is called (right) conjugation by (see also conjugacy class). This function is an endomorphism of : for all x_1,x_2\in G, :\varphi_g(x_1 x_2) = g^ x_1 x_2g = \left(g^ x_1 g\right)\left(g^ x_2 g\right) = \varphi_g(x_1)\varphi_g(x_2), where the second equality is given by the insertion of the identity between x_1 and x_2. Furthermore, it has a left and ri ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Automorphism
In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity. Formally, an automorphism of a graph is a permutation of the vertex set , such that the pair of vertices form an edge if and only if the pair also form an edge. That is, it is a graph isomorphism from to itself. Automorphisms may be defined in this way both for directed graphs and for undirected graphs. The composition of two automorphisms is another automorphism, and the set of automorphisms of a given graph, under the composition operation, forms a group, the automorphism group of the graph. In the opposite direction, by Frucht's theorem, all groups can be represented as the automorphism group of a connected graph – indeed, of a cubic graph. Computational complexity Constructing the automorphism group is at least as difficult (in terms of its computational complexity) as solving the graph is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Group (mathematics)
In mathematics, a group is a Set (mathematics), set and an Binary operation, operation that combines any two Element (mathematics), elements of the set to produce a third element of the set, in such a way that the operation is Associative property, associative, an identity element exists and every element has an Inverse element, inverse. These three axioms hold for Number#Main classification, number systems and many other mathematical structures. For example, the integers together with the addition operation form a group. The concept of a group and the axioms that define it were elaborated for handling, in a unified way, essential structural properties of very different mathematical entities such as numbers, geometric shapes and polynomial roots. Because the concept of groups is ubiquitous in numerous areas both within and outside mathematics, some authors consider it as a central organizing principle of contemporary mathematics. In geometry groups arise naturally in the study of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Symmetric Graph
In the mathematical field of graph theory, a graph is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices and of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 and f(v_1) = v_2. In other words, a graph is symmetric if its automorphism group acts transitively on ordered pairs of adjacent vertices (that is, upon edges considered as having a direction). Such a graph is sometimes also called -transitive or flag-transitive. By definition (ignoring and ), a symmetric graph without isolated vertices must also be vertex-transitive. Since the definition above maps one edge to another, a symmetric graph must also be edge-transitive. However, an edge-transitive graph need not be symmetric, since might map to , but not to . Star graphs are a simple example of being edge-transitive without being vertex-transitive or symmetric. As a further example, semi-symmetric graphs are edge-transitive and regular, but not vertex-transitiv ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Perfect Matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly one edge in . A perfect matching is also called a 1-factor; see Graph factorization for an explanation of this term. In some literature, the term complete matching is used. Every perfect matching is a maximum-cardinality matching, but the opposite is not true. For example, consider the following graphs: : In graph (b) there is a perfect matching (of size 3) since all 6 vertices are matched; in graphs (a) and (c) there is a maximum-cardinality matching (of size 2) which is not perfect, since some vertices are unmatched. A perfect matching is also a minimum-size edge cover. If there is a perfect matching, then both the matching number and the edge cover number equal . A perfect matching can only occur when the graph has an even num ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complete Graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction). Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete graphs, with their vertices placed on the points of a regular polygon, had already appeared in the 13th century, in the work of Ramon Llull. Such a drawing is sometimes referred to as a mystic rose. Properties The complete graph on vertices is denoted by . Some sources claim that the letter in this notation stands for the German word , but the German name for a complete graph, , does not contain the letter , and other sources state that the notation honors the contributions of Kazimierz Kuratowski to graph theory. has edges (a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Queue Number
In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings. Definition A queue layout of a given graph is defined by a total ordering of the vertices of the graph together with a partition of the edges into a number of "queues". The set of edges in each queue is required to avoid edges that are properly nested: if and are two edges in the same queue, then it should not be possible to have in the vertex ordering. The queue number of a graph is the minimum number of queues in a queue layout.. Equivalently, from a queue layout, one could process the edges in a single queue using a queue data structure, by considering the vertices in their given ordering, and when reaching a vertex, dequeueing all edges for which it is the second endpoint followed by enqueueing all edges for which it is the first en ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
