Infinite Antichains of Combinatorial Structures

在过去的50年里，组合学中一些最著名的结果涉及到组合结构的良好准序的研究，即在各种自然序下，图、竞赛图或置换等对象的无限反链的存在性或其他问题。在某些情况下不存在无限反链（例如次序下的图），但在其他情况下它们确实存在，并且对于某些结构它们大量出现。PI最近的研究开发了一种用于无限排列反链的一般构造，预计将给出一种可更普遍地用于其他组合结构的技术。这将被扩展到的第一个对象是那些可以被描述为“关系结构”的对象：这些对象包括图、竞赛图、置换和偏序集。本质上，我们在研究良拟序时需要考虑的唯一无限反链是“基本”反链，它们满足某些附加性质，确保它们没有冗余结构。由PI提出的反链结构不仅进一步证明了基本反链实际上具有比它们的定义所保证的更规则的结构，而且还表明了这种规则性的本质。这导致PI假设，基本的反链的组合结构有一个“脊柱”-一个蓝图，从所有，但100%的反链元素创建。采取统一的观点，这个建议是为了调查这一假设的各个方面，推进研究无限反链一般，借鉴和加强各种结构之间的连接。出发点在于现有的结果排列。这些将被扩展并转化为图形和其他关系结构，其中存在不同的技术并可以应用。这将使“交叉受精”发生，因此可以建立一个更完整的无限反链理论，为PI的假设提供证据。

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.