Extremal matrices for the Bruhat-graph order.

We consider the class A s y m 0 (n , k) of symmetric (0 , 1) -matrices with zero trace and constant row sums k which can be identified with the class of the adjacency matrices of k-regular undirected graphs. In a previous paper, two partial orders, the Bruhat and the Bruhat-graph order, have been introduced in this class. In fact, when k = 1 or k = 2, it was shown that the two orders coincide, while for k ≥ 3 the two orders are distinct. In this paper we give general properties of minimal and maximal matrices for these orders on A s y m 0 (n , k) and study the minimal and maximal matrices when k = 1, 2 or 3. [ABSTRACT FROM AUTHOR]