...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >A short proof of non-GF(5)-representability of matroids
【24h】

A short proof of non-GF(5)-representability of matroids

机译：拟阵的非GF（5）可表示性的简短证明

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

摘要

Tutte proved that a matroid is binary if and only if it does not contain a U-2,U-4-minor. This provides a short proof for non-GF(2)-representability in that we can verify that a given minor is isomorphic to U-2,U-4 in just a few rank evaluations. Using excluded-minor characterizations, short proofs can also be given of non-representablity over GF(3) and over GF(4). For GF(5), it is not even known whether the set of excluded minors is finite. Nevertheless, we show here that if a matroid is not representable over GF(5), then this can be verified by a short proof. Here a "short proof" is a proof whose length is bounded by some polynomial in the number of elements of the matroid. In contrast to these positive results, Seymour showed that we require exponentially many rank evaluations to prove GF(2)-representability, and this is in fact the case for any field. (C) 2003 Elsevier Inc. All rights reserved.
机译：Tutte证明，仅当不包含U-2，U-4-未成年人时，拟阵是二元的。这为非GF（2）可表示性提供了简短的证明，因为我们可以在仅几次等级评估中验证给定的未成年人与U-2，U-4同构。使用排除的次要特征，也可以给出关于GF（3）和GF（4）的非代表性的简短证明。对于GF（5），甚至不知道被排除的未成年人的集合是否有限。然而，我们在这里表明，如果拟阵不能通过GF（5）表示，那么可以用一个简短的证明来验证。在这里，“短证明”是证明其长度由拟阵中的元素数量的多项式确定的证明。与这些积极的结果相反，西摩表明我们需要指数级的等级评估来证明GF（2）的可表示性，而实际上对于任何领域都是如此。 （C）2003 Elsevier Inc.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号