Combinatorial and metric properties of Thompson's group T

We discuss metric and combinatorial properties of Thompson's group T, such as the normal forms for elements and uniqueness of tree pair diagrams. We relate these properties to those of Thompson's group F when possible, and highlight combinatorial differences between the two groups. We define a set of unique normal forms for elements of T arising from minimal factorizations of elements into convenient pieces. We show that the number of carets in a reduced representative of T estimates the word length, that F is undistorted in T, and that cyclic subgroups of T are undistorted. We show that every element of T has a power which is conjugate to an element of F and describe how to recognize torsion elements in T.

Combinatorial Synthesis and Biological Evaluation of Inhibitors of D-Ala-D-Ala-Ligase

Report for the scientific sojourn carried out at the Max Planck Institut of Molecular Phisiology, Germany, from 2006 to 2008.The work carried out during this postdoctoral stage was focused on two different projects. Firstly, identification of D-Ala D-Ala Inhibitors and the development of new synthethic approaches to obtain lipidated peptides and proteins and the use of these lipidated proteins in biological and biophysical studies. In the first project, new D-Ala D-Ala inhibitors were identified by using structural alignments of the ATP binding sites of the bacterial ligase DDl and protein and lipid kinases in complex with ATP analogs. We tested a series of commercially available kinase inhibitors and found LFM-A13 and Tyrphostine derivatives to inhibit DDl enzyme activity. Based on the initial screening results we synthesized a series of malononitrilamide and salicylamide derivatives and were able to confirm the validity of these scaffolds as inhibitors of DDl. From this investigation we gained a better understanding of the structural requirements and limitations necessary for the preparation of ATP competitive DDl inhibitors. The compounds in this study may serve as starting points for the development of bi-substrate inhibitors that incorporate both, an ATP competitive and a substrate competitive moiety. Bisubstrate inhibitors that block the ATP and D-Ala binding sites should exhibit enhanced selectivity and potency profiles by preferentially inhibiting DDl over kinases. In the second project, an optimized synthesis for tha alkylation of cysteins using the thiol ene reaction was establisehd. This new protocol allowed us to obtain large amounts of hexadecylated cysteine that was required for the synthesis of differently lipidated peptides. Afterwards the synthesis of various N-ras peptides bearing different lipid anchors was performed and the peptides were ligated to a truncated N-ras protein. The influence of this differently lipidated N-ras proteins on the partioning and association of N-Ras in model membrane subdomains was studied using Atomic Force Microscopy.

A parameter-free approach for solving combinatorial optimization problems through biased randomization of efficient heuristics

This paper discusses the use of probabilistic or randomized algorithms for solving combinatorial optimization problems. Our approach employs non-uniform probability distributions to add a biased random behavior to classical heuristics so a large set of alternative good solutions can be quickly obtained in a natural way and without complex conguration processes. This procedure is especially useful in problems where properties such as non-smoothness or non-convexity lead to a highly irregular solution space, for which the traditional optimization methods, both of exact and approximate nature, may fail to reach their full potential. The results obtained are promising enough to suggest that randomizing classical heuristics is a powerful method that can be successfully applied in a variety of cases.

Identification of Ligands for the Tau Exon 10 Splicing Regulatory Element RNA Using Dynamic Combinatorial Chemistry

We describe the use of dynamic combinatorial chemistry (DCC) to identify ligands for the stem-loop structure located at the exon 10-5'-intron junction of Tau pre-mRNA, which is involved in the onset of several tauopathies including frontotemporal dementia with Parkinsonism linked to chromosome 17 (FTDP-17). A series of ligands that combine the small aminoglycoside neamine and heteroaromatic moieties (azaquinolone and two acridines) have been identified by using DCC. These compounds effectively bind the stem-loop RNA target (the concentration required for 50% RNA response (EC(50)): 2-58 μM), as determined by fluorescence titration experiments. Importantly, most of them are able to stabilize both the wild-type and the +3 and +14 mutated sequences associated with the development of FTDP-17 without producing a significant change in the overall structure of the RNA (as analyzed by circular dichroism (CD) spectroscopy), which is a key factor for recognition by the splicing regulatory machinery. A good correlation has been found between the affinity of the ligands for the target and their ability to stabilize the RNA secondary structure.

On the preservation of combinatorial types for maps on trees

We study the preservation of the periodic orbits of an A-monotone tree map f:T→T in the class of all tree maps g:S→S having a cycle with the same pattern as A. We prove that there is a period-preserving injective map from the set of (almost all) periodic orbits of ƒ into the set of periodic orbits of each map in the class. Moreover, the relative positions of the corresponding orbits in the trees T and S (which need not be homeomorphic) are essentially preserved

Distortion of surface groups in Cat (0) free-by-cyclic groups

Given a non-positively curved 2-complex with a circle-valued Morse function satisfying some extra combinatorial conditions, we describe how to locally isometrically embed this in a larger non- positively curved 2-complex with free-by-cyclic fundamental group. This embedding procedure is used to produce examples of CAT(0) free-by-cyclic groups that contain closed hyperbolic surface subgroups with polynomial distortion of arbitrary degree. We also produce examples of CAT(0) hyperbolic free-by-cyclic groups that contain closed hyperbolic surface subgroups that are exponentially distorted.

Free and fragmenting filling length

The filling length of an edge-circuit η in the Cayley 2-complex of a finite presentation of a group is the minimal integer length L such that there is a combinatorial null-homotopy of η down to a base point through loops of length at most L. We introduce similar notions in which the full-homotopy is not required to fix a base point, and in which the contracting loop is allowed to bifurcate. We exhibit a group in which the resulting filling invariants exhibit dramatically different behaviour to the standard notion of filling length. We also define the corresponding filling invariants for Riemannian manifolds and translate our results to this setting.

Testing Cayley graph densities

We present a computer-assisted analysis of combinatorial properties of the Cayley graphs of certain finitely generated groups: Given a group with a finite set of generators, we study the density of the corresponding Cayley graph, that is, the least upper bound for the average vertex degree (= number of adjacent edges) of any finite subgraph. It is known that an m-generated group is amenable if and only if the density of the corresponding Cayley graph equals to 2m. We test amenable and non-amenable groups, and also groups for which amenability is unknown. In the latter class we focus on Richard Thompson’s group F.

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.

Brown representability follows from Rosicky

We prove that the dual of a well generated triangulated category satisfies Brown representability, as long as there is a combinatorial model. This settles the major open problem in [13]. We also prove that Brown representability holds for non-dualized well generated categories, but that only amounts to the fourth known proof of the fact. The proof depends crucially on a new result of Rosicky [14].

Agent based simulation to optimise emergency departments

Nowadays, many of the health care systems are large and complex environments and quite dynamic, specifically Emergency Departments, EDs. It is opened and working 24 hours per day throughout the year with limited resources, whereas it is overcrowded. Thus, is mandatory to simulate EDs to improve qualitatively and quantitatively their performance. This improvement can be achieved modelling and simulating EDs using Agent-Based Model, ABM and optimising many different staff scenarios. This work optimises the staff configuration of an ED. In order to do optimisation, objective functions to minimise or maximise have to be set. One of those objective functions is to find the best or optimum staff configuration that minimise patient waiting time. The staff configuration comprises: doctors, triage nurses, and admissions, the amount and sort of them. Staff configuration is a combinatorial problem, that can take a lot of time to be solved. HPC is used to run the experiments, and encouraging results were obtained. However, even with the basic ED used in this work the search space is very large, thus, when the problem size increases, it is going to need more resources of processing in order to obtain results in an acceptable time.

Colocaciones léxicas en dicconarios monolingües generales del español

El objetivo de la presente investigación es analizar el tratamiento que algunos de los diccionarios generales monolingües del español aparecidos en los últimos diez años han dado al fenómeno de las colocaciones léxicas, a saber, aquellas combinaciones de palabras que, desde el punto de vista de la norma, presentan ciertas restricciones combinatorias, esencialmente de carácter semántico, impuestas por el uso (Corpas: 1996). Los repertorios objeto de análisis han sido: el "Diccionario Salamanca de la lengua española", dirigido por Juan Gutiérrez (1996); el "Diccionario del español actual", de Manuel Seco, Olimpia Andrés y Gabino Ramos (1999); la vigésima segunda edición del diccionario de la RAE (2001); y el "Gran diccionario de uso del español actual. Basado en el corpus Cumbre", dirigido por Aquilino Sánchez (2001). Nuestro estudio se ha fundamentado en un corpus de 52 colocaciones léxicas confeccionado a partir del análisis de las subentradas contenidas en la letra "b" de cada uno de los diccionarios seleccionados. Posteriormente, hemos examinado las entradas correspondientes a cada uno de los elementos que constituyen la colocación (base y colocativo) con el fin de observar si los diccionarios estudiados dan cuenta de estas mismas combinaciones en otras partes del artículo lexicográfico, como son las definiciones o los ejemplos. A la hora de analizar la información lexicográfica hemos centrado nuestra atención en cuatro aspectos: a) la información contenida en las páginas preliminares de cada una de las obras; b) la ubicación de las colocaciones en el artículo lexicográfico; c) la asignación de la colocación a un artículo determinado; y d) la marcación gramatical.

Computing hypergraph width measures exactly

Hypergraph width measures are a class of hypergraph invariants important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponential algorithm for a large variety of these measures. A connection between these and tree decompositions is established. This enables us to almost seamlessly adapt the combinatorial and algorithmic results known for tree decompositions of graphs to the case of hypergraphs and obtain fast exact algorithms. As a consequence, we provide algorithms which, given a hypergraph H on n vertices and m hyperedges, compute the generalized hypertree-width of H in time O*(2n) and compute the fractional hypertree-width of H in time O(1.734601n.m).1

Decision Support Methods for Global Optomization

Immobile location-allocation (LA) problems is a type of LA problem that consists in determining the service each facility should offer in order to optimize some criterion (like the global demand), given the positions of the facilities and the customers. Due to the complexity of the problem, i.e. it is a combinatorial problem (where is the number of possible services and the number of facilities) with a non-convex search space with several sub-optimums, traditional methods cannot be applied directly to optimize this problem. Thus we proposed the use of clustering analysis to convert the initial problem into several smaller sub-problems. By this way, we presented and analyzed the suitability of some clustering methods to partition the commented LA problem. Then we explored the use of some metaheuristic techniques such as genetic algorithms, simulated annealing or cuckoo search in order to solve the sub-problems after the clustering analysis

Solving Large Location-Allocation problems by Clustering and Simulated Annealing

Globalization involves several facility location problems that need to be handled at large scale. Location Allocation (LA) is a combinatorial problem in which the distance among points in the data space matter. Precisely, taking advantage of the distance property of the domain we exploit the capability of clustering techniques to partition the data space in order to convert an initial large LA problem into several simpler LA problems. Particularly, our motivation problem involves a huge geographical area that can be partitioned under overall conditions. We present different types of clustering techniques and then we perform a cluster analysis over our dataset in order to partition it. After that, we solve the LA problem applying simulated annealing algorithm to the clustered and non-clustered data in order to work out how profitable is the clustering and which of the presented methods is the most suitable