• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Order >Irreducible Width 2 Posets of Linear Discrepancy 3
【24h】

Irreducible Width 2 Posets of Linear Discrepancy 3

机译：不可约宽度2线性差异的点集3

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then ∣h_L(x) - h_L(y)∣≤ k, where h_L(x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139-153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width 2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique linear extension that witnesses linear discrepancy 2.
机译：位姿P的线性差异至少为k，从而存在P的线性扩展L，使得如果x和y在P中不可比，则∣h_L（x）-h_L（y）∣≤ k，其中h_L（ Tannenbaum，Trunk和Fishburn将线性差异1的样态描述为宽度2的半数，并提出了表征线性差异2的样态的问题。 （第24：139-153号命令，2007年）表明，此问题等同于找到线性差异3的所有样态，以便去除任何点都会减小线性差异。在本文中，我们确定所有具有宽度2的线性差异3的所有最小姿态。我们通过显示出，当在最小线性差异3姿态中移除特定的最大点时，有一个唯一的线性扩展见证了线性差异2。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号