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 November 15, 2023

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)$ .

In fact, unless $n=2k$ or $k\in \{1,n-1\}$ , $\operatorname {Aut} (J_{q}(n,k))$ $≅$ $\operatorname {P\Gamma L} (n,q)$ ; otherwise $\operatorname {Aut} (J_{q}(n,k))$ $≅$ $\operatorname {P\Gamma L} (n,q)\times C_{2}$ or $\operatorname {Aut} (J_{q}(n,k))$ $≅$ $\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 a die 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 differential geometry, a Riemannian manifold or Riemannian space(M, g), so called after the German mathematician Bernhard Riemann, is a real, smooth manifold M equipped with a positive-definite inner product g_p on the tangent space T_pM at each point p.

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.

<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.

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 the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, the graph Laplacian matrix can be viewed as a matrix form of the negative discrete Laplace operator on a graph approximating the negative continuous Laplacian obtained by the finite difference method.

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, 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 F_n on R-treesT such that the quotient metric graph T/F_n has volume 1.

In mathematics, the Smith–Minkowski–Siegel mass formula is a formula for the sum of the weights of the lattices in a genus, weighted by the reciprocals of the orders of their automorphism groups. The mass formula is often given for integral quadratic forms, though it can be generalized to quadratic forms over any algebraic number field.

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 linear algebra, particularly projective geometry, a semilinear map between vector spaces V and W over a field K is a function that is a linear map "up to a twist", hence semi-linear, where "twist" means "field automorphism of K". Explicitly, it is a function T : V → W that is:

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.

N = 4 supersymmetric Yang–Mills (SYM) theory is a relativistic conformally invariant Lagrangian gauge theory describing fermions interacting via gauge field exchanges. In D=4 spacetime dimensions, N=4 is the maximal number of supersymmetries or supersymmetry charges.

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]