On a family of strongly regular graphs with λ = 1

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

Restricted walks in regular trees

Let T be the Cayley graph of a finitely generated free group F. Given two vertices in T consider all the walks of a given length between these vertices that at a certain time must follow a number of predetermined steps. We give formulas for the number of such walks by expressing the problem in terms of equations in F and solving the corresponding equations.

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.

Strongly non-degenerate Lie algebras

Let A be a semiprime 2 and 3-torsion free non-commutative associative algebra. We show that the Lie algebra Der(A) of(associative) derivations of A is strongly non-degenerate, which is a strong form of semiprimeness for Lie algebras, under some additional restrictions on the center of A. This result follows from a description of the quadratic annihilator of a general Lie algebra inside appropriate Lie overalgebras. Similar results are obtained for an associative algebra A with involution and the Lie algebra SDer(A) of involution preserving derivations of A

New FFT/IFFT Factorizations with Regular Interconnection Pattern Stage-to-Stage Subblocks

Les factoritzacions de la FFT (Fast Fourier Transform) que presenten un patró d’interconnexió regular entre factors o etapes son conegudes com algorismes paral·lels, o algorismes de Pease, ja que foren originalment proposats per Pease. En aquesta contribució s’han desenvolupat noves factoritzacions amb blocs que presenten el patró d’interconnexió regular de Pease. S’ha mostrat com aquests blocs poden ser obtinguts a una escala prèviament seleccionada. Les noves factoritzacions per ambdues FFT i IFFT (Inverse FFT) tenen dues classes de factors: uns pocs factors del tipus Cooley-Tukey i els nous factors que proporcionen la mateix patró d’interconnexió de Pease en blocs. Per a una factorització donada, els blocs comparteixen dimensions, el patró d’interconnexió etapa a etapa i a més cada un d’ells pot ser calculat independentment dels altres.

Singular integrals on Ahlfors-David regular subsets of the Heisenberg group

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

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.

Level-wise node size distribution of randomly generated regular trees

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

Superatomic Boolean algebras constructed from strongly unbounded functions

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

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.

El espacio como producto social: variables arqueológicas para un análisis de la organización social en prehistoria

El espacio social es un concepto ambiguo cuyo componente material está determinado por el carácter del componente social, puesto que la organización de los objetos en el espacio y el espacio mismo, responden a las normas sociales del comportamiento humano. Partimos de la premisa que los residuos generados durante el proceso de producción y del consumo tienden a tener una distribución relativamente regular en el espacio físico. La ausencia de la aleatoriedad en la dispersión de estos restos solo significa que habían sido acumulados y depositados como restos de acciones previamente planificadas no-aleatoriamente. En este trabajo planteamos estudiar la organización y la producción del espacio social de una sociedad cazadora-recolectora concreta – la sociedad yámana - a través del análisis de las actividades cotidianas que figuran en las fuentes etnográficas y en el registro arqueológico. Con este fin creamos una metodología de trabajo interdisciplinaria, basada en un enfoque etnoarqueológico, y a través del estudio de las fuentes etnográficas, los trabajos etnoarqueológicos previos y el registro arquelógico concreto, descubrimos cuáles son las posibilidades y limitaciones de este tipo de estudios. Pudimos reconocer la regularidad espacial de los procesos de producción y reproducción social y a resolver algunas preguntas acerca del estudio de la organización social en prehistoria trabajando con los datos etnoarqueológicos obtenidos en los yacimientos Lanashuaia y Túnel VII (Tierra del Fuego, Argentina), analizando el registro extraido y trabajado en varias campañas de excavaciones arqueológicas en ultimos 25 años. El presente trabajo al fondo es un experimento etnoarqueológico estándar: partiendo de la observación etnográfica registramos unas recurrencias específicas entre algunas variables (por ejemplo: mujer/lugar/tipo de trabajo), intentamos extraer las variables definitorias de esas recurrencias, y finalmente las buscamos en el espacio definido arqueológicamente.  

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.

Irregular to regular sampling, denoising and deconvolution

We propose a restoration algorithm for band limited images that considers irregular(perturbed) sampling, denoising, and deconvolution. We explore the application of a family ofregularizers that allow to control the spectral behavior of the solution combined with the irregular toregular sampling algorithms proposed by H.G. Feichtinger, K. Gr¨ochenig, M. Rauth and T. Strohmer.Moreover, the constraints given by the image acquisition model are incorporated as a set of localconstraints. And the analysis of such constraints leads to an early stopping rule meant to improvethe speed of the algorithm. Finally we present experiments focused on the restoration of satellite images, where the micro-vibrations are responsible of the type of distortions we are considering here. We will compare results of the proposed method with previous methods and show an extension tozoom.

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.