文献

J-GLOBAL ID：201802297875718699   整理番号：18A1133834

Kneser-Lovasz彩色原理の短い証明【JST・京大機械翻訳】

Short proofs of the Kneser-Lovasz coloring principle

著者 (5件)： Aisenberg James (Department of Mathematics, University of California, San Diego, La Jolla, CA 92093-0112, USA) ,  Bonet Maria Luisa (Computer Science Department, Universidad Politecnica de Cataluna, Barcelona, Spain) ,  Buss Sam (Department of Mathematics, University of California, San Diego, La Jolla, CA 92093-0112, USA) ,  Craciun Adrian (West University of Timisoara, and the e-Austria Research Institute, Timisoara, RO-300223, Romania) ,  Istrate Gabriel (West University of Timisoara, and the e-Austria Research Institute, Timisoara, RO-300223, Romania)
資料名： Information and Computation  (Information and Computation)
巻： 261  号： P2  ページ： 296-310  発行年： 2018年 
JST資料番号： D0449A  ISSN： 0890-5401  CODEN： INFCEC  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Kneser-Lovasz定理の命題変換は,kのすべての固定値に対して,多項式サイズ拡張Frege証明と準多項式サイズFrege証明を持つことを証明した。著者らは,Hilton-Milner定理に基づくKneser-Lovasz定理の新しい計数ベースの組合せ証明を提示した。これにより,すべての場合に対する事前の証明のトポロジー的議論を避けることができる。著者らは,八面体Tucker補助定理の小型化である,新しい「打切りTucker」の原理を紹介した。打切りTuckerの補助定理はKneser-Lovasz定理を意味する。著者らは,打切りTucker補助定理のk=1ケースが,多項式サイズ拡張Frege証明を持つことを示した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 多項式 ,  打切 ,  小型化 ,  *発色 ,  八面体 ,  位相幾何学 ,  命題
準シソーラス用語： 補題 , 【Automatic Indexing@JST】

分類 (2件)： 論理代数  (JB03000H) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： 彩色 ,  原理 ,  証明