Especificación e implementación de una librería para el estudio de la secuencia de excentricidades de un grafo

Implementación de una librería en Java capaz de calcular grafos conexos, incluidos todos los grafos conexos no isomorfos a un orden dado y sus respectivas tablas de secuencias de excentricidades (para órdenes pequeños). Aparte se ha realizado un estudio del sistema Nauty y se han utilizado sus ficheros auxiliares.

Implementació de la cerca d'un subgraf comú maximal a dos grafs mitjançant colles

La memòria que ací es presenta s'emmarca dins de l'àrea de teoria de grafs. En concret es treballa la implementació d'un algorisme per trobar el subgraf comú maximal (SCM) de dos grafs mitjançant la cerca de colles maximals (CM). L'aportació principal del projecte consisteix en, donats dos grafs qualsevol, trobar el seu graf associat per tal de poder cercar la seva colla maximal (CM). I així, utilitzant funcions existents en el llenguatge de programació, poder trobar el seu subgraf comú maximal (SCM), necessari per calcular la distància entre grafs i així determinar quan d'isomorfs són.

La privacitat de les connexions dels usuaris d'una xarxa social

Aquest projecte mostra com les connexions dels usuaris d'una xarxa social suposen un risc afegit per a la privacitat dels usuaris que hi formen part. Aquestes connexions ofereixen informació suficient per a poder dur a terme processos d'agregació d'informació entre diferents xarxes socials, permetent a un atacant millorar el seu coneixement inicial sobre les xarxes. El projecte és un recorregut per totes les fases necessàries per dur a terme aquest procés, des de la recollida de la informació fins a l'agregació de les dades obtingudes.

Aplicació de representació gràfica de grafs de mobilitat

El programa tracta de fer transformacions de linies simples amb informació en grafs més visuals, definint carrils, simbologies de carril i linies de divisió de trams.

Análisis, comparativa y visualización de redes sociales on-line representadas como grafos

El presente documento conduce a un análisis y comparativa de diferentes y variados conjuntos de redes sociales on-line. Para ello, primero se explica la base teórica de teoría de grafos para su interpretación y comprensión, así como de la base matemática que fundamenta el tipo específico de red estudiada y las diferentes métricas (estadísticas) extraídas de estas. Luego, se ofrece una detallada explicación del entorno de trabajo tanto para la aplicación informática desarrollada, como para posterior visualización y también una explicación y los algoritmos utilizados en las funciones implementadas con tales fines. Para finalizar el documento, se realiza una inmersión particular en cada red social on-line, puntualizando sus características y finalizando con una comparativa general entre todas ellas, siempre acompañadas con sus respectivas visualizaciones en el espacio 2D representadas en forma de grafo.

The Patterson-Sullivan embedding and minimal volume entropy for outer space

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

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.

On the number of K3,3-minor-free and maximal K3,3-minor-free graphs

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

Orthogonal systems in finite grahps

To a finite graph there corresponds a free partially commutative group: with the given graph as commutation graph. In this paper we construct an orthogonality theory for graphs and their corresponding free partially commutative groups. The theory developed here provides tools for the study of the structure of partially commutative groups, their universal theory and automorphism groups. In particular the theory is applied in this paper to the centraliser lattice of such groups.

Random graphs on surfaces

Counting labelled planar graphs, and typical properties of random labelled planar graphs, have received much attention recently. We start the process here of extending these investigations to graphs embeddable on any fixed surface S. In particular we show that the labelled graphs embeddable on S have the same growth constant as for planar graphs, and the same holds for unlabelled graphs. Also, if we pick a graph uniformly at random from the graphs embeddable on S which have vertex set {1, . . . , n}, then with probability tending to 1 as n → ∞, this random graph either is connected or consists of one giant component together with a few nodes in small planar components.

A class of stochastic games with infinitely many interacting agents related to Glauber dynamics on random graphs

We introduce and study a class of infinite-horizon nonzero-sum non-cooperative stochastic games with infinitely many interacting agents using ideas of statistical mechanics. First we show, in the general case of asymmetric interactions, the existence of a strategy that allows any player to eliminate losses after a finite random time. In the special case of symmetric interactions, we also prove that, as time goes to infinity, the game converges to a Nash equilibrium. Moreover, assuming that all agents adopt the same strategy, using arguments related to those leading to perfect simulation algorithms, spatial mixing and ergodicity are proved. In turn, ergodicity allows us to prove “fixation”, i.e. that players will adopt a constant strategy after a finite time. The resulting dynamics is related to zerotemperature Glauber dynamics on random graphs of possibly infinite volume.

On locally finite transitive two-ended digraphs

Projecte de recerca elaborat a partir d’una estada al Department de Matemàtica Aplicada de la Montanuniversität Leoben, Àustria, entre agost i desembre del 2006. L’ objectiu ha estat fer recerca sobre digrafs infinits amb dos finals, connexos i localment finits, i, en particular, en digrafs amb dos finals i altament arc-transitius. Malnic, Marusic et al. van introduir un nou tipus de relació d’equivalència en els vèrtexs d’un dígraf, anomenades relacions d’assolibilitat, que generalitzen i tenen el seu origen en un problema posat per Cameron et al., on les classes de la relació d’equivalència eren vèrtexs que pertanyien a un camí alternat del dígraf . Malnic et al. en el mencionat article van establir connexions ben estretes entre aquestes relacions d’assolibilitat i l'estructura de finals i creixement dels digrafs localment finits i transitius. En aquest treball, s’ha caracteritzat per complet aquestes relacions d’assolibitat en el cas de dígrafs localment finits i transitius amb exactament dos finals, en termes de la descomposició en números primers del número de línies que genera el digraf amb dos finals. A més, es nega la Conjectura 1 sostinguda per Seifter que afirmava que un digraf connex localment finit amb més d’un final era necessàriament o be 0-, 1- o altament arc-transitiu. Seifer havia donat una solució parcial a la conjectura pel cas de digrafs regulars amb grau primer que tinguin un conjunt de tall connex. En aquest treball, es descriu una família infinita de dígrafs regulars de grau dos, amb dos finals, exactament 2-arc transitius i no 3-arc transitius. Així, es nega la Conjectura de Seifter en el cas general, fins i tot per grau primer. Tot i així, la solució parcial donada per Seifter en el seu article és en cert sentit la millor possible i l'existència un conjunt de tall connex essencial.

On the growth rate of minor-closed classes of graphs

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

On graphs with few disjoint t-stars

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

Level-wise node size distribution of randomly generated regular trees

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