On Algorithmic Study of Non-negative Posets of Corank at Most Two and their Coxeter-Dynkin Types

Abstract

Following the Coxeter spectral analysis of loop-free edge-bipartite graphs Δ and finite posets I, with n ≥ 2 vertices, introduced and developed in [SIAM J. Discrete Math., 27(2013), 827-854], we present a Coxeter spectral classification of finite posets I, with n ≥ 2 elements. Here we study the connected posets I that are non-negative of corank one or two, in the sense that the symmetric Gram matrix $\frac{1}{2}(C_I+C_I^{tr})\in {𝕄}_n(\mathbb{Q})$ is positive semi-definite of corank one or two, where C_I ∈ 𝕄 _n (ℤ) is the incidence matrix of I. We study such posets I by means of the Dynkin type Dyn _I and the Coxeter polynomial cox _I (t) := det(t · E − Cox _I ) ∈ ℤ[t], where Cox _I := −C_I · C^−tr _I ∈ 𝕄 _n (ℤ) is the Coxeter matrix of I.

Among other results, we develop an algorithmic technique that allows us to compute a complete list of such posets I, with |I| ≤ 16, their Dynkin types Dyn _I , and the Coxeter polynomials cox _I (t) ∈ ℤ[t]. We prove that, given a pair of such connected posets I and J, the incidence matrices C_I and C_J are ℤ-congruent if and only if cox _I (t) = cox _J (t) and Dyn _I = Dyn _J .