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.

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.

Distortion of wreath products in some finitely presented groups

"Vegeu el resum a l'inici del document del fitxer adjunt."

Distortion of Hausdorff measures and improved Painlevé removability for quasiregular mappings

"Vegeu el resum a l'inici del document del fitxer adjunt."

Quasiconformal distortion of Riesz capacities and Hausdorff measures in the plane

In this paper we prove the sharp distortion estimates for the quasiconformal mappings in the plane, both in terms of the Riesz capacities from non linear potential theory and in terms of the Hausdorff measures.

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.

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.

Distortion theorems for quasiconformal mappings

L'any 1994, Astala publicà el reconegut teorema de distorió de l'àrea per aplicacions quasiconformes, un resultat innovador que va permetre que n'apareguessin nombrosos més dins d'aquest camp de l'anàlisi durant la darrera dècada. Ens centrem en les conseqüències que té en la distorsió de la mesura de Hausdorff. Seguim la demostració de Lacey, Sawyer i Uriarte-Tuero per la distorsió del contingut de Hausdorff, clarificant-ne alguns punts i canviant l'enfocament per l'acotació de la transformada de Beurling, on prenem les idees d'Astala, Clop, Tolsa, Uriarte-Tuero i Verdera.

Distortion control for delay-sensitive sources

We investigate the problem of finding minimum-distortion policies for streaming delay-sensitive but distortion-tolerant data. We consider cross-layer approaches which exploit the coupling between presentation and transport layers. We make the natural assumption that the distortion function is convex and decreasing. We focus on a single source-destination pair and analytically find the optimum transmission policy when the transmission is done over an error-free channel. This optimum policy turns out to be independent of the exact form of the convex and decreasing distortion function. Then, for a packet-erasure channel, we analytically find the optimum open-loop transmission policy, which is also independent of the form of the convex distortion function. We then find computationally efficient closed-loop heuristic policies and show, through numerical evaluation, that they outperform the open-loop policy and have near optimal performance.

The minimax distortion redundancy in empirical quantizer design

We obtain minimax lower and upper bounds for the expected distortionredundancy of empirically designed vector quantizers. We show that the meansquared distortion of a vector quantizer designed from $n$ i.i.d. datapoints using any design algorithm is at least $\Omega (n^{-1/2})$ awayfrom the optimal distortion for some distribution on a bounded subset of${\cal R}^d$. Together with existing upper bounds this result shows thatthe minimax distortion redundancy for empirical quantizer design, as afunction of the size of the training data, is asymptotically on the orderof $n^{1/2}$. We also derive a new upper bound for the performance of theempirically optimal quantizer.

Comparing Random-based and k-Anonymity-Based Algorithms for Graph Anonymization

Recently, several anonymization algorithms have appeared for privacy preservation on graphs. Some of them are based on random-ization techniques and on k-anonymity concepts. We can use both of them to obtain an anonymized graph with a given k-anonymity value. In this paper we compare algorithms based on both techniques in orderto obtain an anonymized graph with a desired k-anonymity value. We want to analyze the complexity of these methods to generate anonymized graphs and the quality of the resulting graphs.

Dimerization of polyacetylene treated as a spin-Peierls distortion of the Heisenberg Hamiltonian

Extracting a bond-length-dependent Heisenberg-like Hamiltonian from the potential-energy surfaces of the two lowest states of ethylene, it is possible to study the geometry of polyacetylene by minimization of the cohesive energy, using both variational-cluster and Rayleigh-Schrödinger perturbative expansions. The dimerization amplitude is satisfactorily reproduced. Optimizing the variational-cluster-expansion total energy with the equal-bond-length constraint, the barrier to reversal of alternation is obtained. The alternating-to-regular phase transition is treated from the Néel-state starting function and appears to be of second order.