Infinite Antichains of 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.