The Open UniversitySkip to content

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:
PDF (Accepted Manuscript) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (213kB)
DOI (Digital Object Identifier) Link:
Google Scholar: Look up in Google Scholar


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, ⌈log2(n + 1)⌉, ⌈(n + 1)/2⌉, ⌈(n + 1)/2⌉, ⌈log4(n + 1)⌉, ⌈log3(n + 1)⌉ and 1, respectively. In each case these bounds are best possible.

Item Type: Journal Item
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/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 29672
Depositing User: Robert Brignall
Date Deposited: 06 Oct 2011 08:38
Last Modified: 07 Dec 2018 23:59
Share this page:


Altmetrics from Altmetric

Citations from Dimensions

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU