Combinatorics of Fulton's essential set (Q1816468)

Our first result, in Section 3, is an elementary algorithm that retrieves a permutation from its ranked essential set. The algorithm is flexible, in that the input set may be bigger and include any other squares, as well as be smaller as long as it contains a certain ``core'' of the essential set. By this flexibility, the algorithm ought to be useful as a practical tool. In general, the core is much smaller than the essential set, so this is a significant strengthening. \textit{W. Fulton} [Duke Math. J. 65, No. 3, 381-420 (1992; Zbl 0788.14044)] used the essential sets mainly for vexillary (2143-avoiding) permutations. He gave a characterization of the ranked essential set for vexillary permutations, which may be expressed by three simple conditions, and he pointed out that it might be useful to have an analogous characterization of the ranked sets of squares that arise as ranked essential sets of all permutations. As an application of the algorithm, we are able to state such a characterization, which keeps two of Fulton's three conditions for the vexillary case and replaces the third one with a new and, alas, more complicated condition. We also remark on how the algorithm can be used directly to determine if a given ranked set contains the essential set of a permutation. This is done in Section 4. In Section 5, we use a combinatorial technique to describe several classes of permutations in terms of their essential set. For example, the Baxter permutations are precisely those whose essential set has at most one square in each row and column. Another example is 321-avoiding vexillary permutations, which can be described as having the essential set entirely contained in one row or in one column. As a corollary we obtain a direct interpretation of the formula for the number of 321-avoiding vexillary permutations of \textit{S. C. Billey}, \textit{W. Jockusch} and \textit{R. P. Stanley} [J. Algebr. Comb. 2, No. 4, 345-374 (1993; Zbl 0790.05093)]. In Section 6 we discuss how some of Fulton's results on minor ideals and the essential set can be generalized to higher dimensions, that is, if we work not with matrices but with higher-dimensional arrays of variable entries. It turns out that with natural definitions of permutations, determinants, and essential sets, it is true also in this general situation that a permutation is determined by its essential set, and that the minor ideal defined by the permutation is generated by the minors stemming from the essential set. There are several interesting problems left open, and we collect some of them at the end of the paper. In another paper [Electron. J. Comb. 2, R6, 18 p. (1995; Zbl 0814.05006)], the same authors have studied various enumerative aspects of the essential set.