Simple extensions of combinatorial structures

Details Simple extensions of combinatorial structures Simple extensions of combinatorial structures

2009-11-23

arxiv.org/abs/0911.4378v2

Mathematics

Combinatorics

24 pages, 9 figures

Scientific paper

An interval in a combinatorial structure S is a set I of points which relate to every point from S 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, \lceil log_2(n+1)\rceil, \lceil (n+1)/2\rceil, \lceil (n+1)/2\rceil, \lceil log_4(n+1)\rceil, \lceil \log_3(n+1)\rceil and 1, respectively. In each case these bounds are best possible.

Affiliated with

Also associated with

No associations

Rating

Simple extensions of combinatorial structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Simple extensions of combinatorial structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simple extensions of combinatorial structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-173168