<ph f="cmex"> </ph><ph f="cmbx">Linear spaces, transversal polymatroids and ASL domains</ph>

Aldo Conca

Dipartimento di Matematica, Universita di Genova, Genova, Italy E-mail address : conca@dima.unige.it

1 Introduction

Let $K$  be an infinite field and $R=K\left[{x}_{1},...,{x}_{n}\right]$  be the polynomial ring. Let $V={V}_{1},...,{V}_{m}$  be a collection of vector spaces of linear forms. Denote by $A\left(V\right)$  the $K$  -subalgebra of $R$  generated by the elements of the product ${V}_{1}\cdots {V}_{m}$  . Our goal is to investigate the properties of the algebra $A\left(V\right)$  and the relations with two problems in algebraic combinatorics: White's and related conjectures on polymatroids and the study of integral posets.

Polymatroids

A finite subset $B$  of ${\mathbb{N}}^{n}$  is the base set of a discrete polymatroid $P$  if for every $v=\left({v}_{1},...,{v}_{n}\right),w=\left({w}_{1},...,{w}_{n}\right)\in B$  one has ${v}_{1}+\cdot \cdot \cdot +{v}_{n}={w}_{1}+\cdot \cdot \cdot +{w}_{n}$  and for all $i$  such that ${v}_{i}>{w}_{i}$  there exists a $j$  with ${v}_{j}<{w}_{j}$  and $v+{e}_{j}-{e}_{i}\in B$  . Here ${e}_{k}$  denotes the $k$  -th vector of the standard basis of ${\mathbb{N}}^{n}$  . The notion of discrete polymatroid is a generalization of the classical notion of matroid, see [9, 11, 18, 25. Associated with the base $B$  of a discrete polymatroid $P$  one has a $K$  -algebra $K\left[B\right]$  , called the base ring of $P$  , defined to be the $K$  -subalgebra of $R$  generated by the monomials ${x}^{v}$  with $v\in B$  . The algebra $K\left[B\right]$  is known to be normal and hence Cohen-Macaulay [11. White predicted in [26the shape of the defining equations of $K\left[B\right]$  as a quotient of a polynomial ring: they should the quadrics arising from the so-called symmetric exchange relations of the polymatroids. Herzog and Hibi [11did not “escape from the temptation” to ask whether $K\left[B\right]$  is defined by a Gröbner basis of quadrics and whether $K\left[B\right]$  is a Koszul algebra. These two questions are closely related to White's conjecture. This is because for any standard graded algebra $A$  with defining ideal $I$  , the existence of a Gröbner basis of quadrics for $I$  implies the Koszul property of $A$  which implies that $I$  is defined by quadrics.
If ${C}_{1},...,{C}_{m}$  are non-empty subsets of $\left\{1,...,n\right\}$  then the set of the vectors ${\sum }_{k=1}^{m}{e}_{{j}_{k}}$  with ${j}_{k}\in {C}_{k}$  is the base of a polymatroid. Polymatroids of this kind are called transversal. Therefore the base rings of transversal polymatroids are exactly the rings of type $A\left(V\right)$  where the spaces ${V}_{i}$  are generated by variables. For transversal polymatroids we prove that the base ring $K\left[B\right]$  is Koszul and describe the defining equations, see Section  3 . Indeed, $K\left[B\right]$  is defined as a quotient of a Segre product ${T}^{*}$  of polynomial rings by a Gröbner basis of linear binomial forms of ${T}^{*}$  .

ASL and integral posets

Algebras with straightening laws (ASL for short) on posets were introduced by De Concini, Eisenbud and Procesi [7, 10, see also [4. The abstract definition of ASL was inspired by earlier work of Hochster, Hodge, Laksov, Musili, Rota, and Seshadri among others. It was motivated by the existence of many families of classical algebras, such as coordinate rings of Grassmannians and their Schubert subvarieties and various kinds of determinantal rings, which could be treated within that frame. We recall in  5.4 the definition of homogeneous ASL and in  5.5 a well-known characterization of them in terms of revlex Gröbner bases.
A finite poset $H$  is integral (with respect to a field $K$  ) if there exists a homogeneous ASL domain supported on $H$  . A beautiful result, due to Hibi [14, says that any distributive lattice $L$  is integral. Indeed, $L$  supports a homogeneous ASL domain, denoted by ${H}_{L}$  , in a very natural way. The ring ${H}_{L}$  is called the Hibi ring of $L$  and its defining equations are the so-called Hibi relations: $xy-\left(x\wedge y\right)\left(x\vee y\right)$  . In a series of papers [15, 16, 17, 22, 23Hibi and Watanabe classified various families of integral posets of low dimension. In this direction, we construct a new class of integral posets: the rank truncations of hypercubes. In details, given a sequence of positive integers $d={d}_{1},...,{d}_{m},$  let $H\left(d\right)={\Pi }_{i=1}^{m}\left\{1,...,{d}_{i}\right\}$  and, for $n\in \mathbb{N}$  , ${H}_{n}\left(d\right)=\left\{\alpha \in H\left(d\right):rk\alpha   . We show that ${H}_{n}\left(d\right)$  is an integral poset (over every infinite field $K$  ). This is done by proving that $A\left(V\right)$  is a homogeneous ASL on ${H}_{n}\left(d\right)$  if the ${V}_{i}$  are generic linear spaces of dimension ${d}_{i}$  of $R$  , see Section  5 . In particular, our construction shows that the Veronese subrings of polynomials rings are homogeneous ASL (obviously domains). Note however that they are not, in general, ASL with respect to their semigroup presentation.

Results from [6show that for any collection $V={V}_{1},...,{V}_{m}$  the algebra $A\left(V\right)$  is normal. As said above, in the monomial case, i.e. when the ${V}_{i}$  are generated by variables, we show that $A\left(V\right)$  is Koszul and describe its defining equations. Our argument for the monomial case is based on a certain elimination process and on a result, Theorem  3.1 , proved independently by Sturmfels and Villarreal, describing the universal Gröbner basis of the ideal of $2$  -minors of a matrix of variables. This approach suggests also a possible strategy for proving that $A\left(V\right)$  is Koszul in the general case. The elimination process is still available and what one needs is a replacement of the Sturmfels-Villarreal's theorem. This boils down to the following:
Conjecture 1.1. Let ${t}_{ij}$  be distinct variables over a field $K$  with $1\le i\le m$  and $1\le j\le n$  . Let $L=\left({L}_{ij}\right)$  be a $m×n$  matrix with ${L}_{ij}={\sum }_{k=1}^{n}{a}_{ijk}{t}_{ik}$  and ${a}_{ijk}\in K$  for all $i,j,k$  .
Denote by ${I}_{2}\left(L\right)$  the ideal of the $2$  -minors of $L$  . We conjecture that for every choice of ${a}_{ijk}$  's, for every term order $<$  on $K\left[{t}_{ij}\right]$  the initial ideal $i{n}_{<}\left({I}_{2}\left(L\right)\right)$  is square-free in the ${\mathbb{Z}}^{m}$  -graded sense, i.e. it is generated by elements the form ${t}_{{i}_{1}{j}_{1}}\cdots {t}_{{i}_{k}{j}_{k}}$  with ${i}_{1}<{i}_{2}<\cdots <{i}_{k}$  .
This conjecture can be rephrased in terms of universal comprehensive Gröbner bases [24: the parametric ideal ${I}_{2}\left(L\right)$  (the parameters being the ${a}_{ijk}$  's) has a comprehensive and universal Gröbner basis whose elements are multihomogeneous of degree bounded by $\left(1,1,...,1\right)$  .
If $L=\left({t}_{ij}\right)$  then  1.1 holds; this is a consequence of Theorem  3.1 . We prove in  5.1 that  1.1 holds when the ${a}_{ijk}$  are generic. As a consequence, we are able to show that for generic spaces ${V}_{i}$  the algebra $A\left(V\right)$  is Cohen-Macaulay, Koszul and describe the defining equations of $A\left(V\right)$  . In particular, as mentioned above, in the generic case $A\left(V\right)$  turns out to be a homogeneous ASL on the poset ${H}_{n}\left(d\right)$  where $d={d}_{1},...,{d}_{m}$  and ${d}_{i}=dim{V}_{i}$  .
We thank C.Krattenthaler who provided a combinatorial argument for a statement which was used in an earlier version of the proof of  5.1 . The results presented in this the paper have been inspired, suggested and confirmed by computations performed by the computer algebra system CoCoA [5.

2 Normality of $A\left(V\right)$

Let ${I}_{i}$  be the ideal of $R$  generated by ${V}_{i}$  . In [6it is proved that the product ideal ${I}_{1}\cdots {I}_{m}$  has always a linear resolution. One of the main step in proving that result is the following [6,3.2:
Proposition 2.1. For any subset $A\subseteq \left\{1,...,m\right\}$  set ${I}_{A}={\sum }_{i\in A}{I}_{i}$  and denote by $#A$  the cardinality of $A$  . Then ${I}_{1}\cdots {I}_{m}=\cap {I}_{A}^{#A}$  is a primary decomposition of $I$  . Here the intersection is extended to all the $A\ne \varnothing$  .
Proposition  2.1 easily implies:
Theorem 2.2. $A\left(V\right)$  is normal.
• Proof. Set $J={I}_{1}\cdots {I}_{m}$  . Note that ${I}_{A}$  is a prime ideal generated by linear forms. Hence the powers of ${I}_{A}$  are integrally closed. It follows that $J$  is integrally closed. Since the powers of $J$  are again product of ideals of linear forms, the same argument apply also to the powers of $J$  . Hence we conclude that $J$  is normal (i.e. all the powers of $J$  are integrally closed). This is equivalent to the fact that the Rees algebra $\mathcal{ℛ}\left(J\right)={\oplus }_{k\in \mathbb{N}}{J}^{k}$  is normal. Now $A\left(V\right)$  , being a direct summand of $\mathcal{ℛ}\left(J\right)$  , is normal as well.

3 The monomial case

We now analyze the monomial case. Our goal is to show that $A\left(V\right)$  is Koszul if each ${V}_{i}$  is monomial and to develop a strategy to attack the general case. So in this section we assume that each ${V}_{i}$  is generated by a subset of the variables $\left\{{x}_{1},...,{x}_{n}\right\}$  . Say ${V}_{i}=〈{x}_{j}:j\in {C}_{i}〉$  where ${C}_{i}$  is a non-empty subset of $\left\{1,...,n\right\}$  . Consider the auxiliary algebra $B\left(V\right)=K\left[{V}_{1}{y}_{1},...,{V}_{m}{y}_{m}\right]=K\left[{y}_{i}{x}_{j}:i\in 1,...,n,\text{and}j\in {C}_{i}\right]$  where ${y}_{1},...,{y}_{m}$  are new variables. The algebra $B\left(V\right)$  sits inside the Segre product $S=K\left[{y}_{i}{x}_{j}:1\le i\le m,1\le j\le n\right].$  We consider variables ${t}_{ij}$  with $i=1,...,m$  and $j=1,...,n$  , and define $T=K\left[{t}_{ij}:1\le i\le m,1\le j\le n\right]\text{and}T\left(V\right)=K\left[{t}_{ij}:1\le i\le m,j\in {C}_{i}\right]$  and presentations:
$\phi :T\to S\text{and}{\phi }^{\prime }:T\left(V\right)\to B\left(V\right)$  defined by sending ${t}_{ij}$  to ${y}_{i}{x}_{j}$  .
It is well-known that $Ker\phi$  is the ideal ${I}_{2}\left(t\right)$  of $2$  -minors of the $m×n$  matrix $t=\left({t}_{ij}\right)$  . Then the algebra $B\left(V\right)$  is defined as a quotient of $T\left(V\right)$  by the ideal ${I}_{2}\left(t\right)\cap T\left(V\right)$  . The algebras $B\left(V\right),T\left(V\right),S$  and $T$  can be given a ${\mathbb{Z}}^{m}$  -graded structure by setting the degree of ${y}_{i}{x}_{j}$  and ${t}_{ij}$  to be ${e}_{i}\in {\mathbb{Z}}^{m}$  .
By work of Sturmfels [20,4.11and8.11and Villarreal [21,8.1.10one knows that a universal Gröbner basis of ${I}_{2}\left(t\right)$  is given by the cycles of the complete bipartite graph ${K}_{n,m}$  . In details, a cycle of the complete bipartite graph is described by a pair $\left(I,J\right)$  of sequences of integers, say $I={i}_{1},...,{i}_{s},J={j}_{1},...,{j}_{s}$  with $2\le s\le min\left(n,m\right)$  , $1\le {i}_{k}\le m$  , $1\le {j}_{k}\le n$  , and such that the ${i}_{k}$  are distinct and the ${j}_{k}$  are distinct. Associated with any such a pair we have a polynomial ${f}_{I,J}={t}_{{i}_{1}{j}_{1}}\cdots {t}_{{i}_{s}{j}_{s}}-{t}_{{i}_{2}{j}_{1}}\cdots {t}_{{i}_{s}{j}_{s-1}{t}_{{i}_{1}{j}_{s}}}$  which is in ${I}_{2}\left(t\right)$  .
Theorem 3.1. (Sturmfels-Villarreal) The set of the polynomials ${f}_{I,J}$  where $\left(I,J\right)$  is a cycle of ${K}_{n,m}$  form a universal Gröbner basis of ${I}_{2}\left(t\right)$  .
In particular we have:
Corollary 3.2. The polynomials ${f}_{I,J}$  involving only variables of $T\left(V\right)$  form a universal Gröbner basis of ${I}_{2}\left(t\right)\cap T\left(V\right)$  .
Important for us is the following:
Corollary 3.3. The ideal ${I}_{2}\left(t\right)\cap T\left(V\right)$  has a universal Gröbner basis whose elements have ${\mathbb{Z}}^{m}$  -degree bounded above by $\left(1,1,...,1\right)\in {\mathbb{Z}}^{m}$  .
For a ${\mathbb{Z}}^{m}$  -graded algebra $E$  we denote by ${E}_{\Delta }$  the direct sum of the graded components of $E$  of degree $\left(v,v,...,v\right)\in {\mathbb{Z}}^{m}$  as $v$  varies in $\mathbb{Z}$  . Similarly, for a ${\mathbb{Z}}^{m}$  -graded $E$  -module $M$  we denote by ${M}_{\Delta }$  the direct sum of the graded components of $M$  of degree $\left(v,v,...,v\right)\in {\mathbb{Z}}^{m}$  as $v$  varies in $\mathbb{Z}$  .
Clearly ${E}_{\Delta }$  is a $\mathbb{Z}$  -graded algebra and ${M}_{\Delta }$  is a $\mathbb{Z}$  -graded ${E}_{\Delta }$  -module. Furthermore ${-}_{\Delta }$  is exact as a functor on the category of ${\mathbb{Z}}^{m}$  -graded $E$  -module with maps of degree $0$  .
Now $B\left(V{\right)}_{\Delta }$  is the $K$  -algebra generated by the elements in ${y}_{1}{V}_{1}\cdots {y}_{m}{V}_{m}$  . Therefore $A\left(V\right)$  is (isomorphic to) the algebra of $B\left(V{\right)}_{\Delta }$  .
Hence we obtain a presentation $0\to Q\to {T}^{*}\to A\left(V\right)\to 0$  where $Q=\left({I}_{2}\left(t\right)\cap T\left(V\right){\right)}_{\Delta }$  and ${T}^{*}=T\left(V{\right)}_{\Delta }$  is the $K$  -algebra generated by the monomials ${t}_{1{j}_{1}}...{t}_{m{j}_{m}}$  with ${j}_{k}\in {C}_{k}$  , that is, ${T}^{*}$  is the Segre product of the polynomial rings ${T}_{i}=K\left[{t}_{ij}:j\in {C}_{i}\right].$  From  3.3 we get:
Corollary 3.4. The ideal $Q$  is generated by elements of degree $\left(1,1,...,1\right)$  which form a Gröbner basis with respect to any term order on the variables ${t}_{ij}$  .
• Proof. Let $g\in Q$  be a homogeneous element of degree, say, $\left(a,a,...,a\right)$  . Then there exists $h\in {I}_{2}\left(t\right)\cap T\left(V\right)$  of multidegree $\le \left(1,1,...,1\right)$  such that $in\left(h\right)|in\left(g\right)$  . Then there exists a monomial $v$  of multidegree $\left(1,1,...,1\right)-degh$  such that $in\left(h\right)v|in\left(g\right)$  . It follows that $hv\in Q$  has degree $\left(1,1,...,1\right)$  and its initial term divides $in\left(g\right)$  .
In  3.4 (and later on) we consider Gröbner bases and initial ideals of ideals in $K$  -subalgebras of polynomial rings. For the details on this “relative” Gröbner basis theory the reader can consult, for instance, [2,Sect.3or the [20,Chap.11. We may now conclude:
Theorem 3.5. If the ${V}_{i}$  are generated by variables then $A\left(V\right)$  is a Koszul algebra.
Moreover $A\left(V\right)$  is a quotient of the Segre product ${T}^{*}$  by an ideal generated by linear (binomial) forms which are a Gröbner basis.
• Proof. From  3.4 we know that the initial ideal $in\left(Q\right)$  (with respect to any term order) is an ideal of ${T}^{*}$  generated by a subset of the monomials generating ${T}^{*}$  as a $K$  -algebra. By work of Herzog, Hibi and Restuccia [12,2.3we know that Segre products of polynomial rings are strongly Koszul semigroup rings. Strongly Koszul semigroup rings remain strongly Koszul after moding out semigroup generators [12,2.1. So ${T}^{*}/in\left(Q\right)$  is strongly Koszul and in particular Koszul. But then the standard deformation argument shows that ${T}^{*}/Q$  is Koszul, see [2,3.16for details. Therefore we can conclude that $A\left(V\right)$  is a Koszul algebra.
Remark 3.6. In the proof of above we have shown that a Segre product of polynomial rings modulo a certain ideal of linear forms is Koszul. One might ask whether linear sections of Segre product of polynomial rings are always Koszul. It is not the case.
The ideal of $2$  -minors of the matrix $\left(\begin{array}{cccc}0& x& y& z\\ x& y& 0& t\end{array}\right)$  defines an algebra which is a linear section of the Segre product of polynomial rings of dimension $2$  and $4$  and it is not Koszul. This is the algebra number $69$  in Roos' list [19, a well-known gold-mine of examples.
Keeping track of the various steps of the construction above one can describe the defining equations of $A\left(V\right)$  . In details, we set $C={C}_{1}×{C}_{2}×\cdot \cdot \cdot ×{C}_{m}$  . Consider variables ${s}_{\alpha }$  with $\alpha \in C$  and the polynomial ring $K\left[C\right]=K\left[{s}_{\alpha }:\alpha \in C\right]$  . Then we get presentations of the Segre product ${T}^{*}$  and of $A\left(V\right)$  as quotients of $K\left[C\right]$  of by sending ${s}_{\left({j}_{1},...,{j}_{m}\right)}$  to ${t}_{1{j}_{1}}\cdots {t}_{m{j}_{m}}$  and to ${x}_{{j}_{1}}\cdots {x}_{{j}_{m}}$  respectively.
The ring ${T}^{*}$  is the Hibi ring of the distributive lattice $C$  so it is defined by the Hibi relations, namely ${s}_{\alpha }{s}_{\beta }-{s}_{\alpha \vee \beta }{s}_{\alpha \wedge \beta }$  where $\alpha \vee \beta =\left(max\left({\alpha }_{1},{\beta }_{1}\right),...,max\left({\alpha }_{m},{\beta }_{m}\right)\right)$  and $\alpha \wedge \beta =\left(min\left({\alpha }_{1},{\beta }_{1}\right),...,min\left({\alpha }_{m},{\beta }_{m}\right)\right).$  We have:
Proposition 3.7. The defining ideal of $A\left(V\right)$  as a quotient of the polynomial ring $K\left[C\right]$  is generated by the Hibi relations ${s}_{\alpha }{s}_{\beta }-{s}_{\alpha \vee \beta }{s}_{\alpha \wedge \beta }$  and by the relations ${s}_{\alpha }-{s}_{\beta }$  where $\alpha ,\beta \in C$  and one is obtained by the other with a non-trivial permutation.
For instance:
Example 3.8. Let $n=3$  and ${V}_{1}=〈{x}_{2},{x}_{3}〉,{V}_{2}=〈{x}_{1},{x}_{3}〉,{V}_{3}=〈{x}_{1},{x}_{2}〉$  . Then $B\left(V\right)$  is the quotient of $K\left[{t}_{12},{t}_{13},{t}_{21},{t}_{23},{t}_{31},{t}_{32}\right]$  by the polynomial ${t}_{12}{t}_{23}{t}_{31}-{t}_{13}{t}_{21}{t}_{32}$  and then $A\left(V\right)$  is the quotient of $K\left[{s}_{ijk}:\left(i,j,k\right)\in \left\{2,3\right\}×\left\{1,3\right\}×\left\{1,2\right\}\right]$  by the Hibi-relations
 $\begin{array}{cc}{s}_{312}{s}_{331}-{s}_{311}{s}_{332},& {s}_{212}{s}_{311}-{s}_{211}{s}_{312},\end{array}$
 $\begin{array}{cc}{s}_{212}{s}_{231}-{s}_{211}{s}_{232},& {s}_{212}{s}_{331}-{s}_{211}{s}_{332},\end{array}$
 $\begin{array}{cc}{s}_{231}{s}_{311}-{s}_{211}{s}_{331},& {s}_{231}{s}_{312}-{s}_{211}{s}_{332},\end{array}$
 $\begin{array}{cc}{s}_{232}{s}_{311}-{s}_{211}{s}_{332},& {s}_{232}{s}_{312}-{s}_{212}{s}_{332},\end{array}$
 $\begin{array}{c}{s}_{232}{s}_{331}-{s}_{231}{s}_{332}\end{array}$
and by the linear relation ${s}_{231}-{s}_{312}$
Remark 3.9. It is not clear whether the defining ideal of $A\left(V\right)$  as a quotient of $K\left[C\right]$  has a Gröbner basis of quadrics. The Hibi relations form a Gröbner basis with respect to any revlex linear extension of the partial order on $C$  . There are examples where the Hibi relations together with the linear relations defining $A\left(V\right)$  are not a Gröbner basis with respect to such revlex linear extensions.
Remark 3.10. In a special case it turns out that both $B\left(V\right)$  and $A\left(V\right)$  are defined by Gröbner bases of quadrics as quotient of polynomial rings. For a nested chain of vector spaces of linear forms ${V}_{1}\supseteq {V}_{2}\supseteq \cdot \cdot \cdot \supseteq {V}_{m}$  , we can fix a basis ${x}_{1},{x}_{2},...,{x}_{n}$  of ${R}_{1}$  such that ${V}_{i}$  is generated by ${x}_{1},...,{x}_{{d}_{i}}$  . Here ${d}_{1}\ge {d}_{2}\ge \cdot \cdot \cdot \ge {d}_{m}$  . It follows that $B\left(V\right)$  corresponds to a one-sided ladder determinantal ring, the ladder being the set of points $\left(i,j\right)$  with $1\le i\le m$  and $1\le j\le {d}_{i}$  . Furthermore, $A\left(V\right)$  coincides with the algebra associated with the principal Borel subset generated by the monomial ${\Pi }_{i}{x}_{{d}_{i}}$  . A Gröbner basis of quadrics for $B\left(V\right)$  is described in [13and a Gröbner basis of quadrics for $A\left(V\right)$  is described in [8.
In general, however, the algebra $B\left(V\right)$  is not defined by quadrics as the Example  3.8 shows.
White's conjecture [26predicts the structure of the defining equations of the base ring of a (poly)matroid: they should be quadrics representing the basic symmetric exchange relations of the polymatroid. Our result above  3.7 does not prove White's conjecture in this precise form.

4 Conjectures

The constructions and arguments of the previous section suggest a general strategy to investigate the Koszul property of $A\left(V\right)$  for general (i.e. non-monomial) ${V}_{i}$  . We outline in this section the strategy which leads us to Conjecture  1.1 . Let $V={V}_{1},...,{V}_{m}$  be a collection of subspaces of ${R}_{1}$  and let ${y}_{1},...,{y}_{m}$  be new variables. Set ${d}_{i}=dim{V}_{i}$  , and set $S=K\left[{y}_{i}{x}_{j}:i=1,...,m,j=1,...,n\right]$  $B\left(V\right)=K\left[{y}_{1}{V}_{1},...,{y}_{m}{V}_{m}\right].$  and $T=K\left[{t}_{ij}:i=1,...,m,j=1,...,n\right].$  Again $B\left(V\right)$  is a $K$  -subalgebra of $S$  . We give degree ${e}_{i}\in {\mathbf{Z}}^{m}$  to ${y}_{i}{x}_{j}$  and to ${t}_{ij}$  so that $S$  , $T$  and as well $B\left(V\right)$  are ${\mathbf{Z}}^{m}$  -graded. We present $S$  as a quotient of $T$  by sending ${t}_{ij}$  to ${y}_{i}{x}_{j}$  . The kernel of such presentation is the ideal ${I}_{2}\left(t\right)$  generated by the $2$  -minors of the $m×n$  matrix $t=\left({t}_{ij}\right)$  . As we have seen in the previous section $A\left(V\right)$  is the diagonal algebra $B\left(V{\right)}_{\Delta }$  .
We want to get the presentations of $B\left(V\right)$  and $A\left(V\right)$  by elimination from that of $S$  . To that end we do the following: Let ${f}_{ij}$  , $j=1,...,{d}_{i}$  , be a basis of ${V}_{i}$  and complete it to a basis of ${R}_{1}$  with elements ${f}_{ij}$  , $j={d}_{i}+1,...,n$  . Denote by ${f}_{i}$  the row vector $\left({f}_{ij}\right)$  and by $x$  the row vector of the ${x}_{i}$  's. Let ${A}_{i}$  be the $n×n$  matrix with entries in $K$  with $x={f}_{i}{A}_{i}$  . Then $S=K\left[{y}_{i}{f}_{ij}:i=1,...,m,j=1,...,n\right]$  and $B\left(V\right)=K\left[{y}_{i}{f}_{ij}:i=1,...,m,j=1,...,{d}_{i}\right]$  . Set $T\left(V\right)=K\left[{t}_{ij}:1\le i\le m,1\le j\le {d}_{i}\right]$  . We have presentations:
 $\begin{array}{ccc}\phi :T\to S& \text{with}{t}_{ij}\to {y}_{i}{f}_{ij}& \text{for all}i,j\end{array}$
 $\begin{array}{c}\end{array}$
 $\begin{array}{ccc}{\phi }^{\prime }:T\left(V\right)\to B\left(V\right)& \text{with}{t}_{ij}\to {y}_{i}{f}_{ij}& \text{for all}i\text{and}1\le j\le {d}_{i}\end{array}$
By construction, the kernel of $\phi$  is the ideal of $2$  -minors ${I}_{2}\left(L\right)$  of the matrix $L=\left({L}_{ij}\right)$  where the row vector $\left({L}_{ij}:j=1,...,n\right)$  is given by $\left({t}_{i1},...,{t}_{in}\right){A}_{i}$  . Clearly, $Ker{\phi }^{\prime }={I}_{2}\left(L\right)\cap T\left(V\right)$  . As explained in the previous section, by applying the diagonal functor we obtain a presentation:
$A\left(V\right)\simeq {T}^{*}/Q$  where ${T}^{*}$  is the Segre product of the ${T}_{i}$  's, ${T}_{i}=K\left[{t}_{ij}:j=1,...,{d}_{i}\right]$  , and $Q=\left({I}_{2}\left(L\right)\cap T\left(V\right){\right)}_{\Delta }$  .
Remark 4.1. One can easily check that the arguments of Section  3 , in particular those of  3.4 and  3.5 , work and can be used to show that $A\left(V\right)$  is Koszul provided one knows that ${I}_{2}\left(L\right)\cap T\left(V\right)$  has an initial ideal generated in degree $\le \left(1,1,...,1\right)\in {\mathbb{Z}}^{m}$  .
On the other hand, ${I}_{2}\left(L\right)\cap T\left(V\right)$  has the desired initial ideal provided ${I}_{2}\left(L\right)$  has an initial ideal generated in degree $\le \left(1,1,...,1\right)\in {\mathbb{Z}}^{m}$  with respect to the appropriate elimination order.
We are led by  4.1 to analyze initial ideals of ideals of $2$  -minors of matrices as $L$  . To our great surprise, the experiments support the Conjecture  1.1 . What we really need is a weak for of  1.1 , namely:
Conjecture 4.2. Let $L=\left({L}_{ij}\right)$  be a $m×n$  matrix with ${L}_{ij}={\sum }_{k=1}^{n}{a}_{ijk}{t}_{ik}$  and ${a}_{ijk}\in K$  for all $i,j,k$  . Assume that for every $i$  the forms ${L}_{i1},...,{L}_{in}$  are linearly independent.
Then any lexicographic initial ideal of ${I}_{2}\left(L\right)$  is generated in degree $\le \left(1,1,...,1\right)$  .
If conjecture  4.2 holds then from the discussion above follows that for every ${V}_{1},...,{V}_{m}$  the algebra $A\left(V\right)$  is Koszul and defined by a Gröbner basis of linear forms as a quotient of the Segre product ${T}^{*}$  .
The next section is devoted to prove Conjecture  1.1 in the generic case.

5 The generic case

We consider now the case of generic spaces ${V}_{1},...,{V}_{m}$  . What we prove is the following:
Theorem 5.1. If the matrix $L$  is generic, that is, every entry ${L}_{ij}={\sum }_{k=1}^{n}{a}_{ijk}{t}_{ik}$  is a generic linear combination of the variable ${t}_{i1},...,{t}_{in}$  , then  1.1 holds.
The key lemma is:
Lemma 5.2. Let ${V}_{1},...,{V}_{m}$  be subspaces of ${R}_{1}$  . If ${\sum }_{i=1}^{m}dim{V}_{i}\ge n+m$  then $dim{\prod }_{i=1}^{m}{V}_{i}<{\prod }_{i=1}^{m}dim{V}_{i}$  , i.e. there is a non-trivial linear relation among the generators of the product ${\prod }_{i=1}^{m}{V}_{i}$  obtained by multiplying $K$  -bases of the ${V}_{i}$  .
• Proof. By induction on $n$  and $m$  . If one of the ${V}_{i}$  is principal then we can simply skip it. The case $m=2$  is easy: the assumption is equivalent to $dim\left({V}_{1}\cap {V}_{2}\right)\ge 2$  and for $f,g\in {V}_{1}\cap {V}_{2}$  we get the non-trivial relation $fg-gf=0$  . For $m>2$  , if $dim\left({V}_{i}\cap {V}_{j}\right)\ge 2$  for some $i\ne j$  then the non-trivial relation above gives a non-trivial relation also for ${V}_{1}\cdots {V}_{m}$  . Therefore we may assume that $dim\left({V}_{i}\cap {V}_{j}\right)<2$  , and, since none of the ${V}_{i}$  is principal, also none of the ${V}_{i}$  is ${R}_{1}$  . The case $n=2$  follows and to prove the assertion in the general case we may assume that $1<{d}_{i}  for all $i$  . Further we may assume also that the ${V}_{i}$  are generic, the dimension of ${V}_{1}\cdots {V}_{m}$  for special ${V}_{i}$  can be only smaller. By the genericity of the ${V}_{i}$  we may find $K$  -bases ${f}_{ij}$  of ${V}_{i}$  so that any set of $n$  elements in the set $\left\{{f}_{ij}:i=1,...,m,andj=1,...,{d}_{i}\right\}$  is a basis of ${R}_{1}$  . Now let $x$  be a general linear form (it suffices that $x$  is not contained in any sum of the ${V}_{i}$  which is a proper subspace of ${R}_{1}$  ). Since $x\notin {V}_{i}$  we have that $dim{V}_{i}+\left(x\right)/\left(x\right)={d}_{i}$  , so by induction on $n$  we may find a non-trivial relation among the generators of ${V}_{1}\cdots {V}_{m}$  modulo $x$  . In other words there exists a relation of the form $\sum {\lambda }_{\alpha }{f}_{1{\alpha }_{1}}\cdots {f}_{m{\alpha }_{m}}=xh$  where ${\lambda }_{\alpha }\in K$  , the sum is extended to all the $\alpha$  in ${\prod }_{i=1}^{m}\left\{1,...,{d}_{i}\right\}$  and at least one of the ${\lambda }_{\alpha }$  is non-zero. We may assume ${\lambda }_{\alpha }\ne 0$  for $\alpha =\left(1,1,...,1\right)$  . By the above relation we have that $xh\in {\prod }_{i=1}^{m}{V}_{i}$  and hence $xh\in {\prod }_{i\ne j}{V}_{i}$  for all $j$  . But form  2.1 we see immediately that $x$  acts as a non-zero divisor in degree $m-1$  and higher on the ideal generated by ${\prod }_{i\ne j}{V}_{i}$  . It follows that $h\in {\prod }_{i\ne j}{V}_{i}$  for all $j$  . By the choice of the ${f}_{ij}$  and since ${\sum }_{i=1}^{m}{d}_{i}\ge n+m$  we may write $x$  as a linear combination of the ${f}_{ij}$  with $i=1,...,m,$  and $1  . It follows that $xh$  can be written as a linear combination of the ${f}_{1{\alpha }_{1}}\cdots {f}_{m{\alpha }_{m}}$  with $\alpha \ne \left(1,1,...,1\right)$  . Hence we obtain a relation $\sum {\lambda }_{\alpha }^{\prime }{f}_{1{\alpha }_{1}}\cdots {f}_{m{\alpha }_{m}}=0$  with ${\lambda }_{\alpha }^{\prime }={\lambda }_{\alpha }\ne 0$  for $\alpha =\left(1,1,...,1\right)$  .
Now we are ready to prove:
• Proof. of  5.1 Set $I={I}_{2}\left(L\right)$  . Let $<$  be a term order on the ${t}_{ij}$  . After a change of name of the variables in the $i$  -th row of $L$  if needed, we may assume that ${t}_{ij+1}>{t}_{ij}$  for all $j=1,...,n-1$  and for all $i=1,...,m$  . Let $J$  be the ideal generated by the monomials ${t}_{{i}_{1}{j}_{1}}\cdots {t}_{{i}_{k}{j}_{k}}$  satisfying conditions:
$\left(*\right)\left\{\begin{array}{c}1\le {i}_{1}<\cdot \cdot \cdot <{i}_{k}\le m,\\ 1\le {j}_{1},...,{j}_{k}\le n,\\ {j}_{1}+\cdot \cdot \cdot +{j}_{k}\ge n+k.\end{array}$  We will show that the initial ideal of $I$  with respect to $<$  is equal to $J$  . From this the assertion follows immediately. It is a simple exercise on primary decompositions that the equality $J=in\left(I\right)$  follows from three facts:
(1) $J\subseteq in\left(I\right)$  , (2) $J$  and $I$  have the same codimension and degree, (3) $J$  is unmixed.
For (1) we have to show that for each pair of sequences of integers satisfying conditions (*) the monomial ${t}_{{i}_{1}{j}_{1}}\cdots {t}_{{i}_{k}{j}_{k}}$  is in $in\left(I\right)$  . As $L$  is generic, the initial ideal $in\left(I\right)$  is the multigraded generic initial ideal of $I$  with respect to $>$  . Hence $in\left(I\right)$  is Borel fixed is the multigraded sense, see [1. In characteristic $0$  this means that if a monomial $M$  is in $in\left(I\right)$  and ${t}_{ij}|M$  then ${t}_{ik}M/{t}_{ij}$  is in $in\left(I\right)$  as well for all the $k>j$  . In arbitrary characteristic the same assertion is also true as long as $M$  is square-free. It follows that, (no matter what the characteristic is), it suffices to show that there exists an $f$  in $I$  such that $in\left(f\right)={t}_{{i}_{1}{p}_{1}}\cdots {t}_{{i}_{k}{p}_{k}}$  and ${p}_{1}\le {j}_{1},...,{p}_{k}\le {j}_{k}$  . To this end, consider the linear forms ${f}_{ij}$  defined (implicitly) by the relation ${x}_{k}={\sum }_{k=1}^{n}{f}_{ij}{a}_{ikj}$  for all $j$  . By the construction of Section  4 we see that $I$  is the kernel of the map $\phi$  . Now for $s=1,...,k$  consider the subspace ${W}_{{i}_{s}}$  generated by the ${f}_{{i}_{s}j}$  with $j\le {j}_{s}$  . Since, by assumption ${\sum }_{s=1}^{k}dim{W}_{{i}_{s}}={\sum }_{s=1}^{k}{j}_{s}\ge n+k$  , by Lemma  5.2 we have that there exists a non-trivial relation among the generators of the product ${W}_{{i}_{1}}\cdots {W}_{{i}_{k}}$  . This implies that the $I$  contains a non-zero polynomial $f$  supported on the set of the monomials ${t}_{{i}_{1}{p}_{1}}\cdots {t}_{{i}_{k}{p}_{k}}$  and ${p}_{1}\le {j}_{1},...,{p}_{k}\le {j}_{k}$  . Take $in\left(f\right)$  to get what we want.
As for the step (2) and (3), the ideal of $I$  is a generic determinantal ideal and its numerical invariants are well-known: its codimension is $\left(m-1\right)\left(n-1\right)$  and the its degree is $\left(\genfrac{}{}{0}{}{m+n-2}{m-1}\right)$  . Knowing the generators of $J$  we can describe the facets of the associated simplicial complex $\Delta \left(J\right)$  . Then we can read from the descriptions of the facets the codimension, the degree of $J$  and check that it is unmixed. The facets of $\Delta \left(J\right)$  have the following description: for each $p=\left({p}_{1},...,{p}_{m}\right)\in \left\{1,...,n{\right\}}^{m}$  with ${p}_{1}+...,{p}_{m}=n+m-1$  we let ${F}_{p}=\left\{{t}_{ij}:i=1,...,m\text{and}1\le j\le {p}_{i}\right\}$  It is easy to check that any such ${F}_{p}$  is a facet of $\Delta \left(J\right)$  . On the other hand if $F$  is a face of $\Delta \left(J\right)$  let $a\left(F\right)=\left\{i:\exists j\text{with}{t}_{ij}\in F\right\}$  and ${j}_{i}=max\left\{j:{t}_{ij}\in F\right\}$  if $i\in a\left(F\right)$  . Then set $q=\left({q}_{1},...,{q}_{m}\right)$  with ${q}_{i}={j}_{i}$  if $a\in a\left(F\right)$  and ${q}_{i}=1$  otherwise. Note that ${q}_{1}+\cdot \cdot \cdot +{q}_{m}={\sum }_{i\in a\left(F\right)}{j}_{i}+m-|a\left(F\right)|$  and that ${\sum }_{i\in a\left(F\right)}{j}_{i}  since $\left\{{t}_{i{j}_{i}}:i\in a\left(F\right)\right\}\subset F\in \Delta \left(J\right)$  . It follows that ${q}_{1}+\cdot \cdot \cdot +{q}_{m}  . So, increasing the ${q}_{i}$  's if needed, we may take $p=\left({p}_{1},...,{p}_{m}\right)\in \left\{1,...,n{\right\}}^{m}$  with ${p}_{1}+...,{p}_{m}=n+m-1$  and ${q}_{i}\le {p}_{i}$  .
It follows that $F\subseteq {F}_{p}$  .
From the description above we see that the cardinality of each ${F}_{p}$  is $n+m-1$  . It follows that $J$  is unmixed of codimension $\left(m-1\right)\left(n-1\right)$  . The degree $J$  is the number of facets of $\Delta \left(J\right)$  , that is the number of $p=\left({p}_{1},...,{p}_{m}\right)\in \left\{1,...,n{\right\}}^{m}$  with ${p}_{1}+\cdot \cdot \cdot +{p}_{m}=n+m-1$  . Setting ${q}_{i}={p}_{i}-1$  , we see that the number of facets of $\Delta \left(J\right)$  is the number of $q=\left({q}_{1},...,{q}_{m}\right)\in \left\{0,...,n-1{\right\}}^{m}$  with ${q}_{1}+\cdot \cdot \cdot +{q}_{m}=n-1$  , that is, the number of monomials of degree $n-1$  in $m$  variables. This number is $\left(\genfrac{}{}{0}{}{m+n-2}{m-1}\right)$  . We have checked that (2) and (3) hold. The proof of the theorem is now complete.
Let us single out the following corollary of the proof of of  5.1 :
Corollary 5.3. With the notations of the proof of  5.1 we have:
• (a) If ${i}_{1}<\cdot \cdot \cdot <{i}_{k}$  then a monomial ${t}_{{i}_{1}{j}_{1}}\cdots {t}_{{i}_{k}{j}_{k}}$  is in $J$  iff ${j}_{1}+\cdot \cdot \cdot +{j}_{k}\ge n+k$  .
• (b) For every monomial $M={t}_{{i}_{1}{j}_{1}}\cdots {t}_{{i}_{k}{j}_{k}}\in J$  with ${i}_{1}<\cdot \cdot \cdot <{i}_{k}$  there exists a polynomial ${f}_{M}\in I$  of the form ${f}_{M}=M+{\sum }_{v}{\lambda }_{v}{t}_{{i}_{1}{v}_{1}}\cdots {t}_{{i}_{k}{v}_{k}}$  where ${\lambda }_{v}\in K$  , $v\in {\Pi }_{h=1}^{k}\left\{1,2,...,{j}_{h}\right\}$  , and ${t}_{{i}_{1}{v}_{1}}\cdots {t}_{{i}_{k}{v}_{k}}\notin J$  .
• (c) The set of the polynomials ${f}_{M}$  is a Gröbner basis of $I$  with respect to any term order $<$  on $K\left[{t}_{ij}\right]$  satisfying ${t}_{ij+1}>{t}_{ij}$  for all $j=1,...,n-1$  and for all $i=1,...,m$  .
• Proof. (a) follows form the definition of $J$  . For (b) we argue as follows. Let $<$  be a term order on $K\left[{t}_{ij}\right]$  satisfying ${t}_{ij+1}>{t}_{ij}$  for all $j=1,...,n-1$  and for all $i=1,...,m$  . We have seen in the proof of  5.1 that $J=i{n}_{<}\left(I\right)$  . Considering the reduced expression, we have that for every monomial $M={t}_{{i}_{1}{j}_{1}}\cdots {t}_{{i}_{k}{j}_{k}}\in J$  there exists a polynomial ${f}_{M}$  in $I$  with initial term $M$  and all the others terms not in $J$  . Suppose that one the non-leading terms of ${f}_{M}$  , say $N={t}_{{i}_{1}{v}_{1}}\cdots {t}_{{i}_{k}{v}_{k}}$  , does not satisfies the condition ${v}_{h}\le {j}_{h}$  for all $h=1,...,k$  . So there exists an $h$  in $\left\{1,2,...,k\right\}$  , say ${h}_{1}$  , such that ${v}_{{h}_{1}}>{j}_{{h}_{1}}$  . We claim that there exists a term order ${<}_{1}$  such that ${t}_{ij+1}{>}_{1}{t}_{ij}$  for all $i,j$  and such that $N{>}_{1}M$  . Then it follows that the initial term of ${f}_{M}$  with respect to ${<}_{1}$  is not $M$  and hence in must be a monomial not in $J$  . This contradicts the fact, proved in  5.1 that $i{n}_{{<}_{1}}\left(I\right)=J$  . It remains to prove the existence of a term order ${<}_{1}$  as above. To this end it is suffices to find weights ${w}_{ij}\in \mathbb{N}$  such that ${w}_{ij}<{w}_{ij+1}$  for all $i,j$  and $w\left(M\right)  , that is ${w}_{{i}_{1},{j}_{1}}+\cdot \cdot \cdot +{w}_{{i}_{k}{j}_{k}}<{w}_{{i}_{1}{v}_{1}}+\cdot \cdot \cdot +{w}_{{i}_{k}{v}_{k}}$  Just take ${w}_{ij}=j$  if $i\ne {i}_{{h}_{1}}$  of if $i={i}_{{h}_{1}}$  and $j<{v}_{{h}_{1}}$  and ${w}_{ij}=a+j$  otherwise with $a$  large enough. Finally (c) is a direct consequence of (b).
As explained in Section  4 from  5.1 follows that $A\left(V\right)$  is Koszul for generic $V$  . To get more precise information about the structure of $A\left(V\right)$  we analyze in details the defining equations of of $B\left(V\right)$  and $A\left(V\right)$  . To this end we recall the definition of homogeneous ASL on a poset.
Let $\left(H,>\right)$  be a finite poset and denote by $K\left[H\right]$  the polynomial ring whose variables are the elements of $H$  . Let ${J}_{H}$  be the monomial ideal of $K\left[H\right]$  generated by $xy$  with $x,y\in H$  such that $x$  and $y$  are incomparable in $H$  .
Definition 5.4. Let $A=K\left[H\right]/I$  where $I$  is a homogeneous ideal (with respect to the usual grading). One says that $A$  is a homogeneous ASL on $H$  if
• (ASL1) The (residue classes of the) monomials not in ${J}_{H}$  are linearly independent in $A$  .
• (ASL2) For every $x,y\in H$  such that $x$  and $y$  are incomparable the ideal $I$  contains a polynomial of the form $xy-\sum \lambda zt$  with $\lambda \in K$  , $z,t\in H$  , $z\le t$  , $z  and $z  .
A linear extension of the poset $\left(H,<\right)$  is a total order ${<}_{1}$  on $H$  such that $x{<}_{1}y$  if $x  . A revlex term order $\tau$  on $K\left[H\right]$  is said to be a revlex linear extension of $<$  if $\tau$  induces on $H$  a linear extension of $<$  . For obvious reasons, if $A=K\left[H\right]/I$  is a homogeneous ASL on $H$  and $\tau$  is a revlex linear extension of $<$  then the polynomials in (ASL2) form a Gröbner basis of $I$  and $i{n}_{\tau }\left(I\right)={J}_{H}$  .
In a sense the converse in also true:
Lemma 5.5. Let $A=K\left[H\right]/I$  where $I$  is a homogeneous ideal. Assume that for every revlex linear extension $\tau$  of $<$  one has $i{n}_{\tau }\left(I\right)={J}_{H}$  . Then $A$  is an ASL on $H$  .
• Proof. Let $\tau$  be a revlex linear extension of $<$  . Since $i{n}_{\tau }\left(I\right)={J}_{H}$  the monomials not in ${J}_{H}$  form a $K$  -basis of $A$  , hence ASL1 is satisfied. Let $x,y\in H$  be incomparable elements. Then $xy\in i{n}_{\tau }\left(I\right)$  and hence there exists $F\in I$  with $i{n}_{\tau }\left(F\right)=xy$  . We can take $F$  reduced in the sense that $xy$  is the only term in $F$  belonging to ${J}_{H}$  . It follows that $F$  have the form $xy-\sum \lambda zt$  with $\lambda \in K$  , $z,t\in H$  and $z\le t$  . Assume, by contradiction that this polynomial does not satisfy the conditions required in ASL2. Then there exist a non-leading term ${z}_{1}{t}_{1}$  appearing in $F$  such that ${z}_{1}\ngtr x$  or ${z}_{1}\ngtr y$  . Say ${z}_{1}\ngtr x$  . It is easy to see that one can find a linear extension ${<}_{1}$  of $<$  such that $x{<}_{1}{z}_{1}$  . Denote by $\sigma$  the revlex term order associated with ${<}_{1}$  . Then $xy$  is smaller than ${z}_{1}{t}_{1}$  with respect to $\sigma$  and hence $i{n}_{\sigma }\left(F\right)$  is a term not in ${J}_{H}$  , contradicting the assumption.
For a given sequence of positive integers $d={d}_{1},...,{d}_{m}$  we set $H\left(d\right)=\left\{1,...,{d}_{1}\right\}×\cdot \cdot \cdot ×\left\{1,...,{d}_{m}\right\}$  and note that $H\left(d\right)$  is a sublattice of ${\mathbb{N}}^{m}$  with respect to the natural partial order $\alpha \le \beta$  iff ${\alpha }_{i}\le {\beta }_{i}$  for all $i$  . The rank $rk\alpha$  of an element $\alpha =\left({\alpha }_{i}\right)\in H\left(d\right)$  is ${\alpha }_{1}+\cdot \cdot \cdot +{\alpha }_{m}-m$  .
Set ${H}_{n}\left(d\right)=\left\{\alpha \in H\left(d\right):rk\alpha   With the notation of Section  4 we have a presentation ${\phi }^{\prime }:T\left(V\right)\to B\left(V\right)$  where $T\left(V\right)=K\left[{t}_{ij}:i=1,...,m,j=1,...,{d}_{i}\right]$  . As a corollary of  5.1 , by elimination we obtain a description $Ker{\phi }^{\prime }$  :
Corollary 5.6. Let ${V}_{1},...,{V}_{m}$  be generic spaces of dimension ${d}_{1},...,{d}_{m}$  and let ${f}_{ij}$  with $j=1,...,{d}_{i}$  be generic generators of ${V}_{i}$  . Let $<$  be a term order such that ${t}_{ij}<{t}_{ij+1}$  .
Then the ideal $Ker{\phi }^{\prime }$  has a Gröbner basis whose elements are the polynomials ${f}_{M}$  of  5.3 with $M={t}_{{i}_{1}{j}_{1}}\cdots {t}_{{i}_{k}{j}_{k}}$  with ${i}_{1}<\cdot \cdot \cdot <{i}_{k}$  , $1\le {j}_{h}\le {d}_{{i}_{h}}$  and ${j}_{1}+\cdot \cdot \cdot +{j}_{k}\ge n+k$  .
Set ${T}_{i}=K\left[{t}_{ij}:1\le j\le {d}_{i}\right]$  and denote by ${T}^{*}$  the Segre product ${T}_{1}*\cdot \cdot \cdot *{T}_{m}$  . Consider variables ${s}_{\alpha }$  with $\alpha \in H\left(d\right)$  and the polynomial ring $K\left[{s}_{\alpha }:\alpha \in H\left(d\right)\right]$  . For each $\alpha \in H\left(d\right)$  set ${t}_{\alpha }={t}_{1{\alpha }_{1}}\cdots {t}_{m{\alpha }_{m}}$  .
We get a presentation $K\left[{s}_{\alpha }:\alpha \in H\left(d\right)\right]\to {T}^{*}$  by sending ${s}_{\alpha }$  to ${t}_{\alpha }$  whose kernel is generated by the Hibi relations:
${s}_{\alpha }{s}_{\beta }-{s}_{\alpha \vee \beta }{s}_{\alpha \wedge \beta }.$  Adopting the notation of Section  4 we get a presentation $A\left(V\right)={T}^{*}/Q$  . To describe the generators of $Q$  we do the following. For every $\alpha \in H\left(d\right)\{H}_{n}\left(d\right)$  consider the polynomial ${f}_{M}$  of  5.3 associated with the monomial $M={t}_{1{\alpha }_{1}}\cdots {t}_{m{\alpha }_{m}}$  . Set ${L}_{\alpha }={f}_{M}$  . So for all $\alpha \in H\left(d\right)\{H}_{n}\left(d\right)$  we have ${L}_{\alpha }={t}_{\alpha }-{\sum }_{\beta <\alpha }{\lambda }_{\alpha \beta }{t}_{\beta }\text{with}{\lambda }_{\alpha \beta }\in K$  and the arguments of  3.4 show that the ${L}_{\alpha }$  's form a Gröbner basis of $Q$  for any term order such that ${t}_{ij}>{t}_{ij-1}$  for all $i,j$  . It follows that $in\left(Q\right)=\left({t}_{1{\alpha }_{1}}\cdots {t}_{m{\alpha }_{m}}:\alpha \in H\left(d\right)\{H}_{n}\left(d\right)\right)$  for any term order such that ${t}_{ij}>{t}_{ij-1}$  for all $i,j$  . Then ${T}^{*}/in\left(Q\right)$  is defined as a quotient of $K\left[{s}_{\alpha }:\alpha \in H\left(d\right)\right]$  by:
(1) the Hibi relations ${s}_{\alpha }{s}_{\beta }-{s}_{\alpha \vee \beta }{s}_{\alpha \wedge \beta }$  with $\alpha ,\beta \in H\left(d\right)$  incomparable.
(2) ${s}_{\alpha }$  with $\alpha \in H\left(d\right)\{H}_{n}\left(d\right)$  .
It is easy to see that the elements of type (1) and (2) form a Gröbner basis for any revlex linear extension of the partial order on $H\left(d\right)$  . Hence a $K$  -basis of ${T}^{*}/in\left(Q\right)$  is given by the monomials not in ${J}_{{H}_{n}\left(d\right)}+\left(H\left(d\right)\{H}_{n}\left(d\right)\right)$  . This in turns implies that the Hibi relations and the relation ${L}_{\alpha }$  form a Gröbner basis with respect to any revlex linear extension of the partial order on $H\left(d\right)$  of the defining ideal of $A\left(V\right)$  as a quotient of $K\left[{s}_{\alpha }:\alpha \in H\left(d\right)\right]$  by the map sending ${s}_{\alpha }$  to ${f}_{1{\alpha }_{1}}\cdots {f}_{m{\alpha }_{m}}$  .
Summing up, we have:
Theorem 5.7. Let ${V}_{1},...,{V}_{m}$  be generic spaces of dimension ${d}_{1},...,{d}_{m}$  and take generic generators ${f}_{ij}$  of ${V}_{i}$  . Then:
• (1) We have a surjective $K$  -algebra homomorphism $F:K\left[{s}_{\alpha }:\alpha \in {H}_{n}\left(d\right)\right]\to A\left(V\right)$  sending the variable ${s}_{\alpha }$  to ${f}_{1{\alpha }_{1}}\cdots {f}_{m{\alpha }_{m}}$  .
• (2) $KerF$  is generated by two types of polynomials:
• (a) ${s}_{\alpha }{s}_{\beta }-{s}_{\alpha \vee \beta }{s}_{\alpha \wedge \beta }$  if $\alpha ,\beta \in {H}_{n}\left(d\right)$  are incomparable and $\alpha \vee \beta \in {H}_{n}\left(d\right)$  .
• (b) ${s}_{\alpha }{s}_{\beta }-\sum {\lambda }_{\gamma }{s}_{\gamma }{s}_{\alpha \wedge \beta }$  if $\alpha ,\beta \in {H}_{n}\left(d\right)$  are incomparable and $\alpha \vee \beta \notin {H}_{n}\left(d\right)$  and the sum is extended to the $\gamma \in {H}_{n}\left(d\right)$  with $\gamma \le \alpha \vee \beta$  and ${\lambda }_{\gamma }\in K$  (and depends also on $\alpha$  and $\beta$  ).
• (3) The polynomials of type (a) and (b) form a Gröbner basis of $KerF$  with respect to any revlex linear extension of the partial order of ${H}_{n}\left(d\right)$  .
• (4) $A\left(V\right)$  is a homogeneous ASL on the poset ${H}_{n}\left(d\right)$  .
• (5) $A\left(V\right)$  is normal, Cohen-Macaulay and Koszul.
• (6) $A\left(V\right)$  is defined, as a quotient of the Segre product ${T}^{*}$  , by a Gröbner basis of linear forms.
• (7) The Krull dimension of $A\left(V\right)$  is $min\left\{n,dim{T}^{*}=1-m+{\sum }_{i=1}^{m}{d}_{i}\right\}$  and its degree is the number of maximal chains in ${H}_{n}\left(d\right)$  .
• Proof. (1), (2), (3) and (6) follows immediately from the discussion above and (4) follows  5.5 and (3). As for (5), normality is proved in  2.2 , Koszulness follows from the general argument of Section  4 and also from (3). The Cohen-Macaulay property and (7) follows from (4) by applying [4,Chap.5since ${H}_{n}\left(d\right)$  is a wonderful poset.
As a corollary we obtain:
Corollary 5.8. For every $m$  and $n$  , the Veronese subring ${R}^{\left(m\right)}$  of $R=K\left[{x}_{1},...,{x}_{n}\right]$  is an ASL on the poset ${H}_{n}\left(d\right)$  where $d=n,n,...,n$  ( $m$  -times).
Remark 5.9. The realization of the $m$  -th Veronese subring of a polynomial ring in $n$  variables as a homogeneous ASL has been done before for $n=2$  and any $m$  in [22, for $n=m=3$  in [15and in two different ways, and for $n=m=4$  in [23.
An interesting consequence of  5.6 is:
Corollary 5.10. Let ${V}_{1},...,{V}_{m}$  be subspaces of ${R}_{1}$  of dimension ${d}_{1},{d}_{2},...,{d}_{m}$  then:
• (a) $dim{\Pi }_{i=1}^{m}{V}_{i}\le |{H}_{n}\left(d\right)|$  .
• (b) if the ${V}_{i}$  are generic then $dim{\Pi }_{i=1}^{m}{V}_{i}=|{H}_{n}\left(d\right)|$  .
• (c) if the ${V}_{i}$  are generic and if ${f}_{ij}$  with $j=1,...,{d}_{i}$  are generic generators of ${V}_{i}$  then the set $\left\{{f}_{1{j}_{1}}\cdots {f}_{m{j}_{m}}:\left({j}_{1},...,{j}_{m}\right)\in {H}_{n}\left(d\right)\right\}$  is a $K$  -basis of ${\Pi }_{i=1}^{m}{V}_{i}$  .
• (d) if the ${V}_{i}$  are generic then: $dim{\Pi }_{i=1}^{m}{V}_{i}={\Pi }_{i=1}^{m}dim{V}_{i}$  iff $\sum dim{V}_{i}  .
• Proof. Obviously (b) implies (a) and also (c) implies (b) and (d). So we have only to prove (c). By definition, the product ${\Pi }_{i=1}^{m}{V}_{i}$  is the component of degree $\left(1,1,...,1\right)$  of the algebra $B\left(V\right)$  . Then the conclusion follows from  5.6 .
Example 5.11. Take $n=3$  and ${d}_{1}={d}_{2}={d}_{3}=2$  and generic spaces ${V}_{i}$  of dimension ${d}_{i}$  . Note that, up to a choice of coordinates, we are in the situation of Example  3.8 and so the structure of $A\left(V\right)$  has been already identified. But to describe the the ASL structure of $A\left(V\right)$  we have take generic coordinates for the ${V}_{i}$  , say ${V}_{i}=〈{f}_{i1},{f}_{i,2}〉$  . In this case ${H}_{n}\left(d\right)$  is the cube $\left\{1,2{\right\}}^{3}$  without the point $\left(2,2,2\right)$  . We have a relation ${f}_{12}{f}_{22}{f}_{32}={\sum }_{\alpha \in {H}_{n}\left(d\right)}{\lambda }_{\alpha }{f}_{1{\alpha }_{1}}{f}_{2{\alpha }_{2}}{f}_{3{\alpha }_{3}}.$  Set $L={\sum }_{\alpha \in {H}_{n}\left(d\right)}{\lambda }_{\alpha }{s}_{\alpha }$  . Then the defining equations of $A\left(V\right)$  as a quotient of $K\left[{s}_{\alpha }:\alpha \in {H}_{n}\left(d\right)\right]$  are:
 $\begin{array}{ccc}{s}_{112}{s}_{221}-{s}_{111}L,& {s}_{121}{s}_{212}-{s}_{111}L,& {s}_{211}{s}_{122}-{s}_{111}L,\end{array}$
 $\begin{array}{ccc}{s}_{121}{s}_{211}-{s}_{111}{s}_{221},& {s}_{112}{s}_{211}-{s}_{111}{s}_{212},& {s}_{112}{s}_{121}-{s}_{111}{s}_{122},\end{array}$
 $\begin{array}{ccc}{s}_{212}{s}_{221}-{s}_{211}L,& {s}_{122}{s}_{221}-{s}_{121}L,& {s}_{122}{s}_{212}-{s}_{112}L\end{array}$
Remark 5.12. With an argument similar to that of  2.2 one can prove that the algebra $B\left(V\right)$  is normal for any $V={V}_{1},...,{V}_{m}$  . Furthermore, in the monomial and in the generic case one can prove that $B\left(V\right)$  is Cohen-Macaulay. In the monomial case the Cohen-Macaulayness is a consequence of the normality. In generic case it follows form the fact that, by  5.1 , we can describe an initial ideal of its defining ideal and such initial ideal turns out to be associated with a shellable simplicial complex.
References

1. A.Aramova, K.Crona, E.De Negri Bigeneric initial ideals, diagonal subalgebras and bigraded Hilbert functions. J. Pure Appl. Algebra 150 (2000),no. 3, 215–235.
2. W.Bruns, A.Conca, Gröbner bases and determinantal ideals. Commutative algebra, singularities and computer algebra (Sinaia, 2002), 9–66, NATO Sci. Ser. II Math. Phys. Chem., 115, Kluwer Acad. Publ., Dordrecht, 2003.
3. W. Bruns and J. Herzog, Cohen-Macaulay Rings, Cambridge University Press, Cambridge, 1996.
4. W.Bruns, U.Vetter, Determinantal rings. Lecture Notes in Mathematics, 1327. Springer-Verlag, Berlin, 1988.
5. CoCoA Team, CoCoA: a system for doing Computations in Commutative Algebra, Available at http://cocoa.dima.unige.it
6. A.Conca, J.Herzog Castelnuovo-Mumford regularity of products of ideals. Collect. Math. 54 (2003), no. 2, 137–152.
7. C.De Concini, D.Eisenbud, C.Procesi, Hodge algebras, Astérisque, 91. Société Mathématique de France, Paris, 1982. 87 pp.
8. E.De Negri, Toric rings generated by special stable sets of monomials. Math. Nachr. 203 (1999), 31–45.
9. J. Edmonds, Submodular functions, matroids, and certain polyhedra, in Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Schonheim (Eds.), Gordon and Breach, New York, 1970, pp. 69–87.
10. D.Eisenbud, Introduction to algebras with straightening laws. Ring theory and algebra, III (Proc. Third Conf., Univ. Oklahoma, Norman, Okla., 1979), pp. 243–268, Lecture Notes in Pure and Appl. Math., 55, Dekker, New York, 1980.
11. J.Herzog and T.Hibi, Discrete polymatroids. J. Algebraic Combin. 16 (2002), no. 3, 239–268.
12. J.Herzog and T.Hibi, G.Restuccia Strongly Koszul algebras. Math. Scand. 86 (2000), no. 2, 161–178.
13. J.Herzog and N.V.Trung, Gröbner bases and multiplicity of determinantal and Pfaffian ideals. Adv. Math. 96 (1992), no. 1, 1–37.
14. T.Hibi, Distributive lattices, affine semigroup rings and algebras with straightening laws. Commutative algebra and combinatorics (Kyoto, 1985), 93–109,Adv. Stud. Pure Math., 11, North-Holland, Amsterdam, 1987.
15. T.Hibi, K.Watanabe, Study of three-dimensional algebras with straightening laws which are Gorenstein domains. I. Hiroshima Math. J. 15 (1985), no. 1, 27–54.
16. T.Hibi, K.Watanabe, Study of three-dimensional algebras with straightening laws which are Gorenstein domains. II. Hiroshima Math. J. 15 (1985), no. 2, 321–340.
17. T.Hibi, Study of three-dimensional algebras with straightening laws which are Gorenstein domains. III. Hiroshima Math. J. 18 (1988), no. 2, 299–308.
18. J. Oxley, Matroid Theory, Oxford University Press, Oxford, 1992.
19. J.Roos, A description of the homological behaviour of families of quadratic forms in four variables, in Syzygies and Geometry, Boston 1995, A.Iarrobino, A.Martsinkovsky and J.Weyman eds., pp.86-95, Northeastern Univ. 1995.
20. B.Sturmfels, Gröbner Bases and Convex Polytopes, Amer. Math. Soc., Providence, RI,1995.
21. R.Villarreal, Monomial algebras. Monographs and Textbooks in Pure and Applied Mathematics, 238. Marcel Dekker, Inc., New York, 2001.
22. K.Watanabe, Study of algebras with straightening laws of dimension $2$  . Algebraic and topological theories (Kinosaki, 1984), 622–639, Kinokuniya, Tokyo, 1986.
23. K.Watanabe, Study of four-dimensional Gorenstein ASL domains. I. Integral posets arising from triangulations of a $2$  -sphere. Commutative algebra and combinatorics (Kyoto, 1985), 313–335, Adv. Stud. Pure Math., 11, North-Holland, Amsterdam, 1987.
24. V.Weispfenning, Comprehensive Gröbner bases. J. Symbolic Comput. 14 (1992), no. 1, 1–29.
25. D.Welsh, Matroid Theory, Academic Press, London, 1976.
26. N. White, A unique exchange property for bases, Linear Algebra Appl. 31 (1980), 81–91.

Dipartimento di Matematica, Universita di Genova, Genova, Italy E-mail address : conca@dima.unige.it