|
Grassmann Graph
In graph theory, Grassmann graphs are a special class of simple graphs defined from systems of subspaces. The vertices of the Grassmann graph are the -dimensional subspaces of an -dimensional vector space over a finite field of order ; two vertices are adjacent when their intersection is -dimensional. Many of the parameters of Grassmann graphs are -analogs of the parameters of Johnson graphs, and Grassmann graphs have several of the same graph properties as Johnson graphs. Graph-theoretic properties * is isomorphic to . * For all , the intersection of any pair of vertices at distance is -dimensional. * The clique number of is given by an expression in terms its least and greatest eigenvalues and : ::\omega \left ( J_q(n,k) \right ) = 1 - \frac Automorphism group There is a distance-transitive subgroup of \operatorname(J_q(n, k)) isomorphic to the projective linear group \operatorname(n, q). In fact, unless n = 2k or k \in \, \operatorname(J_q(n,k)) \operatornam ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hermann Grassmann
Hermann Günther Grassmann (german: link=no, Graßmann, ; 15 April 1809 – 26 September 1877) was a German polymath known in his day as a linguist and now also as a mathematician. He was also a physicist, general scholar, and publisher. His mathematical work was little noted until he was in his sixties. Biography Hermann Grassmann was the third of 12 children of Justus Günter Grassmann, an ordained minister who taught mathematics and physics at the Stettin Gymnasium, where Hermann was educated. Grassmann was an undistinguished student until he obtained a high mark on the examinations for admission to Prussian universities. Beginning in 1827, he studied theology at the University of Berlin, also taking classes in classical languages, philosophy, and literature. He does not appear to have taken courses in mathematics or physics. Although lacking university training in mathematics, it was the field that most interested him when he returned to Stettin in 1830 after completing h ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Q-analog
In mathematics, a ''q''-analog of a theorem, identity or expression is a generalization involving a new parameter ''q'' that returns the original theorem, identity or expression in the limit as . Typically, mathematicians are interested in ''q''-analogs that arise naturally, rather than in arbitrarily contriving ''q''-analogs of known results. The earliest ''q''-analog studied in detail is the basic hypergeometric series, which was introduced in the 19th century.Exton, H. (1983), ''q-Hypergeometric Functions and Applications'', New York: Halstead Press, Chichester: Ellis Horwood, 1983, , , ''q''-analogues are most frequently studied in the mathematical fields of combinatorics and special functions. In these settings, the limit is often formal, as is often discrete-valued (for example, it may represent a prime power). ''q''-analogs find applications in a number of areas, including the study of fractals and multi-fractal measures, and expressions for the entropy of chaotic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Grassmannian
In mathematics, the Grassmannian is a space that parameterizes all -Dimension, dimensional linear subspaces of the -dimensional vector space . For example, the Grassmannian is the space of lines through the origin in , so it is the same as the projective space of one dimension lower than . When is a real or complex vector space, Grassmannians are compact space, compact smooth manifolds. In general they have the structure of a smooth algebraic variety, of dimension k(n-k). The earliest work on a non-trivial Grassmannian is due to Julius Plücker, who studied the set of projective lines in projective 3-space, equivalent to and parameterized them by what are now called Plücker coordinates. Hermann Grassmann later introduced the concept in general. Notations for the Grassmannian vary between authors; notations include , , , or to denote the Grassmannian of -dimensional subspaces of an -dimensional vector space . Motivation By giving a collection of subspaces of some vecto ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Distance-regular Graph
In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and . Every distance-transitive graph is distance-regular. Indeed, distance-regular graphs were introduced as a combinatorial generalization of distance-transitive graphs, having the numerical regularity properties of the latter without necessarily having a large automorphism group. Intersection arrays It turns out that a graph G of diameter d is distance-regular if and only if there is an array of integers \ such that for all 1 \leq j \leq d , b_j gives the number of neighbours of u at distance j+1 from v and c_j gives the number of neighbours of u at distance j - 1 from v for any pair of vertices u and v at distance j on G . The array of integers characterizing a distance-regular graph is known as its intersection array. Cos ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Eigenvalue
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted by \lambda, is the factor by which the eigenvector is scaled. Geometrically, an eigenvector, corresponding to a real nonzero eigenvalue, points in a direction in which it is stretched by the transformation and the eigenvalue is the factor by which it is stretched. If the eigenvalue is negative, the direction is reversed. Loosely speaking, in a multidimensional vector space, the eigenvector is not rotated. Formal definition If is a linear transformation from a vector space over a field into itself and is a nonzero vector in , then is an eigenvector of if is a scalar multiple of . This can be written as T(\mathbf) = \lambda \mathbf, where is a scalar in , known as the eigenvalue, characteristic value, or characteristic root ass ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clique Number
In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied. Although the study of complete subgraphs goes back at least to the graph-theoretic reformulation of Ramsey theory by , the term ''clique'' comes from , who used complete subgraphs in social networks to model cliques of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in bioinf ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Isomorphism
In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H'' : f \colon V(G) \to V(H) such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) are adjacent in ''H''. This kind of bijection is commonly described as "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection. If an isomorphism exists between two graphs, then the graphs are called isomorphic and denoted as G\simeq H. In the case when the bijection is a mapping of a graph onto itself, i.e., when ''G'' and ''H'' are one and the same graph, the bijection is called an automorphism of ''G''. If a graph is finite, we can prove it to be bijective by showing it is one-one/onto; no need to show both. Graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes. A set of graphs isomorphic to each ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Property
In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.. Definitions While graph drawing and graph representation are valid topics in graph theory, in order to focus only on the abstract structure of graphs, a graph property is defined to be a property preserved under all possible isomorphisms of a graph. In other words, it is a property of the graph itself, not of a specific drawing or representation of the graph. Informally, the term "graph invariant" is used for properties expressed quantitatively, while "property" usually refers to descriptive characterizations of graphs. For example, the statement "graph does not have vertices of degree 1" is a "property" while "the number of vertices of degree 1 in a graph" is an "invariant". More formally, a graph property is a class of graphs with the property that any two isomorphic gra ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Johnson Graph
Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph J(n,k) are the k-element subsets of an n-element set; two vertices are adjacent when the intersection of the two vertices (subsets) contains (k-1)-elements.. Both Johnson graphs and the closely related Johnson scheme are named after Selmer M. Johnson. Special cases *J(n,1) is the complete graph . *J(4,2) is the octahedral graph. *J(5,2) is the complement graph of the Petersen graph, hence the line graph of . More generally, for all n, the Johnson graph J(n,2) is the complement of the Kneser graph K(n,2). Graph-theoretic properties * J(n,k) is isomorphic to J(n,n-k). * For all 0 \leq j \leq \operatorname(J(n,k)), any pair of vertices at distance j share k-j elements in common. * J(n,k) is Hamilton-connected, meaning that every pair of vertices forms the endpoints of a Hamiltonian path in the graph. In particular this means that it has a Hamiltonian cycle. * It ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Intersection Number (graph Theory)
In the mathematical field of graph theory, the intersection number of a graph G=(V,E) is the smallest number of elements in a representation of G as an intersection graph of finite sets. In such a representation, each vertex is represented as a set, and two vertices are connected by an edge whenever their sets have a common element. Equivalently, the intersection number is the smallest number of cliques needed to cover all of the edges of G. A set of cliques that cover all edges of a graph is called a clique edge cover or edge clique cover, or even just a clique cover, although the last term is ambiguous: a clique cover can also be a set of cliques that cover all vertices of a graph. Sometimes "covering" is used in place of "cover". As well as being called the intersection number, the minimum number of these cliques has been called the ''R''-content, edge clique cover number, or clique cover number. The problem of computing the intersection number has been called the intersection ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Distance-transitive Graph
In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices and at any distance , and any other two vertices and at the same distance, there is an automorphism of the graph that carries to and to . Distance-transitive graphs were first defined in 1971 by Norman L. Biggs and D. H. Smith. A distance-transitive graph is interesting partly because it has a large automorphism group. Some interesting finite groups are the automorphism groups of distance-transitive graphs, especially of those whose diameter is 2. Examples Some first examples of families of distance-transitive graphs include: * The Johnson graphs. * The Grassmann graphs. * The Hamming Graphs. * The folded cube graphs. * The square rook's graphs. * The hypercube graphs. * The Livingstone graph. Classification of cubic distance-transitive graphs After introducing them in 1971, Biggs and Smith showed that there are only 12 finite trivalent ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Finite Field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are given by the integers mod when is a prime number. The ''order'' of a finite field is its number of elements, which is either a prime number or a prime power. For every prime number and every positive integer there are fields of order p^k, all of which are isomorphic. Finite fields are fundamental in a number of areas of mathematics and computer science, including number theory, algebraic geometry, Galois theory, finite geometry, cryptography and coding theory. Properties A finite field is a finite set which is a field; this means that multiplication, addition, subtraction and division (excluding division by zero) are ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
