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.

Theoretical aspects of graph models for MANETs

We survey the main theoretical aspects of models for Mobile Ad Hoc Networks (MANETs). We present theoretical characterizations of mobile network structural properties, different dynamic graph models of MANETs, and finally we give detailed summaries of a few selected articles. In particular, we focus on articles dealing with connectivity of mobile networks, and on articles which show that mobility can be used to propagate information between nodes of the network while at the same time maintaining small transmission distances, and thus saving energy.

A linear optimization technique for graph pebbling

Graph pebbling is a network model for studying whether or not a given supply of discrete pebbles can satisfy a given demand via pebbling moves. A pebbling move across an edge of a graph takes two pebbles from one endpoint and places one pebble at the other endpoint; the other pebble is lost in transit as a toll. It has been shown that deciding whether a supply can meet a demand on a graph is NP-complete. The pebbling number of a graph is the smallest t such that every supply of t pebbles can satisfy every demand of one pebble. Deciding if the pebbling number is at most k is NP 2 -complete. In this paper we develop a tool, called theWeight Function Lemma, for computing upper bounds and sometimes exact values for pebbling numbers with the assistance of linear optimization. With this tool we are able to calculate the pebbling numbers of much larger graphs than in previous algorithms, and much more quickly as well. We also obtain results for many families of graphs, in many cases by hand, with much simpler and remarkably shorter proofs than given in previously existing arguments (certificates typically of size at most the number of vertices times the maximum degree), especially for highly symmetric graphs. Here we apply theWeight Function Lemma to several specific graphs, including the Petersen, Lemke, 4th weak Bruhat, Lemke squared, and two random graphs, as well as to a number of infinite families of graphs, such as trees, cycles, graph powers of cycles, cubes, and some generalized Petersen and Coxeter graphs. This partly answers a question of Pachter, et al., by computing the pebbling exponent of cycles to within an asymptotically small range. It is conceivable that this method yields an approximation algorithm for graph pebbling.

Phlebotomine Sand Flies from São Gabriel da Cachoeira (State of Amazonas, Brazil) with a Description of Lutzomyia (Psychodopygus) douradoi n. sp. (Diptera: Psychodidae)

Thirty-five species of Lutzomyia and two species of Brumptomyia were identified among 795 phlebotomines taken in light-traps near the upper reaches of the middle Rio Negro. The subgenus Psychodopygus predominated in number of species (11) and relative abundance (74-81% in light trap samples from the forest and 99% on human bait). For many of the species these records help to fill large gaps on current maps of distribution, and for others (L. olmeca nociva, L. mangabeirana, L. triacantha) the findings represent a significant expansion of their known range. A new species in the subgenus Psychodopygus (L. douradoi) is described from both sexes, and L. bettinii is recorded for the first time in Brazil.

The involvement of thaumatin-like proteins in plant food cross-reactivity: a multicenter study using a specific protein microarray

Cross-reactivity of plant foods is an important phenomenon in allergy, with geographical variations with respect to the number and prevalence of the allergens involved in this process, whose complexity requires detailed studies. We have addressed the role of thaumatin-like proteins (TLPs) in cross-reactivity between fruit and pollen allergies. A representative panel of 16 purified TLPs was printed onto an allergen microarray. The proteins selected belonged to the sources most frequently associated with peach allergy in representative regions of Spain. Sera from two groups of well characterized patients, one with allergy to Rosaceae fruit (FAG) and another against pollens but tolerant to food-plant allergens (PAG), were obtained from seven geographical areas with different environmental pollen profiles. Cross-reactivity between members of this family was demonstrated by inhibition assays. Only 6 out of 16 purified TLPs showed noticeable allergenic activity in the studied populations. Pru p 2.0201, the peach TLP (41%), chestnut TLP (24%) and plane pollen TLP (22%) proved to be allergens of probable relevance to fruit allergy, being mainly associated with pollen sensitization, and strongly linked to specific geographical areas such as Barcelona, Bilbao, the Canary Islands and Madrid. The patients exhibited >50% positive response to Pru p 2.0201 and to chestnut TLP in these specific areas. Therefore, their recognition patterns were associated with the geographical area, suggesting a role for pollen in the sensitization of these allergens. Finally, the co-sensitizations of patients considering pairs of TLP allergens were analyzed by using the co-sensitization graph associated with an allergen microarray immunoassay. Our data indicate that TLPs are significant allergens in plant food allergy and should be considered when diagnosing and treating pollen-food allergy.

Clustering algorithms for anti-money laundering using graph theory and social network analysis

HEMOLIA (a project under European community’s 7th framework programme) is a new generation Anti-Money Laundering (AML) intelligent multi-agent alert and investigation system which in addition to the traditional financial data makes extensive use of modern society’s huge telecom data source, thereby opening up a new dimension of capabilities to all Money Laundering fighters (FIUs, LEAs) and Financial Institutes (Banks, Insurance Companies, etc.). This Master-Thesis project is done at AIA, one of the partners for the HEMOLIA project in Barcelona. The objective of this thesis is to find the clusters in a network drawn by using the financial data. An extensive literature survey has been carried out and several standard algorithms related to networks have been studied and implemented. The clustering problem is a NP-hard problem and several algorithms like K-Means and Hierarchical clustering are being implemented for studying several problems relating to sociology, evolution, anthropology etc. However, these algorithms have certain drawbacks which make them very difficult to implement. The thesis suggests (a) a possible improvement to the K-Means algorithm, (b) a novel approach to the clustering problem using the Genetic Algorithms and (c) a new algorithm for finding the cluster of a node using the Genetic Algorithm.