EPSRC logo

Details of Grant 

EPSRC Reference: EP/J006130/1
Title: Infinite Antichains of Combinatorial Structures
Principal Investigator: Brignall, Dr R
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Pure Mathematics
Organisation: The Open University
Scheme: First Grant - Revised 2009
Starts: 01 October 2012 Ends: 30 September 2013 Value (£): 91,797
EPSRC Research Topic Classifications:
Logic & Combinatorics
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
05 Sep 2011 Mathematics Prioritisation Panel Meeting September 2011 Announced
Summary on Grant Application Form
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.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: