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.

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.

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."

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.

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.

On a family of strongly regular graphs with λ = 1

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