Semigroups of matrices of intermediate growth

Finitely generated linear semigroups over a field K that have intermediate growth are considered. New classes of such semigroups are found and a conjecture on the equivalence of the subexponential growth of a finitely generated linear semigroup S and the nonexistence of free noncommutative subsemigroups in S, or equivalently the existence of a nontrivial identity satisfied in S, is stated. This ‘growth alternative’ conjecture is proved for linear semigroups of degree 2, 3 or 4. Certain results supporting the general conjecture are obtained. As the main tool, a new combinatorial property of groups is introduced and studied.

Biased Random-key Genetic Algorithms For The Winner Determination Problem In Combinatorial Auctions.

Abstract In this paper, we address the problem of picking a subset of bids in a general combinatorial auction so as to maximize the overall profit using the first-price model. This winner determination problem assumes that a single bidding round is held to determine both the winners and prices to be paid. We introduce six variants of biased random-key genetic algorithms for this problem. Three of them use a novel initialization technique that makes use of solutions of intermediate linear programming relaxations of an exact mixed integer-linear programming model as initial chromosomes of the population. An experimental evaluation compares the effectiveness of the proposed algorithms with the standard mixed linear integer programming formulation, a specialized exact algorithm, and the best-performing heuristics proposed for this problem. The proposed algorithms are competitive and offer strong results, mainly for large-scale auctions.

Social interaction as a heuristic for combinatorial optimization problems

We investigate the performance of a variant of Axelrod's model for dissemination of culture-the Adaptive Culture Heuristic (ACH)-on solving an NP-Complete optimization problem, namely, the classification of binary input patterns of size F by a Boolean Binary Perceptron. In this heuristic, N agents, characterized by binary strings of length F which represent possible solutions to the optimization problem, are fixed at the sites of a square lattice and interact with their nearest neighbors only. The interactions are such that the agents' strings (or cultures) become more similar to the low-cost strings of their neighbors resulting in the dissemination of these strings across the lattice. Eventually the dynamics freezes into a homogeneous absorbing configuration in which all agents exhibit identical solutions to the optimization problem. We find through extensive simulations that the probability of finding the optimal solution is a function of the reduced variable F/N(1/4) so that the number of agents must increase with the fourth power of the problem size, N proportional to F(4), to guarantee a fixed probability of success. In this case, we find that the relaxation time to reach an absorbing configuration scales with F(6) which can be interpreted as the overall computational cost of the ACH to find an optimal set of weights for a Boolean binary perceptron, given a fixed probability of success.

Encoding combinatorial libraries: A novel application of fluorescent silica colloids

A major challenge associated with using large chemical libraries synthesized on microscopic solid support beads is the rapid discrimination of individual compounds in these libraries. This challenge can be overcome by encoding the beads with 1 mum silica colloidal particles (reporters) that contain specific and identifiable combinations of fluorescent byes. The colored bar code generated on support beads during combinatorial library synthesis can be easily, rapidly, and inexpensively decoded through the use of fluorescence microscopy. All reporters are precoated with polyelectrolytes [poly(acrylic acid), PAA, poly(sodium 4-styrenesulfonate PSSS, polyethylenimine, PEI, and/or poly(diallyldimethylammonium chloride), PDADMAC] with the aim of enhancing surface charge, promoting electrostatic attraction to the bead, and facilitating polymer bridging between the bead and reporter for permanent adhesion. As shown in this article, reporters coated with polyelectrolytes clearly outperform uncoated reporters with regard to quantity of attached reporters per bead (54 +/- 23 in 2500 mum(2) area for PEI/PAA coated and 11 +/- 6 for uncoated reporters) and minimization of cross-contamination (1 red reporter in 2500 mum(2) area of green-labeled bead for PEI/PAA coated and 26 +/- 15 red reporters on green-labeled beads for uncoated reporters after 10 days). Examination of various polyelectrolyte systems shows that the magnitude of the xi -potential of polyelectrolyte-coated reporters (-64 mV for PDADMAC/PSSS and -42 mV for PEI/PAA-coated reporters) has no correlation with the number of reporters that adhere to the solid support beads (21 +/- 16 in 2500 mum(2) area for PDADMAC/PSSS and 54 +/- 23 for PEI/PAA-coated reporters). The contribution of polymer bridging to the adhesion has a far greater influence than electrostatic attraction and is demonstrated by modification of the polyelectrolyte multilayers using gamma irradiation of precoated reporters either in aqueous solution or in polyelectrolyte solution.

Multi-fluorescent silica colloids for encoding large combinatorial libraries

Large chemical libraries can be synthesized on solid-support beads by the combinatorial split-and-mix method. A major challenge associated with this type of library synthesis is distinguishing between the beads and their attached compounds. A new method of encoding these solid-support beads, 'colloidal bar-coding', involves attaching fluorescent silica colloids ('reporters') to the beads as they pass through the compound synthesis, thereby creating a fluorescent bar code on each bead. In order to obtain sufficient reporter varieties to bar code extremely large libraries, many of the reporters must contain multiple fluorescent dyes. We describe here the synthesis and spectroscopic analysis of various mono- and multi-fluorescent silica particles for this purpose. It was found that by increasing the amount of a single dye introduced into the particle reaction mixture, mono- fluorescent silica particles of increasing intensities could be prepared. This increase was highly reproducible and was observed for six different fluorescent dyes. Multi-fluorescent silica particles containing up to six fluorescent dyes were also prepared. The resultant emission intensity of each dye in the multi-fluorescent particles was found to be dependent upon a number of factors; the hydrolysis rate of each silane-dye conjugate, the magnitude of the inherent emission intensity of each dye within the silica matrix, and energy transfer effects between dyes. We show that by varying the relative concentration of each silane-dye conjugate in the synthesis of multi-fluorescent particles, it is possible to change and optimize the resultant emission intensity of each dye to enable viewing in a fluorescence detection instrument.

Rational combinatorial chemistry-based selection, synthesis and evaluation of an affinity adsorbent for recombinant human clotting factor VII

The selection, synthesis and chromatographic evaluation of a synthetic affinity adsorbent for human recombinant factor VIIa is described. The requirement for a metal ion-dependent immunoadsorbent step in the purification of the recombinant human clotting factor, FVIIa, has been obviated by using the X-ray crystallographic structure of the complex of tissue factor (TF) and Factor VIIa and has directed our combinatorial approach to select, synthesise and evaluate a rationally-selected affinity adsorbent from a limited library of putative ligands. The selected and optimised ligand comprises a triazine scaffold bis-substituted with 3-aminobenzoic acid and has been shown to bind selectively to FVIIa in a Ca2+-dependent manner. The adsorbent purifies FVIIa to almost identical purity (>99%), yield (99%), activation/degradation profile and impurity content (∼1000 ppm) as the current immunoadsorption process, while displaying a 10-fold higher static capacity and substantially higher reusability and durability. © 2002 Elsevier Science B.V. All rights reserved.

Exploring privileged structures: the combinatorial synthesis of cyclic peptides

Head-to-tail cyclic peptides have been reported to bind to multiple, unrelated classes of receptor with high affinity. They may therefore be considered to be privileged structures. This review outlines the strategies by which both macrocyclic cyclic peptides and cyclic dipeptides or diketopiperazines have been synthesised in combinatorial libraries. It also briefly outlines some of the biological applications of these molecules, thereby justifying their inclusion as privileged structures.

On semigroups of endomorphisms of a chain with restricted range

Let X be a finite or infinite chain and let be the monoid of all endomorphisms of X. In this paper, we describe the largest regular subsemigroup of and Green's relations on. In fact, more generally, if Y is a nonempty subset of X and is the subsemigroup of of all elements with range contained in Y, we characterize the largest regular subsemigroup of and Green's relations on. Moreover for finite chains, we determine when two semigroups of the type are isomorphic and calculate their ranks.

On lattices from combinatorial game theory modularity and a representation theorem: finite case

We show that a self-generated set of combinatorial games, S. may not be hereditarily closed but, strong self-generation and hereditary closure are equivalent in the universe of short games. In [13], the question "Is there a set which will give a non-distributive but modular lattice?" appears. A useful necessary condition for the existence of a finite non-distributive modular L(S) is proved. We show the existence of S such that L(S) is modular and not distributive, exhibiting the first known example. More, we prove a Representation Theorem with Games that allows the generation of all finite lattices in game context. Finally, a computational tool for drawing lattices of games is presented. (C) 2014 Elsevier B.V. All rights reserved.

On divisors of pseudovarieties generated by some classes of full transformation semigroups

Algebra Colloquium, 15 (2008), p. 581–588

Automorphisms of partial endomorphism semigroups

Publicationes Mathematicae Debrecen

Normally ordered semigroups

Glasgow Mathematical Journal, nº 50 (2008), p. 325-333