Search

New invariants for two-dimensional cell complexes are defined, which can be interpreted as curvature bounds. These invariants are proved to be rational and computable in a companion article. This document is a survey that collects theorems about these invariants, computes examples and lays out a programme of conjectures. [ABSTRACT FROM AUTHOR]

In this paper, we construct signal constellations from lattices in complex hyperbolic spaces. To construct a hyperbolic lattice, we identify an arithmetic Fuchsian group with the group of units O1 of a natural quaternion order O ⊂ V, in which V is some quaternion algebra over an algebraic number field. The arithmetic Fuchsian group, G, is isomorphic to the fundamental group of a regular hyperbolic polygon P, and an oriented compact surface arises from the pairwise identification of its opposite edges. The polygon P is the fundamental region associated with a regular tessellation {p, q}. The main contribution of this paper is to employ the Reidemeister-Schreier rewriting process to use proper decompositions of the full symmetry group of a tessellation {p, q}, which allows the matching of uniform signal constellations to quotient groups of G. In this direction, we consider the labelling of phaseshift keying (PSK) and amplitude-phase keying (APK) signal constellations diagrams via three approaches: cyclic quotient groups, a direct product of cyclic quotient groups and semi-direct product of cyclic groups (the dihedral group case). [ABSTRACT FROM AUTHOR]

We study the language-theoretic aspects of the word problem, in the sense of Duncan & Gilman, of free products of semigroups and monoids. First, we provide algebraic tools for studying classes of languages known as super-AFLs, which generalise e.g. the context-free or the indexed languages. When C is a super-AFL closed under reversal, we prove that the semigroup (monoid) free product of two semigroups (resp. monoids) with word problem in C also has word problem in C. This recovers and generalises a recent result by Brough, Cain & Pfeiffer that the class of context-free semigroups (monoids) is closed under taking free products. As a group-theoretic corollary, we deduce that the word problem of the (group) free product of two groups with word problem in C is also in C. As a particular case, we find that the free product of two groups with indexed word problem has indexed word problem. [ABSTRACT FROM AUTHOR]

We show that picture groups are directly related to maximal green sequences for valued Dynkin quivers of finite type. Namely, there is a bijection between maximal green sequences and positive expressions (words in the generators without inverses) for the Coxeter element of the picture group. We actually prove the theorem for the more general set up of finite "vertically and laterally ordered" sets of positive real Schur roots for any hereditary algebra (not necessarily of finite type). Furthermore, we show that every picture for such a set of positive roots is a linear combination of "atoms" and we give a precise description of atoms as special semi-invariant pictures. [ABSTRACT FROM AUTHOR]

This article aims to be a self-contained account of the history of the B B Newman Spelling Theorem, including the historical context in which it arose. First, an account of B B Newman and how he came to prove his Spelling Theorem is given, together with a description of the author's efforts to track this information down. Following this, a high-level description of combinatorial group theory is given. This is then tied in with a description of the history of the word problem, a fundamental problem in the area. After a description of some of the theory of one-relator groups, an important part of combinatorial group theory, the natural division line into the torsion and torsion-free case for such groups is described. This culminates in a statement of and general discussion about the B B Newman Spelling Theorem and its importance. [ABSTRACT FROM AUTHOR]

In this paper, we use the notion of twisted subgroups (i.e. subsets of group elements closed under the binary operation (a , b) ↦ a b a) to provide the first structural characterization of optimal play in the Explorer-Director game, introduced as the Magnus–Derek game by Nedev and Muthukrishnan and generalized to finite groups by Gerbner. In particular, we reduce the game to the problem of finding the largest proper twisted subgroup, and as a corollary we resolve the Explorer-Director game completely for all nilpotent groups. [ABSTRACT FROM AUTHOR]

In this paper, an explicit construction of a countable parafree Lie algebra with nonzero second homology is given. It is also shown that the cohomological dimension of the pronilpotent completion of a free noncyclic finitely generated Lie algebra over Z is greater than two. Moreover, it is proven that there exists a countable parafree group with nontrivial H 2. [ABSTRACT FROM AUTHOR]

We use tools from combinatorial group theory in order to study actions of three types on groups acting on a curve, namely the automorphism group of a compact Riemann surface, the mapping class group acting on a surface (which now is allowed to have some points removed) and the absolute Galois group Gal (Q ¯ / Q) in the case of cyclic covers of the projective line. [ABSTRACT FROM AUTHOR]

We give a direct proof that all Higman-Thompson groups of the form Gk,1 (for k ≥ 2 ) are embedded in one another, which is a recent result of N. Matte Bon. This extends the embeddings given by Higman in 1974. Communicated by Karl Auinger [ABSTRACT FROM AUTHOR]

We consider whether given a simple, finite description of a group in the form of an algorithm, it is possible to algorithmically determine if the corresponding group has some specified property or not. When there is such an algorithm, we say the property is recursively recognizable within some class of descriptions. When there is not, we ask how difficult it is to detect the property in an algorithmic sense. We consider descriptions of two sorts: first, recursive presentations in terms of generators and relators, and second, algorithms for computing the group operation. For both classes of descriptions, we show that a large class of natural algebraic properties, Markov properties, are not recursively recognizable, indeed they are Π 2 0 -hard to detect in recursively presented groups and Π 1 0 -hard to detect in computable groups. These theorems suffice to give a sharp complexity measure for the detection problem of a number of typical group properties, for example, being abelian, torsion-free, orderable. Some properties, like being cyclic, nilpotent, or solvable, are much harder to detect, and we give sharp characterizations of the corresponding detection problems from a number of them. We give special attention to orderability properties, as this was a main motivation at the beginning of this project. [ABSTRACT FROM AUTHOR]

We prove that the property of being cyclic subgroup separable, that is having all cyclic subgroups closed in the profinite topology, is preserved under forming graph products. Furthermore, we develop the tools to study the analogous question in the pro- p case. For a wide class of groups we show that the relevant cyclic subgroups – which are called p -isolated – are closed in the pro- p topology of the graph product. In particular, we show that every p -isolated cyclic subgroup of a right-angled Artin group is closed in the pro- p topology, and we fully characterise such subgroups. [ABSTRACT FROM AUTHOR]

Abstract This paper is about application of various homological methods to classical problems in the theory of group rings. It is shown that the third homology of groups plays a key role in Narain Gupta's three normal subgroup problem. For a free group F and its normal subgroups R , S , T , and the corresponding ideals in the integral group ring Z [ F ] , r = (R − 1) Z [ F ] , s = (S − 1) Z [ F ] , t = (T − 1) Z [ F ] , a complete description of the normal subgroup F ∩ (1 + rst) is given, provided R ⊆ T and the third, fourth and fifth homology groups of R / R ∩ S are torsion groups. [ABSTRACT FROM AUTHOR]

We show how to modify the tree-based methodology to construct a combinatorial interpretation for certain non-monotonic solutions to recursions in the generalized Golomb family. Using this combinatorial interpretation we derive the asymptotic properties of these solutions. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we provide a mathematical framework for characterizing AMD codes that are R-optimal. We introduce a new combinatorial object, the reciprocally-weighted external difference family (RWEDF) , which corresponds precisely to an R-optimal weak AMD code. This definition subsumes known examples of existing optimal codes, and also encompasses combinatorial objects not covered by previous definitions in the literature. By developing structural group-theoretic characterizations, we exhibit infinite families of new RWEDFs, and new construction methods for known objects such as near-complete EDFs. Examples of RWEDFs in non-abelian groups are also discussed. [ABSTRACT FROM AUTHOR]

Abstract There are extensive results known for the existence of generalized Bhaskar Rao designs signed over solvable groups, and particularly for designs with block size 3. There have so far been no comparable results for any non-solvable groups and in particular none for the non-solvable group of smallest order, the simple group A 5. In this paper we define the new notion of pairwise balanced signed block designs, signed over a group. Our central new result is then a composition theorem for these pairwise balanced signed block designs. From this we derive a pair of induction theorems specifically for constructing generalized Bhaskar Rao design pieces. These induction theorems give conditions under which generalized Bhaskar Rao designs pieces signed over a group can be induced from such designs signed over a subgroup. This is in contrast to long established results which give conditions under which generalized Bhaskar Rao design pieces signed over a quotient group can be inflated to give such designs signed over the whole group. By making systematic use of our new induction theorems and various piecewise constructions we are able to elegantly establish that the well known necessary condition for the existence of generalized Bhaskar Rao designs of block size 3 are also sufficient for designs signed over the non-solvable groups A 5 , Z 2 × A 5 and S 5. In the course of these applications we identify a number of new generic generalized Bhaskar Rao design pieces. Finally, and independently of the new induction theorems, we identify a new infinite family of solvable groups for which the known necessary conditions for the existence of generalized Bhaskar Rao designs of block size 3 are also sufficient. [ABSTRACT FROM AUTHOR]

Abstract T. A. Dowling introduced Whitney numbers of the first and second kinds concerning the so-called Dowling lattices of finite groups. It turned out that they are generalizations of Stirling numbers. Later, I. Mező defined r -Whitney numbers as common generalizations of Whitney numbers and r -Stirling numbers. Additionally, G.-S. Cheon and J.-H. Jung defined r -Whitney–Lah numbers. In our paper, we give new combinatorial interpretations of r -Whitney and r -Whitney–Lah numbers, which correspond better with the combinatorial definitions of Stirling, r -Stirling, Lah and r -Lah numbers. These allow us to explain their properties in a purely combinatorial manner, as well as derive several new identities. [ABSTRACT FROM AUTHOR]

A combinatorial expression for the coefficient of the Schur function sλ in the expansion of the plethysm pn/dd ... sμ is given for all d dividing n for the cases in which n = 2 or λ is rectangular. In these cases, the coefficient is shown to count, up to sign, the number of fixed points of an -element set under the dth power of an order-n cyclic action. If n = 2, the action is the Schützenberger involution on semistandard Young tableaux (also known as evacuation), and, if λ is rectangular, the action is a certain power of Schützenberger and Shimozono's jeu-de-taquin promotion. This work extends results of Stembridge and Rhoades linking fixed points of the Schützenberger actions to ribbon tableaux enumeration. The conclusion for the case n = 2 is equivalent to the domino tableaux rule of Carré and Leclerc for discriminating between the symmetric and antisymmetric parts of the square of a Schur function. [ABSTRACT FROM AUTHOR]

In Panaite [Iterated crossed products, J. Algebra Appl. 13(7), 14580036 (2014)], Panaite studied iterated crossed product construction from the point of algebraic structures. In this paper, we study iterated crossed product from the point of Combinatorial Group Theory and define a new version of the crossed product of groups. First, we give some conditions for this new product to be a group, then we obtain a presentation for iterated crossed product of cyclic groups. Additionally, using this presentation, we find a complete rewriting system and thus we obtain normal form structure of elements of this new group construction. This gives us the solvability of the word problem for this product. [ABSTRACT FROM AUTHOR]

We present a new recursive generation algorithm for prefix normal words. These are binary words with the property that no factor has more 1s than the prefix of the same length. The new algorithm uses two operations on binary words, which exploit certain properties of prefix normal words in a smart way. We introduce infinite prefix normal words and show that one of the operations used by the algorithm, if applied repeatedly to extend the word, produces an ultimately periodic infinite word, which is prefix normal. Moreover, based on the original finite word, we can predict both the length and the density of an ultimate period of this infinite word. 1 [ABSTRACT FROM AUTHOR]

A permutation group is said to be quasiregular if each of its transitive constituents is regular, and a quasiregular coherent configuration can be thought as a combinatorial analog of such a group: the transitive constituents are replaced by the homogeneous components. In this paper, we are interested in the question when the configuration is schurian, i.e., formed by the orbitals of a permutation group, or/and separable, i.e., uniquely determined by the intersection numbers. In these terms, an old result of Hanna Neumann is, in a sense, dual to the statement that the quasiregular coherent configurations with cyclic homogeneous components are schurian. In the present paper, we (a) establish the duality in a precise form and (b) generalize the latter result by proving that a quasiregular coherent configuration is schurian and separable if the groups associated with the homogeneous components have distributive lattices of normal subgroups. [ABSTRACT FROM AUTHOR]

The automorphism group of a partially commutative group 𝔾 Γ is generated by four types of automorphism: graph automorphisms, inversions, transvections and vertex conjugating automorphisms. We find a characterisation of the subgroup S t (𝒦) generated by inversions and transvections, in terms of stabilisers of subgroups of 𝔾 Γ generated by the so-called “admissible” subsets of V (Γ). This is used to give a decomposition of S t (𝒦) as a chain of semi-direct products of (mostly) tractable and recognisable subgroups; which in turn gives rise to a presentation of S t (𝒦). [ABSTRACT FROM AUTHOR]

We provide a combinatorial algorithm for constructing the stable Auslander–Reiten component containing a given indecomposable module of a symmetric special biserial algebra using only information from its underlying Brauer graph. We also show that the structure of the Auslander–Reiten quiver is closely related to the distinct Green walks of the Brauer graph and detail the relationship between the precise shape of the stable Auslander–Reiten components for domestic Brauer graph algebras and their underlying graph. Furthermore, we show that the specific component containing a given simple or indecomposable projective module for any Brauer graph algebra is determined by the edge in the Brauer graph associated to the module. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a simple graph and w∈ℤ>0E assign each edge e ∈ E a positive integer weight w(e). A subset of E that intersects every triangle of G is called a triangle cover of (G, w), and its weight is the total weight of its edges. A collection of triangles in G (repetition allowed) is called a triangle packing of (G, w) if each edge e ∈ E appears in at most w(e) members of the collection. Let τt(G, w) and νt(G, w) denote the minimum weight of a triangle cover and the maximum cardinality of a triangle packing of (G, w), respectively. Generalizing Tuza’s conjecture for unit weight, Chapuy et al. conjectured that τt(G, w)/νt(G, w) ≤ 2 holds for every simple graph G and every w∈ℤ>0E. In this paper, using a hypergraph approach, we design polynomial-time combinatorial algorithms for finding triangle covers of small weights. These algorithms imply new sufficient conditions for the conjecture of Chapuy et al. More precisely, given (G, w), suppose that all edges of G are covered by the set TG consisting of edge sets of triangles in G. Let |E|w=∑e∈Ew(e) and |TG|w=∑{e,f,g}∈TGw(e)w(f)w(g) denote the weighted numbers of edges and triangles in (G, w), respectively. We show that a triangle cover of (G, w) of weight at most 2νt(G, w) can be found in strongly polynomial time if one of the following conditions is satisfied: (i) νt(G,w)/|TG|w≥13, (ii) νt(G,w)/|E|w≥14, (iii) |E|w/|TG|w≥2. [ABSTRACT FROM AUTHOR]

The Tarski number of a group G is the minimal number of the pieces of paradoxical decompositions of that group. Using configurations along with a matrix combinatorial property, we construct paradoxical decompositions. We also compute an upper bound for the Tarski number of a given non-amenable group by counting the number of paths in a diagram associated to the group. [ABSTRACT FROM AUTHOR]

Two isometry groups of combinatorial codes are described: the group of isometries, that is, the group of Hamming isometries from a code to itself and the group of monomial isometries, which is the group of those isometries of a code to itself that extend to monomial maps. Unlike the case of classical linear codes, where these groups are the same, it is shown that for combinatorial codes the groups can be arbitrarily different. In particular, there exist codes with the richest possible group of isometries and the trivial group of monomial isometries. In the paper, the two groups are characterized and codes with predefined isometry groups are constructed. [ABSTRACT FROM AUTHOR]

We study a new model of combinatorial group testing: the item to be found (a.k.a. the target) occupies an unknown node in a graph. At each time instant, we can test (or query) a subset of the nodes and learn whether the target occupies any of such nodes. Immediately after the result of the test is available, the target can move to any node adjacent to its present location. The search finishes when we are able to locate the object with some predefined accuracy s (a parameter fixed beforehand), i.e., to indicate a set of s nodes that includes the location of the object. In this paper we study two types of problems related to the above model: (i) what is the minimum value of the accuracy parameter for which a search strategy in the above sense exists; (ii) given the accuracy, what is the minimum number of tests that allow to locate the target. We study these questions on paths, cycles, and trees as underlying graphs and provide tight answers for the above questions. We also consider a restricted variant of the problem, where the number of moves of the target is bounded. [ABSTRACT FROM AUTHOR]

We consider the quantitative group testing problem where the objective is to identify defective items in a given population based on results of tests performed on subsets of the population. Under the quantitative group testing model, the result of each test reveals the number of defective items in the tested group. The minimum number of tests achievable by nested test plans was established by Aigner and Schughart in 1985 within a minimax framework. The optimal nested test plan offering this performance, however, was not obtained. In this paper, we establish the optimal nested test plan in a closed form. This optimal nested test plan is also order optimal among all test plans as the population size approaches infinity. Using heavy-hitter detection as a case study, we show via simulation examples orders of magnitude improvement of the group testing approach over two prevailing sampling-based approaches in detection accuracy and counter consumption. Other applications include anomaly detection and wideband spectrum sensing in cognitive radio systems. [ABSTRACT FROM AUTHOR]

Recently, Freiman et al. [‘Small doubling in ordered groups’, J. Aust. Math. Soc. 96(3) (2014), 316–325] proved two ‘structure theorems’ for ordered groups. We give elementary proofs of these two theorems. [ABSTRACT FROM AUTHOR]

Our basic objects are partitions of finite sets of points into disjoint subsets. We investigate sets of partitions which are closed under taking tensor products, composition and involution, and which contain certain base partitions. These so called categories of partitions are exactly the tensor categories being used in the theory of Banica–Speicher quantum groups (also called easy quantum groups). In our approach, we additionally allow a coloring of the points. This serves as the basis for the introduction of unitary Banica–Speicher quantum groups, which is done in a separate article. The present article however is purely combinatorial. We find all categories of two-colored noncrossing partitions. For doing so, we extract certain parameters with values in the natural numbers specifying the colorization of the categories on a global as well as on a local level. It turns out that there are ten series of categories, each indexed by one or two parameters from the natural numbers, plus two additional categories. This is just the beginning of the classification of categories of two-colored partitions and we point out open problems at the end of the article. [ABSTRACT FROM AUTHOR]

It is shown that the knapsack problem, which was introduced by Myasnikov et al. for arbitrary finitely generated groups, can be solved in NP for every graph group. This result even holds if the group elements are represented in a compressed form by so called straight-line programs, which generalizes the classical NP-completeness result of the integer knapsack problem. If group elements are represented explicitly by words over the generators, then knapsack for a graph group belongs to the class LogCFL (a subclass of P) if the graph group can be built up from the trivial group using the operations of free product and direct product with $\mathbb {Z}$ . In all other cases, the knapsack problem is NP-complete. [ABSTRACT FROM AUTHOR]

We complement the characterization of the graph products of cyclic groups G ( Γ , p ) admitting a Polish group topology of [9] with the following result. Let G = G ( Γ , p ) , then the following are equivalent: (i) there is a metric on Γ which induces a separable topology in which E Γ is closed; (ii) G ( Γ , p ) is embeddable into a Polish group; (iii) G ( Γ , p ) is embeddable into a non-Archimedean Polish group. We also construct left-invariant separable group ultrametrics for G = G ( Γ , p ) and Γ a closed graph on the Baire space, which is of independent interest. [ABSTRACT FROM AUTHOR]

Finding a maximum weight path in a directed or undirected graph is a basic combinatorial and algorithmic problem. We consider this problem for tournaments in the well-studied random weighted model. Denote by P ( G , D ) the probability space obtained by independently assigning weights to the edges of a tournament G according to a nonnegative probability distribution D . Denote by ℓ ( G , D ) the expected weight of a path with maximum weight. If D has finite mean μ , then ℓ ( G , D ) ≥ μ ( n − 1 ) is a trivial lower bound, with equality if D is constant, as by Redei’s Theorem, every tournament has a Hamilton path. However, already for very simple nontrivial distributions, it is challenging to determine ℓ ( G , D ) even asymptotically, and even if the tournament is small and fixed. We consider the two natural distributions of the random weighted model, the continuous uniform distribution U [ 0 , 1 ] and the symmetric Bernoulli distribution U { 0 , 1 } . Our first result is that for any tournament, both ℓ ( G , U { 0 , 1 } ) and ℓ ( G , U [ 0 , 1 ] ) are larger than the above trivial 0 . 5 ( n − 1 ) lower bound in the sense that 0.5 can be replaced by a larger constant . To this end we prove the existence of dense partial squares of Hamilton paths in any tournament, a combinatorial result which seems of independent interest. Regarding upper bounds, while for some tournaments one can prove that both ℓ ( G , U { 0 , 1 } ) and ℓ ( G , U [ 0 , 1 ] ) are n − o ( n ) , we prove that there are other tournaments for which both ℓ ( G , U { 0 , 1 } ) and ℓ ( G , U [ 0 , 1 ] ) are significantly smaller. In particular, for every n , there are n -vertex tournaments for which ℓ ( G , U { 0 , 1 } ) ≤ 0 . 614 ( n − 1 ) . Finally, we state several natural open problems arising in this setting. [ABSTRACT FROM AUTHOR]

Combinatorial mixed valuations associated to translation-invariant valuations on polytopes are introduced. In contrast to the construction of mixed valuations via polarization, combinatorial mixed valuations reflect and often inherit properties of inhomogeneous valuations. In particular, it is shown that under mild assumptions combinatorial mixed valuations are monotone and hence nonnegative. For combinatorially positive valuations, this has strong computational implications. Applied to the discrete volume, the results generalize and strengthen work of Bihan (2015) on discrete mixed volumes. For rational polytopes, it is proved that combinatorial mixed monotonicity is equivalent to monotonicity. Stronger even, a conjecture is substantiated that combinatorial mixed monotonicity implies the homogeneous monotonicity in the sense of Bernig–Fu (2011). [ABSTRACT FROM AUTHOR]