No CrossRef data available.
Article contents
SIMPLE EXTENSIONS OF COMBINATORIAL STRUCTURES
Published online by Cambridge University Press: 21 December 2010
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
An interval in a combinatorial structure R is a set I of points that 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 𝒞 can be embedded into a simple structure from 𝒞 by adding at most f(n) elements. We prove such results when 𝒞 is the class of all tournaments, graphs, permutations, posets, digraphs, oriented graphs and general relational structures containing a relation of arity greater than two. The functions f(n) in these cases are 2, ⌈log 2(n+1)⌉, ⌈(n+1)/2⌉, ⌈(n+1)/2⌉, ⌈log 4(n+1)⌉, ⌈log 3(n+1)⌉ and 1, respectively. In each case these bounds are the best possible.
Information
- Type
- Research Article
- Information
- Copyright
- Copyright © University College London 2010
References
[1]Bergeron, A., Chauve, C., de Montgolfier, F. and Raffinot, M., Computing common intervals of K permutations, with applications to modular decomposition of graphs. In Algorithms—ESA 2005 (Lecture Notes in Computer Science 3669), Springer (Berlin, 2005), 779–790.Google Scholar
[2]Brandstädt, A., Le, V. B. and Spinrad, J. P., Graph Classes: A Survey (SIAM Monographs on Discrete Mathematics and Applications 3), Society for Industrial and Applied Mathematics (SIAM) (Philadelphia, PA, 1999).Google Scholar
[3]Brignall, R., A survey of simple permutations. In Permutation Patterns (London Mathematical Society Lecture Note Series 376) (eds Linton, S., Ruškuc, N. and Vatter, V.), Cambridge University Press (Cambridge, 2010), 41–65.Google Scholar
[4]Cournier, A. and Habib, M., A new linear algorithm for modular decomposition. In Trees in Algebra and Programming—CAAP ’94 (Edinburgh, 1994) (Lecture Notes in Computer Science 787), Springer (Berlin, 1994), 68–84.Google Scholar
[5]Crvenković, S., Dolinka, I. and Marković, P., A survey of algebra of tournaments. Novi Sad J. Math. 29 (1999), 95–130.Google Scholar
[6]Dahlhaus, E., Gustedt, J. and
McConnell, R. M., Efficient and practical modular decomposition. In Proceedings of the Eighth Annual ACM–SIAM Symposium on Discrete Algorithms (New Orleans, LA, 1997), ACM (New York, 1997), 26–35.Google Scholar
[7]Ehrenfeucht, A., Harju, T. and Rozenberg, G., The Theory of 2-Structures, World Scientific Publishing Co. Inc. (River Edge, NJ, 1999).Google Scholar
[8]Erdős, P., Fried, E., Hajnal, A. and Milner, E. C., Some remarks on simple tournaments. Algebra Universalis 2 (1972), 238–245.Google Scholar
[9]Erdős, P., Hajnal, A. and Milner, E. C., Simple one-point extensions of tournaments. Mathematika 19 (1972), 57–62.Google Scholar
[10]Földes, S., On intervals in relational structures. Z. Math. Logik Grundlag. Math. 26(2) (1980), 97–101.Google Scholar
[11]Fraïssé, R., On a decomposition of relations which generalizes the sum of ordering relations. Bull. Amer. Math. Soc. 59 (1953), 389.Google Scholar
[12]Gallai, T., Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hungar. 18 (1967), 25–66.Google Scholar
[13]Gallai, T., A Translation of T. Gallai’s Paper: Transitiv Orientierbare Graphen (Wiley-Interscience Series in Discrete Mathematics and Optimization), Wiley (Chichester, 2001), 25–66.Google Scholar
[15]McConnell, R. M. and de Montgolfier, F., Linear-time modular decomposition of directed graphs. Discrete Appl. Math. 145(2) (2005), 198–209.Google Scholar
[16]McConnell, R. M. and Spinrad, J. P., Modular decomposition and transitive orientation. Discrete Math. 201(1–3) (1999), 189–241.Google Scholar
[17]Möhring, R. H., On the distribution of locally undecomposable relations and independence systems. In Colloquium on Mathematical Methods of Operations Research (Aachen, 1980) (Methods of Operations Research 42), Athenäum/Hain/Hanstein (Königstein/Ts, 1981), 33–48.Google Scholar
[18]Möhring, R. H., An algebraic decomposition theory for discrete structures. In Universal Algebra and its Links with Logic, Algebra, Combinatorics and Computer Science (Darmstadt, 1983) (Research and Exposition in Mathematics 4), Heldermann (Berlin, 1984), 191–203.Google Scholar
[19]Möhring, R. H., Algorithmic aspects of comparability graphs and interval graphs. In Graphs and Order (Banff, Alta., 1984) (NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences 147), Reidel (Dordrecht, 1985), 41–101.Google Scholar
[20]Möhring, R. H. and Radermacher, F. J., Substitution decomposition for discrete structures and connections with combinatorial optimization. In Algebraic and Combinatorial Methods in Operations Research (North-Holland Mathematics Studies 95), North-Holland (Amsterdam, 1984), 257–355.Google Scholar
[21]Moon, J. W., Embedding tournaments in simple tournaments. Discrete Math. 2 4 (1972), 389–395.Google Scholar
[23]Sumner, D. P., Indecomposable graphs. PhD Thesis, University of Massachusetts, 1971.Google Scholar
You have
Access
- 3
- Cited by