Abstract
A graph is called a pseudo-core if every endomorphism is either an automorphism or a colouring. In this paper, we show that every Grassmann graph $J_q(n,m)$ is a pseudo-core. Moreover, the Grassmann graph $J_q(n,m)$ is a core whenever $m$ and $n-m+1$ are not relatively prime, and $J_q(2pk-2, pk-1)$ is a core whenever $p,k\geq 2$.
Introduction
In algebraic graph theory, the study of endomorphisms—mappings from a graph to itself that preserve adjacency—reveals fundamental structural properties. A graph is defined as a core if all its endomorphisms are automorphisms (symmetries). If a graph can be mapped to a proper subgraph, it is not a core. A broader classification is the pseudo-core, where every endomorphism is either an automorphism or a coloring (a mapping to a complete graph). This paper addresses the classification of Grassmann graphs $J_q(n, m)$ within these categories, a problem central to both geometry and coding theory.
The Geometry of Grassmann Graphs
Grassmann graphs $J_q(n, m)$ are defined by vertices representing $m$-dimensional subspaces of an $n$-dimensional vector space over a finite field $GF(q)$. Two vertices are adjacent if their intersection has dimension $m-1$. These graphs are highly symmetric, but determining whether they are cores requires a deep analysis of their internal mappings.
Proving the Pseudo-Core Property
The central result of this research is that every Grassmann graph $J_q(n, m)$ is a pseudo-core. The authors achieve this by examining the structure of maximal cliques—the largest possible sets of mutually adjacent vertices. In $J_q(n, m)$, these cliques appear in two distinct forms:
- Stars: All subspaces containing a specific $(m-1)$-dimensional subspace.
- Tops: All subspaces contained within a specific $(m+1)$-dimensional subspace.
By analyzing how endomorphisms map these cliques to one another and employing induction on the dimension $n$, the authors demonstrate that any endomorphism that does not collapse the graph into a coloring must necessarily be an automorphism.
Conditions for Core Status
While all Grassmann graphs are pseudo-cores, their status as cores depends on the relationship between their dimensions and the underlying field size. The authors utilize cyclotomic polynomials and Gaussian binomial coefficients to identify specific conditions where $J_q(n, m)$ is a core:
- Divisibility Conditions: If $m$ and $n-m+1$ are not relatively prime, the graph is a core for sufficiently large $q$.
- Specific Dimensions: The graph $J_q(2k+1, 2)$ is a core for any $k \geq 2$.
- Higher Dimensions: $J_q(2pk-2, pk-1)$ is a core whenever $p, k \geq 2$.
Conversely, the paper provides a concrete counter-example in $J_2(4, 2)$. By showing that its chromatic number $\chi(G)$ equals its clique number $\omega(G)$ (both are 7), the authors prove it allows for a coloring endomorphism, making it a pseudo-core that is specifically not a core.
Conclusion and Future Work
This work provides a significant step forward in the classification of symmetric graphs. However, several questions remain. The authors conjecture that $J_q(2k, 2)$ is never a core for any $q$, though a formal proof remains elusive. Additionally, the requirement for $q$ to be "sufficiently large" in certain theorems suggests that the relationship between field size and graph rigidity may be even deeper than currently understood. Future research will likely focus on removing these constraints and providing a complete characterization of core status across all dimensions.
Summary updated