Pure Mathematics Researchhttp://hdl.handle.net/10023/982021-10-27T07:14:45Z2021-10-27T07:14:45ZMaximal subsemigroups of finite transformation and diagram monoidsEast, JamesKumar, JitenderMitchell, James D.Wilson, Wilf A.http://hdl.handle.net/10023/171102021-01-12T11:42:21Z2018-06-15T00:00:00ZWe describe and count the maximal subsemigroups of many well-known transformation monoids, and diagram monoids, using a new unified framework that allows the treatment of several classes of monoids simultaneously. The problem of determining the maximal subsemigroups of a finite monoid of transformations has been extensively studied in the literature. To our knowledge, every existing result in the literature is a special case of the approach we present. In particular, our technique can be used to determine the maximal subsemigroups of the full spectrum of monoids of order- or orientation-preserving transformations and partial permutations considered by I. Dimitrova, V. H. Fernandes, and co-authors. We only present details for the transformation monoids whose maximal subsemigroups were not previously known; and for certain diagram monoids, such as the partition, Brauer, Jones, and Motzkin monoids. The technique we present is based on a specialised version of an algorithm for determining the maximal subsemigroups of any finite semigroup, developed by the third and fourth authors, and available in the Semigroups package for GAP, an open source computer algebra system. This allows us to concisely present the descriptions of the maximal subsemigroups, and to clearly see their common features.
The first author gratefully acknowledges the support of the Glasgow Learning, Teaching, and Research Fund in partially funding his visit to the third author in July, 2014. The second author wishes to acknowledge the support of research initiation grant [0076|2016] provided by BITS Pilani, Pilani. The fourth author wishes to acknowledge the support of his Carnegie Ph.D. Scholarship from the Carnegie Trust for the Universities of Scotland.
2018-06-15T00:00:00ZEast, JamesKumar, JitenderMitchell, James D.Wilson, Wilf A.We describe and count the maximal subsemigroups of many well-known transformation monoids, and diagram monoids, using a new unified framework that allows the treatment of several classes of monoids simultaneously. The problem of determining the maximal subsemigroups of a finite monoid of transformations has been extensively studied in the literature. To our knowledge, every existing result in the literature is a special case of the approach we present. In particular, our technique can be used to determine the maximal subsemigroups of the full spectrum of monoids of order- or orientation-preserving transformations and partial permutations considered by I. Dimitrova, V. H. Fernandes, and co-authors. We only present details for the transformation monoids whose maximal subsemigroups were not previously known; and for certain diagram monoids, such as the partition, Brauer, Jones, and Motzkin monoids. The technique we present is based on a specialised version of an algorithm for determining the maximal subsemigroups of any finite semigroup, developed by the third and fourth authors, and available in the Semigroups package for GAP, an open source computer algebra system. This allows us to concisely present the descriptions of the maximal subsemigroups, and to clearly see their common features.Computing maximal subsemigroups of a finite semigroupDonoven, C. R.Mitchell, J. D.Wilson, W. A.http://hdl.handle.net/10023/170722021-01-12T11:22:20Z2018-07-01T00:00:00ZA proper subsemigroup of a semigroup is maximal if it is not contained in any other proper subsemigroup. A maximal subsemigroup of a finite semigroup has one of a small number of forms, as described in a paper of Graham, Graham, and Rhodes. Determining which of these forms arise in a given finite semigroup is difficult, and no practical mechanism for doing so appears in the literature. We present an algorithm for computing the maximal subsemigroups of a finite semigroup S given knowledge of the Green's structure of S, and the ability to determine maximal subgroups of certain subgroups of S, namely its group H-classes. In the case of a finite semigroup S represented by a generating set X, in many examples, if it is practical to compute the Green's structure of S from X, then it is also practical to find the maximal subsemigroups of S using the algorithm we present. In such examples, the time taken to determine the Green's structure of S is comparable to that taken to find the maximal subsemigroups. The generating set X for S may consist, for example, of transformations, or partial permutations, of a finite set, or of matrices over a semiring. Algorithms for computing the Green's structure of S from X include the Froidure–Pin Algorithm, and an algorithm of the second author based on the Schreier–Sims algorithm for permutation groups. The worst case complexity of these algorithms is polynomial in |S|, which for, say, transformation semigroups is exponential in the number of points on which they act. Certain aspects of the problem of finding maximal subsemigroups reduce to other well-known computational problems, such as finding all maximal cliques in a graph and computing the maximal subgroups in a group. The algorithm presented comprises two parts. One part relates to computing the maximal subsemigroups of a special class of semigroups, known as Rees 0-matrix semigroups. The other part involves a careful analysis of certain graphs associated to the semigroup S, which, roughly speaking, capture the essential information about the action of S on its J-classes.
The third author wishes to acknowledge the support of his Carnegie Ph.D. Scholarship from the Carnegie Trust for the Universities of Scotland.
2018-07-01T00:00:00ZDonoven, C. R.Mitchell, J. D.Wilson, W. A.A proper subsemigroup of a semigroup is maximal if it is not contained in any other proper subsemigroup. A maximal subsemigroup of a finite semigroup has one of a small number of forms, as described in a paper of Graham, Graham, and Rhodes. Determining which of these forms arise in a given finite semigroup is difficult, and no practical mechanism for doing so appears in the literature. We present an algorithm for computing the maximal subsemigroups of a finite semigroup S given knowledge of the Green's structure of S, and the ability to determine maximal subgroups of certain subgroups of S, namely its group H-classes. In the case of a finite semigroup S represented by a generating set X, in many examples, if it is practical to compute the Green's structure of S from X, then it is also practical to find the maximal subsemigroups of S using the algorithm we present. In such examples, the time taken to determine the Green's structure of S is comparable to that taken to find the maximal subsemigroups. The generating set X for S may consist, for example, of transformations, or partial permutations, of a finite set, or of matrices over a semiring. Algorithms for computing the Green's structure of S from X include the Froidure–Pin Algorithm, and an algorithm of the second author based on the Schreier–Sims algorithm for permutation groups. The worst case complexity of these algorithms is polynomial in |S|, which for, say, transformation semigroups is exponential in the number of points on which they act. Certain aspects of the problem of finding maximal subsemigroups reduce to other well-known computational problems, such as finding all maximal cliques in a graph and computing the maximal subgroups in a group. The algorithm presented comprises two parts. One part relates to computing the maximal subsemigroups of a special class of semigroups, known as Rees 0-matrix semigroups. The other part involves a careful analysis of certain graphs associated to the semigroup S, which, roughly speaking, capture the essential information about the action of S on its J-classes.Phases of physics in J.D. Forbes’ Dissertation Sixth for the Encyclopaedia Britannica (1856)Falconer, Isobel Jessiehttp://hdl.handle.net/10023/166182021-05-25T07:30:16Z2018-12-03T00:00:00ZThis paper takes James David Forbes’ Encyclopaedia Britannica entry, Dissertation Sixth, as a lens to examine physics as a cognitive, practical, and social, enterprise. Forbes wrote this survey of eighteenth- and nineteenth-century mathematical and physical sciences, in 1852-6, when British “physics” was at a pivotal point in its history, situated between a discipline identified by its mathematical methods – originating in France - and one identified by its university laboratory institutions. Contemporary encyclopaedias provided a nexus for publishers, the book trade, readers, and men of science, in the formation of physics as a field. Forbes was both a witness, whose account of the progress of physics or natural philosophy can be explored at face value, and an agent, who exploited the opportunity offered by the Encyclopaedia Britannica in the mid nineteenth century to enrol the broadly educated public, and scientific collective, illuminating the connection between the definition of physics and its forms of social practice. Forbes used the terms “physics” and “natural philosophy” interchangeably. He portrayed the field as progressed by the natural genius of great men, who curated the discipline within an associational culture that engendered true intellectual spirit. Although this societal mechanism was becoming ineffective, Forbes did not see university institutions as the way forward. Instead, running counter to his friend William Whewell, he advocated inclusion of the mechanical arts (engineering), and a strictly limited role for mathematics. He revealed tensions when the widely accepted discovery-based historiography conflicted with intellectual and moral worth, reflecting a nineteenth-century concern with spirit that cuts across twentieth-century questions about discipline and field.
2018-12-03T00:00:00ZFalconer, Isobel JessieThis paper takes James David Forbes’ Encyclopaedia Britannica entry, Dissertation Sixth, as a lens to examine physics as a cognitive, practical, and social, enterprise. Forbes wrote this survey of eighteenth- and nineteenth-century mathematical and physical sciences, in 1852-6, when British “physics” was at a pivotal point in its history, situated between a discipline identified by its mathematical methods – originating in France - and one identified by its university laboratory institutions. Contemporary encyclopaedias provided a nexus for publishers, the book trade, readers, and men of science, in the formation of physics as a field. Forbes was both a witness, whose account of the progress of physics or natural philosophy can be explored at face value, and an agent, who exploited the opportunity offered by the Encyclopaedia Britannica in the mid nineteenth century to enrol the broadly educated public, and scientific collective, illuminating the connection between the definition of physics and its forms of social practice. Forbes used the terms “physics” and “natural philosophy” interchangeably. He portrayed the field as progressed by the natural genius of great men, who curated the discipline within an associational culture that engendered true intellectual spirit. Although this societal mechanism was becoming ineffective, Forbes did not see university institutions as the way forward. Instead, running counter to his friend William Whewell, he advocated inclusion of the mechanical arts (engineering), and a strictly limited role for mathematics. He revealed tensions when the widely accepted discovery-based historiography conflicted with intellectual and moral worth, reflecting a nineteenth-century concern with spirit that cuts across twentieth-century questions about discipline and field.Equilibrium states, pressure and escape for multimodal maps with holesDemers, Mark F.Todd, Mikehttp://hdl.handle.net/10023/152142021-05-23T01:03:22Z2017-09-01T00:00:00ZFor a class of non-uniformly hyperbolic interval maps, we study rates of escape with respect to conformal measures associated with a family of geometric potentials. We establish the existence of physically relevant conditionally invariant measures and equilibrium states and prove a relation between the rate of escape and pressure with respect to these potentials. As a consequence, we obtain a Bowen formula: we express the Hausdorff dimension of the set of points which never exit through the hole in terms of the relevant pressure function. Finally, we obtain an expression for the derivative of the escape rate in the zero-hole limit.
MD was partially supported by NSF grants DMS 1101572 and DMS 1362420. MT was partially supported by NSF grants DMS 0606343 and DMS 0908093.
2017-09-01T00:00:00ZDemers, Mark F.Todd, MikeFor a class of non-uniformly hyperbolic interval maps, we study rates of escape with respect to conformal measures associated with a family of geometric potentials. We establish the existence of physically relevant conditionally invariant measures and equilibrium states and prove a relation between the rate of escape and pressure with respect to these potentials. As a consequence, we obtain a Bowen formula: we express the Hausdorff dimension of the set of points which never exit through the hole in terms of the relevant pressure function. Finally, we obtain an expression for the derivative of the escape rate in the zero-hole limit.Two variants of the froidure-pin algorithm for finite semigroupsJonusas, JuliusMitchell, J. D.Pfeiffer, M.http://hdl.handle.net/10023/118792021-01-12T11:28:39Z2018-02-08T00:00:00ZIn this paper, we present two algorithms based on the Froidure-Pin Algorithm for computing the structure of a finite semigroup from a generating set. As was the case with the original algorithm of Froidure and Pin, the algorithms presented here produce the left and right Cayley graphs, a confluent terminating rewriting system, and a reduced word of the rewriting system for every element of the semigroup. If U is any semigroup, and A is a subset of U, then we denote by <A> the least subsemigroup of U containing A. If B is any other subset of U, then, roughly speaking, the first algorithm we present describes how to use any information about <A>, that has been found using the Froidure-Pin Algorithm, to compute the semigroup <A∪B>. More precisely, we describe the data structure for a finite semigroup S given by Froidure and Pin, and how to obtain such a data structure for <A∪B> from that for <A>. The second algorithm is a lock-free concurrent version of the Froidure-Pin Algorithm.
2018-02-08T00:00:00ZJonusas, JuliusMitchell, J. D.Pfeiffer, M.In this paper, we present two algorithms based on the Froidure-Pin Algorithm for computing the structure of a finite semigroup from a generating set. As was the case with the original algorithm of Froidure and Pin, the algorithms presented here produce the left and right Cayley graphs, a confluent terminating rewriting system, and a reduced word of the rewriting system for every element of the semigroup. If U is any semigroup, and A is a subset of U, then we denote by <A> the least subsemigroup of U containing A. If B is any other subset of U, then, roughly speaking, the first algorithm we present describes how to use any information about <A>, that has been found using the Froidure-Pin Algorithm, to compute the semigroup <A∪B>. More precisely, we describe the data structure for a finite semigroup S given by Froidure and Pin, and how to obtain such a data structure for <A∪B> from that for <A>. The second algorithm is a lock-free concurrent version of the Froidure-Pin Algorithm.Effects of thermal conduction and compressive viscosity on the period ratio of the slow modeMacnamara, Cicely KrystynaRoberts, Bernardhttp://hdl.handle.net/10023/84232021-03-21T05:31:20Z2010-06-01T00:00:00ZAims: Increasing observational evidence of wave modes brings us to a closer understanding of the solar corona. Coronal seismology allows us to combine wave observations and theory to determine otherwise unknown parameters. The period ratio, P1/2P2, between the period P1 of the fundamental mode and the period P2 of its first overtone, is one such tool of coronal seismology and its departure from unity provides information about the structure of the corona. Methods: We consider analytically the effects of thermal conduction and compressive viscosity on the period ratio for a longitudinally propagating sound wave. Results: For coronal values of thermal conduction the effect on the period ratio is negligible. For compressive viscosity the effect on the period ratio may become important for some short hot loops. Conclusions: Damping typically has a small effect on the period ratio, suggesting that longitudinal structuring remains the most significant effect.
C.K.M. acknowledges financial support from the CarnegieTrust. Discussions with Dr. I. De Moortel and Prof. A. W. Hood are gratefully acknowledged
2010-06-01T00:00:00ZMacnamara, Cicely KrystynaRoberts, BernardAims: Increasing observational evidence of wave modes brings us to a closer understanding of the solar corona. Coronal seismology allows us to combine wave observations and theory to determine otherwise unknown parameters. The period ratio, P1/2P2, between the period P1 of the fundamental mode and the period P2 of its first overtone, is one such tool of coronal seismology and its departure from unity provides information about the structure of the corona. Methods: We consider analytically the effects of thermal conduction and compressive viscosity on the period ratio for a longitudinally propagating sound wave. Results: For coronal values of thermal conduction the effect on the period ratio is negligible. For compressive viscosity the effect on the period ratio may become important for some short hot loops. Conclusions: Damping typically has a small effect on the period ratio, suggesting that longitudinal structuring remains the most significant effect.Maximal subsemigroups of the semigroup of all mappings on an infinite setEast, J.Mitchell, James DavidPéresse, Y.http://hdl.handle.net/10023/57932021-08-29T05:30:38Z2015-03-01T00:00:00ZIn this paper we classify the maximal subsemigroups of the full transformation semigroup ΩΩ, which consists of all mappings on the infinite set Ω, containing certain subgroups of the symmetric group Sym (Ω) on Ω. In 1965 Gavrilov showed that there are five maximal subsemigroups of ΩΩ containing Sym (Ω) when Ω is countable, and in 2005 Pinsker extended Gavrilov's result to sets of arbitrary cardinality. We classify the maximal subsemigroups of ΩΩ on a set Ω of arbitrary infinite cardinality containing one of the following subgroups of Sym (Ω): the pointwise stabiliser of a non-empty finite subset of Ω, the stabiliser of an ultrafilter on Ω, or the stabiliser of a partition of Ω into finitely many subsets of equal cardinality. If G is any of these subgroups, then we deduce a characterisation of the mappings f, g ∈ ΩΩ such that the semigroup generated by G ∪ {f, g} equals ΩΩ.
2015-03-01T00:00:00ZEast, J.Mitchell, James DavidPéresse, Y.In this paper we classify the maximal subsemigroups of the full transformation semigroup ΩΩ, which consists of all mappings on the infinite set Ω, containing certain subgroups of the symmetric group Sym (Ω) on Ω. In 1965 Gavrilov showed that there are five maximal subsemigroups of ΩΩ containing Sym (Ω) when Ω is countable, and in 2005 Pinsker extended Gavrilov's result to sets of arbitrary cardinality. We classify the maximal subsemigroups of ΩΩ on a set Ω of arbitrary infinite cardinality containing one of the following subgroups of Sym (Ω): the pointwise stabiliser of a non-empty finite subset of Ω, the stabiliser of an ultrafilter on Ω, or the stabiliser of a partition of Ω into finitely many subsets of equal cardinality. If G is any of these subgroups, then we deduce a characterisation of the mappings f, g ∈ ΩΩ such that the semigroup generated by G ∪ {f, g} equals ΩΩ.The effect of slip length on vortex rebound from a rigid boundarySutherland, D.Macaskill, C.Dritschel, D.G.http://hdl.handle.net/10023/52322021-01-12T10:49:57Z2013-09-23T00:00:00ZThe problem of a dipole incident normally on a rigid boundary, for moderate to large Reynolds numbers, has recently been treated numerically using a volume penalisation method by Nguyen van yen, Farge, and Schneider [Phys. Rev. Lett.106, 184502 (2011)]. Their results indicate that energy dissipating structures persist in the inviscid limit. They found that the use of penalisation methods intrinsically introduces some slip at the boundary wall, where the slip approaches zero as the Reynolds number goes to infinity, so reducing to the no-slip case in this limit. We study the same problem, for both no-slip and partial slip cases, using compact differences on a Chebyshev grid in the direction normal to the wall and Fourier methods in the direction along the wall. We find that for the no-slip case there is no indication of the persistence of energy dissipating structures in the limit as viscosity approaches zero and that this also holds for any fixed slip length. However, when the slip length is taken to vary inversely with Reynolds number then the results of Nguyen van yen et al. are regained. It therefore appears that the prediction that energy dissipating structures persist in the inviscid limit follows from the two limits of wall slip length going to zero, and viscosity going to zero, not being treated independently in their use of the volume penalisation method.
2013-09-23T00:00:00ZSutherland, D.Macaskill, C.Dritschel, D.G.The problem of a dipole incident normally on a rigid boundary, for moderate to large Reynolds numbers, has recently been treated numerically using a volume penalisation method by Nguyen van yen, Farge, and Schneider [Phys. Rev. Lett.106, 184502 (2011)]. Their results indicate that energy dissipating structures persist in the inviscid limit. They found that the use of penalisation methods intrinsically introduces some slip at the boundary wall, where the slip approaches zero as the Reynolds number goes to infinity, so reducing to the no-slip case in this limit. We study the same problem, for both no-slip and partial slip cases, using compact differences on a Chebyshev grid in the direction normal to the wall and Fourier methods in the direction along the wall. We find that for the no-slip case there is no indication of the persistence of energy dissipating structures in the limit as viscosity approaches zero and that this also holds for any fixed slip length. However, when the slip length is taken to vary inversely with Reynolds number then the results of Nguyen van yen et al. are regained. It therefore appears that the prediction that energy dissipating structures persist in the inviscid limit follows from the two limits of wall slip length going to zero, and viscosity going to zero, not being treated independently in their use of the volume penalisation method.On disjoint unions of finitely many copies of the free monogenic semigroupAbughazalah, NabilahRuskuc, Nikhttp://hdl.handle.net/10023/33412021-09-26T04:30:45Z2013-08-01T00:00:00ZEvery semigroup which is a finite disjoint union of copies of the free monogenic semigroup (natural numbers under addition) is finitely presented and residually finite.
2013-08-01T00:00:00ZAbughazalah, NabilahRuskuc, NikEvery semigroup which is a finite disjoint union of copies of the free monogenic semigroup (natural numbers under addition) is finitely presented and residually finite.Green index in semigroups : generators, presentations and automatic structuresCain, A.J.Gray, RRuskuc, Nikhttp://hdl.handle.net/10023/27602021-01-12T10:34:58Z2012-01-01T00:00:00ZThe Green index of a subsemigroup T of a semigroup S is given by counting strong orbits in the complement S n T under the natural actions of T on S via right and left multiplication. This partitions the complement S nT into T-relative H -classes, in the sense of Wallace, and with each such class there is a naturally associated group called the relative Schützenberger group. If the Rees index ΙS n TΙ is finite, T also has finite Green index in S. If S is a group and T a subgroup then T has finite Green index in S if and only if it has finite group index in S. Thus Green index provides a common generalisation of Rees index and group index. We prove a rewriting theorem which shows how generating sets for S may be used to obtain generating sets for T and the Schützenberger groups, and vice versa. We also give a method for constructing a presentation for S from given presentations of T and the Schützenberger groups. These results are then used to show that several important properties are preserved when passing to finite Green index subsemigroups or extensions, including: finite generation, solubility of the word problem, growth type, automaticity (for subsemigroups), finite presentability (for extensions) and finite Malcev presentability (in the case of group-embeddable semigroups).
2012-01-01T00:00:00ZCain, A.J.Gray, RRuskuc, NikThe Green index of a subsemigroup T of a semigroup S is given by counting strong orbits in the complement S n T under the natural actions of T on S via right and left multiplication. This partitions the complement S nT into T-relative H -classes, in the sense of Wallace, and with each such class there is a naturally associated group called the relative Schützenberger group. If the Rees index ΙS n TΙ is finite, T also has finite Green index in S. If S is a group and T a subgroup then T has finite Green index in S if and only if it has finite group index in S. Thus Green index provides a common generalisation of Rees index and group index. We prove a rewriting theorem which shows how generating sets for S may be used to obtain generating sets for T and the Schützenberger groups, and vice versa. We also give a method for constructing a presentation for S from given presentations of T and the Schützenberger groups. These results are then used to show that several important properties are preserved when passing to finite Green index subsemigroups or extensions, including: finite generation, solubility of the word problem, growth type, automaticity (for subsemigroups), finite presentability (for extensions) and finite Malcev presentability (in the case of group-embeddable semigroups).Growth rates for subclasses of Av(321)Albert, M.H.Atkinson, M.D.Brignall, RRuskuc, NikSmith, RWest, Jhttp://hdl.handle.net/10023/21372021-04-18T02:30:11Z2010-10-22T00:00:00ZPattern classes which avoid 321 and other patterns are shown to have the same growth rates as similar (but strictly larger) classes obtained by adding articulation points to any or all of the other patterns. The method of proof is to show that the elements of the latter classes can be represented as bounded merges of elements of the original class, and that the bounded merge construction does not change growth rates.
2010-10-22T00:00:00ZAlbert, M.H.Atkinson, M.D.Brignall, RRuskuc, NikSmith, RWest, JPattern classes which avoid 321 and other patterns are shown to have the same growth rates as similar (but strictly larger) classes obtained by adding articulation points to any or all of the other patterns. The method of proof is to show that the elements of the latter classes can be represented as bounded merges of elements of the original class, and that the bounded merge construction does not change growth rates.Generators and relations for subsemigroups via boundaries in Cayley graphsGray, RRuskuc, Nikhttp://hdl.handle.net/10023/21312021-01-12T10:34:59Z2011-11-01T00:00:00ZGiven a finitely generated semigroup S and subsemigroup T of S we define the notion of the boundary of T in S which, intuitively, describes the position of T inside the left and right Cayley graphs of S. We prove that if S is finitely generated and T has a finite boundary in S then T is finitely generated. We also prove that if S is finitely presented and T has a finite boundary in S then T is finitely presented. Several corollaries and examples are given.
2011-11-01T00:00:00ZGray, RRuskuc, NikGiven a finitely generated semigroup S and subsemigroup T of S we define the notion of the boundary of T in S which, intuitively, describes the position of T inside the left and right Cayley graphs of S. We prove that if S is finitely generated and T has a finite boundary in S then T is finitely generated. We also prove that if S is finitely presented and T has a finite boundary in S then T is finitely presented. Several corollaries and examples are given.Presentations of inverse semigroups, their kernels and extensionsCarvalho, C.A.Gray, RRuskuc, Nikhttp://hdl.handle.net/10023/19982021-01-12T10:35:00Z2011-06-01T00:00:00ZLet S be an inverse semigroup and let π:S→T be a surjective homomorphism with kernel K. We show how to obtain a presentation for K from a presentation for S, and vice versa. We then investigate the relationship between the properties of S, K and T, focusing mainly on finiteness conditions. In particular we consider finite presentability, solubility of the word problem, residual finiteness, and the homological finiteness property FPn. Our results extend several classical results from combinatorial group theory concerning group extensions to inverse semigroups. Examples are also provided that highlight the differences with the special case of groups.
"Part of this work was done while Gray was an EPSRC Postdoctoral Research Fellow at the University of St Andrews, Scotland"
2011-06-01T00:00:00ZCarvalho, C.A.Gray, RRuskuc, NikLet S be an inverse semigroup and let π:S→T be a surjective homomorphism with kernel K. We show how to obtain a presentation for K from a presentation for S, and vice versa. We then investigate the relationship between the properties of S, K and T, focusing mainly on finiteness conditions. In particular we consider finite presentability, solubility of the word problem, residual finiteness, and the homological finiteness property FPn. Our results extend several classical results from combinatorial group theory concerning group extensions to inverse semigroups. Examples are also provided that highlight the differences with the special case of groups.Simple extensions of combinatorial structuresBrignall, RRuskuc, NikVatter, Vhttp://hdl.handle.net/10023/19972021-08-15T04:30:52Z2011-07-01T00:00:00ZAn 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 the best possible.
2011-07-01T00:00:00ZBrignall, RRuskuc, NikVatter, VAn 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 the best possible.