Grassmann graph

Grassmann graph
Grassmann graph
Named after	Hermann Grassmann
Vertices
Edges
Diameter	min(k, n – k)
Properties	Distance-transitive ; Connected
Notation	Jq(n,k)
	Table of graphs and parameters

Last updated August 15, 2024

In graph theory, Grassmann graphs are a special class of simple graphs defined from systems of subspaces. The vertices of the Grassmann graph $J q (n, k)$ are the $k$ -dimensional subspaces of an $n$ -dimensional vector space over a finite field of order $q$ ; two vertices are adjacent when their intersection is $(k - 1)$ -dimensional.

Graph-theoretic properties

$J q (n, k)$ is isomorphic to $J q (n, n - k)$ .
For all $0 \leq d \leq diam(J q (n, k))$ , the intersection of any pair of vertices at distance $d$ is $(k - d)$ -dimensional.
The clique number of $J q (n, k)$ is given by an expression in terms its least and greatest eigenvalues $λ min$ and $λ max$ :

\omega \left(J_{q}(n,k)\right)=1-{\frac {\lambda _{\max }}{\lambda _{\min }}}

^{[ citation needed ]}

Automorphism group

There is a distance-transitive subgroup of $\operatorname {Aut} (J_{q}(n,k))$ isomorphic to the projective linear group $\operatorname {P\Gamma L} (n,q)$ .^{[ citation needed ]}

In fact, unless $n=2k$ or $k\in \{1,n-1\}$ , $\operatorname {Aut} (J_{q}(n,k))\cong \operatorname {P\Gamma L} (n,q)$ ; otherwise $\operatorname {Aut} (J_{q}(n,k))\cong \operatorname {P\Gamma L} (n,q)\times C_{2}$ or $\operatorname {Aut} (J_{q}(n,k))\cong \operatorname {Sym} ([n]_{q})$ respectively.^[1]

Intersection array

As a consequence of being distance-transitive, $J_{q}(n,k)$ is also distance-regular. Letting $d$ denote its diameter, the intersection array of $J_{q}(n,k)$ is given by $\left\{b_{0},\ldots ,b_{d-1};c_{1},\ldots c_{d}\right\}$ where:

$b_{j}:=q^{2j+1}[k-j]_{q}[n-k-j]_{q}$ for all $0\leq j<d$ .
$c_{j}:=([j]_{q})^{2}$ for all $0<j\leq d$ .

Spectrum

The characteristic polynomial of $J_{q}(n,k)$ is given by

\varphi (x):=\prod \limits _{j=0}^{\operatorname {diam} (J_{q}(n,k))}\left(x-\left(q^{j+1}[k-j]_{q}[n-k-j]_{q}-[j]_{q}\right)\right)^{\left({\binom {n}{j}}_{q}-{\binom {n}{j-1}}_{q}\right)}

.^[1]

Related Research Articles

<span class="mw-page-title-main">Negative binomial distribution</span> Probability distribution

In probability theory and statistics, the negative binomial distribution is a discrete probability distribution that models the number of failures in a sequence of independent and identically distributed Bernoulli trials before a specified (non-random) number of successes occurs. For example, we can define rolling a 6 on some dice as a success, and rolling any other number as a failure, and ask how many failure rolls will occur before we see the third success. In such a case, the probability distribution of the number of failures that appear will be a negative binomial distribution.

In topology, a covering or covering projection is a map between topological spaces that, intuitively, locally acts like a projection of multiple copies of a space onto itself. In particular, coverings are special types of local homeomorphisms. If $is a covering, is said to be a covering space or cover of, and is said to be the base of the covering, or simply the base . By abuse of terminology, and may sometimes be called covering spaces as well. Since coverings are local homeomorphisms, a covering space is a special kind of étale space.$

In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form $of one complex variable z; here the coefficients a, b, c, d are complex numbers satisfying ad - bc \neq 0 .$

In mathematics, the isoperimetric inequality is a geometric inequality involving the perimeter of a set and its volume. In $-dimensional space the inequality lower bounds the surface area or perimeter of a set by its volume,$

In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem, and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing expander graphs.

In mathematics the spin group, denoted Spin(n), is a Lie group whose underlying manifold is the double cover of the special orthogonal group SO(n) = SO(n, R), such that there exists a short exact sequence of Lie groups (when n ≠ 2)

<span class="mw-page-title-main">Holonomy</span> Concept in differential geometry

In differential geometry, the holonomy of a connection on a smooth manifold is a general geometrical consequence of the curvature of the connection measuring the extent to which parallel transport around closed loops fails to preserve the geometrical data being transported. For flat connections, the associated holonomy is a type of monodromy and is an inherently global notion. For curved connections, holonomy has nontrivial local and global features.

In graph theory, the resistance distance between two vertices of a simple, connected graph, $G$ , is equal to the resistance between two equivalent points on an electrical network, constructed so as to correspond to $G$ , with each edge being replaced by a resistance of one ohm. It is a metric on graphs.

<span class="mw-page-title-main">Barycentric coordinate system</span> Coordinate system that is defined by points instead of vectors

In geometry, a barycentric coordinate system is a coordinate system in which the location of a point is specified by reference to a simplex. The barycentric coordinates of a point can be interpreted as masses placed at the vertices of the simplex, such that the point is the center of mass of these masses. These masses can be zero or negative; they are all positive if and only if the point is inside the simplex.

In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a finite-dimensional graph, the discrete Laplace operator is more commonly called the Laplacian matrix.

In mathematics, Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph $are the -element subsets of an -element set; two vertices are adjacent when the intersection of the two vertices (subsets) contains -elements. Both Johnson graphs and the closely related Johnson scheme are named after Selmer M. Johnson.$

In mathematics, in the field of algebraic geometry, the period mapping relates families of Kähler manifolds to families of Hodge structures.

In mathematics, the Abel–Jacobi map is a construction of algebraic geometry which relates an algebraic curve to its Jacobian variety. In Riemannian geometry, it is a more general construction mapping a manifold to its Jacobi torus. The name derives from the theorem of Abel and Jacobi that two effective divisors are linearly equivalent if and only if they are indistinguishable under the Abel–Jacobi map.

In the mathematical subject of geometric group theory, the Culler–Vogtmann Outer space or just Outer space of a free group F_n is a topological space consisting of the so-called "marked metric graph structures" of volume 1 on F_n. The Outer space, denoted X_n or CV_n, comes equipped with a natural action of the group of outer automorphisms Out(F_n) of F_n. The Outer space was introduced in a 1986 paper of Marc Culler and Karen Vogtmann, and it serves as a free group analog of the Teichmüller space of a hyperbolic surface. Outer space is used to study homology and cohomology groups of Out(F_n) and to obtain information about algebraic, geometric and dynamical properties of Out(F_n), of its subgroups and individual outer automorphisms of F_n. The space X_n can also be thought of as the set of F_n-equivariant isometry types of minimal free discrete isometric actions of F_n on R-treesT such that the quotient metric graph T/F_n has volume 1.

Formalized by John Tukey, the Tukey lambda distribution is a continuous, symmetric probability distribution defined in terms of its quantile function. It is typically used to identify an appropriate distribution and not used in statistical models directly.

In mathematics, Minkowski's second theorem is a result in the geometry of numbers about the values taken by a norm on a lattice and the volume of its fundamental cell.

In algebraic geometry, the Quot scheme is a scheme parametrizing sheaves on a projective scheme. More specifically, if X is a projective scheme over a Noetherian scheme S and if F is a coherent sheaf on X, then there is a scheme $whose set of T -points is the set of isomorphism classes of the quotients of that are flat over T . The notion was introduced by Alexander Grothendieck.$

In coding theory, Zemor's algorithm, designed and developed by Gilles Zemor, is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of Sipser and Spielman.

Maximal entropy random walk (MERW) is a popular type of biased random walk on a graph, in which transition probabilities are chosen accordingly to the principle of maximum entropy, which says that the probability distribution which best represents the current state of knowledge is the one with largest entropy. While standard random walk chooses for every vertex uniform probability distribution among its outgoing edges, locally maximizing entropy rate, MERW maximizes it globally by assuming uniform probability distribution among all paths in a given graph.

In mathematics, a quasirandom group is a group that does not contain a large product-free subset. Such groups are precisely those without a small non-trivial irreducible representation. The namesake of these groups stems from their connection to graph theory: bipartite Cayley graphs over any subset of a quasirandom group are always bipartite quasirandom graphs.

References

1 2 Brouwer, Andries E. (1989). Distance-Regular Graphs. Cohen, Arjeh M., Neumaier, Arnold. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642743436. OCLC 851840609.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:0-1] 1 2 Brouwer, Andries E. (1989). Distance-Regular Graphs. Cohen, Arjeh M., Neumaier, Arnold. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642743436. OCLC 851840609.

[1]