Simple extensions of combinatorial structures

Brignall, Robert; Ruškuc, Nik and Vatter, Vincent (2011). Simple extensions of combinatorial structures. Mathematika, 57(02), pp. 193–214.

Full text available as:

Preview

PDF (Accepted Manuscript) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (208Kb)

DOI (Digital Object Identifier) Link:	http://dx.doi.org/doi:10.1112/S0025579310001518
Google Scholar:	Look up in Google Scholar

Abstract

An interval in a combinatorial structure R is a set I of points which are related to every point in R\I in the same way. A structure is simple if it has no proper intervals. Every combinatorial structure can be expressed as an inflation of a simple structure by structures of smaller sizes — this is called the substitution (or modular) decomposition. In this paper we prove several results of the following type: An arbitrary structure S of size n belonging to a class C can be embedded into a simple structure from C by adding at most f(n) elements. We prove such results when C is the class of all tournaments, graphs, permutations, posets, digraphs, oriented graphs and general relational structures containing a relation of arity greater than 2. The function f(n) in these cases is 2, ⌈log₂(n + 1)⌉, ⌈(n + 1)/2⌉, ⌈(n + 1)/2⌉, ⌈log₄(n + 1)⌉, ⌈log₃(n + 1)⌉ and 1, respectively. In each case these bounds are best possible.

Item Type:	Journal Article
Copyright Holders:	2010 University College London
ISSN:	2041-7942
Keywords:	indecomposable graph; modular decomposition; prime graph; simple permutation; simple poset; simple tournament; substitution decomposition
Academic Unit/Department:	Mathematics, Computing and Technology > Mathematics and Statistics
Item ID:	29672
Depositing User:	Robert Brignall
Date Deposited:	06 Oct 2011 08:38
Last Modified:	09 Dec 2012 05:05
URI:	http://oro.open.ac.uk/id/eprint/29672

Available Versions of this Item

• Simple extensions of combinatorial structures. (deposited 12 Sep 2011 09:54)
  • Simple extensions of combinatorial structures. (deposited 06 Oct 2011 08:38) [Currently Displayed]

Actions (login may be required)

	View Item
RDF+XMLBibTeXRDF+N-TriplesJSONDublin CoreAtomOAI-ORE Resource Map (Atom Format)Simple MetadataReferMETSOAI-ORE Resource Map (RDF Format)HTML CitationASCII CitationMultiline CSVRefMan RIS Format (UTF-8)OpenURL ContextObjectEndNoteMODSOpenURL ContextObject in SpanMPEG-21 DIDLEP3 XMLRefMan RIS FormatRDF+N3Eprints Application Profile	Public: Report issue / request change