Optimal linear arrangement of a rectangular grid (Q1970706): Difference between revisions

The authors prove the following results. Suppose \(m\geq n\geq 2\). Denote by \(F\) the set of all assignments from \(V_{mn}\) onto \(\{1,2,\dots, mn\}\), and for all \(f\in F\) define \(L(f)\) by \[ L(f)= \sum_{\{u,v\}\in E_{mn}}|f(u)- f(v)|. \] For each \(t\in \{1,2,\dots, \lfloor n/2\rfloor\}\) denote by \(f^{(t)}\) the member of \(F\) that is doubly monotonic, complementary, has pattern \(R_t(m,n)\) in the first \(t\) rows of its assignment matrix with horizontal slats in rows \(t\) through \(m-t\). Then \[ \min_{f\in F} L(f)= L(f^{(t^*)})= m(n^2+ n-1)- n- t^*[2(t^*)^2- 6nt^*+ 3n^2+ 3n- 2]/3, \] where \(t^*\) denotes the value of \(t\in \{1,2,\dots, \lfloor n/2\rfloor\}\) that maximizes \(2t^3- 6nt^2+ (3n^2+ 3n- 2)t\).