Infinite Antichains of Combinatorial Structures

组合结构的无限反链

基本信息

批准号：
EP/J006130/1
负责人：
Robert Laurence Francis Brignall
金额：
$ 11.7万
依托单位：
The Open University
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2012
资助国家：
英国
起止时间：
2012 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FJ006130%2F1
关键词：
Infinite Antichains Combinatorial Structures

项目摘要

Some of the most celebrated results in combinatorics of the last 50 years concern the study of well-quasi-ordering of combinatorial structures, i.e. the existence, or otherwise, of infinite antichains for objects such as graphs, tournaments or permutations under various natural orderings. In certain cases no infinite antichains exist (for example graphs under the minor ordering), but in others they do exist, and for some structures they appear in abundance. Recent research by the PI has developed a general construction for infinite antichains of permutations, which it is expected to give a technique that can be used more generally for other combinatorial structures. The first objects that this will be extended to are those that can be described as "relational structures": these include graphs, tournaments, permutations and posets.Essentially the only infinite antichains that we need to consider in the study of well-quasi-order are "fundamental" ones, which satisfy certain additional properties that ensure they have no redundant structure. The antichain constructions developed by the PI not only add to the body of evidence that the fundamental antichains in fact have a much more regular structure than is guaranteed by their definition, but also suggest the nature of this regularity. This has led the PI to hypothesise that the fundamental antichains of combinatorial structures have a "spine" -- a blueprint from which all but finitely many of the antichain elements are created.Taking a unified viewpoint, this proposal is designed to investigate aspects of this hypothesis by advancing the study of infinite antichains in general, drawing on and strengthening the connections between the various structures. The starting point lies with the existing results for permutations. These will be extended and translated to graphs and other relational structures, where different techniques exist and can be applied. This will enable "cross-fertilisation" to occur, and consequently a more complete theory of infinite antichains can be built to provide evidence for or against the PI's hypothesis.

过去50年中，一些最著名的结果涉及组合结构的良好顺序的研究，即在各种自然订购下的图形，锦标赛或排列物（例如图形，锦标赛或排列）的无限敌人的存在或其他方式。在某些情况下，没有无限的敌人（例如，在次要订购下的图形），但在其他情况下确实存在，对于某些结构，它们出现了丰富。 PI的最新研究开发了无限抗逆想的一般结构，预计该技术将提供一种可以在其他组合结构中更普遍使用的技术。将其扩展到的第一个对象是可以将其描述为“关系结构”的物体：其中包括图，锦标赛，排列和posets。实际上，我们在良好的Quasi-Order研究中需要考虑的唯一无限的敌人是“基本”是“基本”的敌人，这些敌人可以满足其确保它们没有冗余结构的某些其他特性。 PI开发的抗抗小构建体不仅增加了基本敌人实际上具有比其定义所保证的更正常结构的证据，而且还暗示了这种规律性的性质。这使PI假设组合结构的基本抗具有“脊柱” - 一种蓝图 - 几乎所有几乎有限的许多抗元素都被创建了。提出一个统一的观点，该提议旨在通过促进Infientient Antifient Antifient ant Infichient Antifient and temants interty Structions thrands Structions temants nounding and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and consents andy，均匀的结构来研究该假设的各个方面。起点在于现有的排列结果。这些将扩展并转化为图形和其他关系结构，其中存在不同的技术并可以应用。这将使“交叉施肥”能够发生，因此，可以建立更完整的无限敌人理论，以提供或反对PI假设的证据。