Ordinals and graph decompositions

详细信息    查看全文

• 作者：Stephen Flood ; ^{sflood@alumni.nd.edu}
• 关键词：primary ; 03B80 ; secondary ; 05C63 ; 03D80 ; 03D35
• 刊名：Annals of Pure and Applied Logic
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：168
• 期：4
• 页码：824-839
• 全文大小：469 K
• 卷排序：168

文摘

The theory of simplicial graph decompositions studies the infinite graphs that are built from a sequence of irreducible graphs which are attached together at complete subgraphs. In this paper, we study the logical complexity of deciding if a graph is prime decomposable. A large part of this analysis involves determining which ordinals must appear in these types of decompositions.A result of Diestel says that every countable simplicial tree decomposition can be rearranged to have length at most ω. We show that no such ordinal bound can be found for the lengths of non-tree decompositions. More generally, we show that for each ordinal σ, there is a decomposable graph whose shortest simplicial decomposition has length exactly σ  . Adapting this argument, we show that the index set of decomposable computable graphs DECOMPDECOMP is Π11 hard by showing that WOWO is 1-reducible to DECOMPDECOMP.