Search

Let G be a graph on n vertices and with maximum degree ¿, and let k be an integer. The k-recolouring graph of G is the graph whose vertices are k-colourings of G and where two k-colourings are adjacent if they differ at exactly one vertex. It is well known that the k-recolouring graph is connected for . Feghali, Johnson and Paulusma (J. Graph Theory 83 (2016) 340–358) showed that the (¿ + 1)-recolouring graph is composed by a unique connected component of size at least 2 and (possibly many) isolated vertices. In this paper, we study the proportion of isolated vertices (also called frozen colourings) in the (¿ + 1)-recolouring graph. Our first contribution is to show that if G is connected, the proportion of frozen colourings of G is exponentially smaller in n than the total number of colourings. This motivates the use of the Glauber dynamics to approximate the number of (¿ + 1)-colourings of a graph. In contrast to the conjectured mixing time of O(nlog n) for colours, we show that the mixing time of the Glauber dynamics for (¿ + 1)-colourings restricted to non-frozen colourings can be O(n 2). Finally, we prove some results about the existence of graphs with large girth and frozen colourings, and study frozen colourings in random regular graphs., Postprint (author's final draft)

A class of graphs is bridge-addable if given a graph G in the class, any graph obtained by adding an edge between two connected components of G is also in the class. The authors recently proved a conjecture of McDiarmid, Steger, and Welsh stating that if G is bridge-addable and Gn is a uniform n-vertex graph from G, then Gn is connected with probability at least (1 + on(1))e -1/2 . The constant e -1/2 is best possible since it is reached for the class of all forests. In this paper we prove a form of uniqueness in this statement: if G is a bridge-addable class and the random graph Gn is connected with probability close to e -1/2 , then Gn is asymptotically close to a uniform n-vertex random forest in some local sense. For example, if the probability converges to e -1/2 , then Gn converges in the sense of Benjamini-Schramm to the uniform infinite random forest F8. This result is reminiscent of so-called “stability results” in extremal graph theory, with the difference that here the stable extremum is not a graph but a graph class., Supported by the European Research Council, grant ERC-2016-STG 716083 “CombiTop”, Postprint (author's final draft)

© 2020 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0, Given an integer ` = 1, a (1, = `)-identifying code in a digraph is a dominating subset C of vertices such that all distinct subsets of vertices of cardinality at most ` have distinct closed in-neighbourhood within C. In this paper, we prove that every k-iterated line digraph of minimum in-degree at least 2 and k = 2, or minimum indegree at least 3 and k = 1, admits a (1, = `)-identifying code with ` = 2, and in any case it does not admit a (1, = `)-identifying code for ` = 3. Moreover, we find that the identifying number of a line digraph is lower bounded by the size of the original digraph minus its order. Furthermore, this lower bound is attained for oriented graphs of minimum in-degree at least 2., This research is supported by MICINN from the Spanish Government under project PGC2018-095471-B-I00 and partially by AGAUR from the Catalan Government under project 2017SGR1087. The research of the second author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. B. Martínez-Barona has received funding from the scholarship 254379/438356 from CONACYT from Mexico. The second and third authors have received funding research and innovation programme under the Marie Sklodowska-Curie grant agreement No 734922., Peer Reviewed, Postprint (author's final draft)

List k–Coloring (LI k-COL) is the decision problem asking if a given graph admits a proper coloring compatible with a given list assignment to its vertices with colors in {1,2,..., k}. The problem is known to be NP-hard even for k = 3 within the class of 3–regular planar bipartite graphs and for k = 4 within the class of chordal bipartite graphs. In 2015 Huang, Johnson and Paulusma asked for the complexity of LI 3-COL in the class of chordal bipartite graphs. In this paper, we give a partial answer to this question by showing that LI k-COL is polynomial in the class of convex bipartite graphs. We show first that biconvex bipartite graphs admit a multichain ordering, extending the classes of graphs where a polynomial algorithm of Enright, Stewart and Tardos (2014) can be applied to the problem. We provide a dynamic programming algorithm to solve the LI k-COL in the class of convex bipartite graphs. Finally, we show how our algorithm can be modified to solve the more general LI H-COL problem on convex bipartite graphs., J. Díaz and M. Serna are partially supported by funds from MINECO and EU FEDER under grant TIN 2017-86727-C2-1-R AGAUR project ALBCOM 2017- SGR-786. O. Y. Diner is partially supported by the Scientific and Technological Research Council Tubitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra is supported by the Spanish Ministry of Science under project MTM2017-82166-P., Peer Reviewed, Postprint (author's final draft)

In the context of software model-driven development, artifacts are specified by several models describing different aspects, e.g., different views, dynamic behavior, structure, distributed information, etc. Then, maintaining and repairing consistency of the whole specification are crucial issues if the models can be separately developed and updated. Model Synchronization is the process of restoring consistency after the update of one or several of the models. In the present work, we approach the case when conflicts may arise due to concurrently updating different models. Specifically, based on the Triple Graph Grammar approach, we propose an incremental algorithm CSynch for solving conflicts and repairing consistency. In addition, we identify and formalize when a synchronizing solution can be considered adequate and show that our procedure CSynch is sound and complete., Peer Reviewed, Postprint (published version)

A k-coloring of a graph G is a k-partition of into independent sets, called colors. A k-coloring is called neighbor-locating if for every pair of vertices belonging to the same color , the set of colors of the neighborhood of u is different from the set of colors of the neighborhood of v. The neighbor-locating chromatic number is the minimum cardinality of a neighbor-locating coloring of G. We establish some tight bounds for the neighbor-locating chromatic number of a graph, in terms of its order, maximum degree and independence number. We determine all connected graphs of order with neighbor-locating chromatic number n or . We examine the neighbor-locating chromatic number for two graph operations: join and disjoint union, and also for two graph families: split graphs and Mycielski graphs., Peer Reviewed, Postprint (author's final draft)

© 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0, The k-independence number of a graph is the maximum size of a set of vertices at pairwise distance greater than k. A graph is called k-partially walk-regular if the number of closed walks of a given length l = k, rooted at a vertex v, only depends on l. In particular, a distance-regular graph is also k-partially walk-regular for any k. In this paper, we introduce a new family of polynomials obtained from the spectrum of a graph, called minor polynomials. These polynomials, together with the interlacing technique, allow us to give tight spectral bounds on the k-independence number of a k-partially walk-regular graph. With some examples and infinite families of graphs whose bounds are tight, we also show that the odd graph O` with ` odd has no 1-perfect code. Moreover, we show that our bound coincide, in general, with the Delsarte’s linear programming bound and the Lovász theta number ¿, the best ones to our knowledge. In fact, as a byproduct, it is shown that the given bounds also apply for ¿ and T, the Shannon capacity of a graph. Moreover, apart from the possible interest that the minor polynomials can have, our approach has the advantage of yielding closed formulas and, so, allowing asymptotic analysis., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government under project PGC2018-095471-B-I00., Peer Reviewed, Postprint (author's final draft)

This paper tackles the problem of user scheduling in satellite content delivery networks with precoding. The clustering process has to consider two crucial and independent characteristics of the user terminals. On the one hand, users belonging to the same group shall have a reduced Euclidean norm between their channel vectors in order to obtain the maximum precoding gain. On the other hand, with the aim of exploiting the multicast capabilities of the system, user terminals grouped in the same cluster shall have requested the same content. The resulting clustering problem is formulated as a multigraph (also known as multiview) spectral clustering problem. The paper shows that this unsupervised learning framework is able to capture the different peculiarities of the mentioned problem. Two different techniques are introduced and validated in a close-to-real numerical simulation., This work has received funding from the Spanish ministry of Science, Innovation and Universities under project TERESA-TEC2017-90093-C3-1-R (AEI/FEDER,UE), and by the Catalan Government under grant 2017-SGR01479., Peer Reviewed, Postprint (author's final draft)

Recently, a Graph Neural Network (GNN) model called RouteNet was proposed as a method to estimate end-to-end computer network performance metrics (e.g. delay, jitter, packet loss rate) given information about topology, routing con guration, and tra c demands of the network. RouteNet achieves an accuracy comparable to packet-level simulators but at a fraction of their computational cost. In spite of its success in making accurate estimations and generalizing to unseen topologies, it does not take into account all the complex particularities of real computer networks. One of the simplifying assumptions that RouteNet makes is to assume that all nodes (forwarding devices) in the network have the same characteristics. In this thesis, we propose a new architecture that allows to introduce the concept of node into RouteNet and support the modelling of di erent forwarding device features. To assess the validity of the new architecture we build a data set composed of network scenarios where nodes have di erent queue sizes, and then we use it to train and evaluate the proposed model. Our solution constitutes one step forward towards building more realistic network models that can be used to optimize and manage real-world computer networks.

It is well known that, in general, part of the spectrum of a graph can be obtained from the adjacency matrix of its quotient graph given by a regular partition. In this paper, a method that gives all the spectrum, and also the local spectra, of a graph from the quotient matrices of some of its regular partitions, is proposed. Moreover, from such partitions, the C -local multiplicities of any class of vertices C is also determined, and some applications of these parameters in the characterization of completely regular codes and their inner distributions are described. As examples, it is shown how to find the eigenvalues and (local) multiplicities of walk-regular, distance-regular, and distance-biregular graphs., Received by the editors on February 20, 2020. Accepted for publication on May 27, 2020. Handling Editor: Sebastian M.Cioaba. Corresponding Author: Cristina Dalf ́o.†Departament de Matem`atica, Universitat de Lleida, Igualada (Barcelona), Catalonia (cristina.dalfo@udl.cat). Partiallysupported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Governmentunder projects PGC2018-095471-B-I00 and MTM2017-83271-R. Also received funding from the European Union’s Horizon 2020research and innovation programme under the Marie Sk lodowska-Curie grant agreement no. 734922.‡Departament de Matem`atiques, Barcelona Graduate School of Mathematics, Universitat Polit`ecnica de Catalunya,Barcelona, Catalonia, (miguel.angel.fiol@upc.edu). Partially supported by AGAUR from the Catalan Government under project2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00., Peer Reviewed, Postprint (author's final draft)

Given the complexity, size, cost, and importance of network infrastructures like the internet, telecommunication, transportation, and social networks, it is not surprising the attention that research on network analysis and protection is receiving. Today¿s world of technological advances creates high expectations in all those areas that humans and computers can manage. Thus, in the context of network science, we expect networks to keep their performance and be adaptative and resilient to diverse circumstances. As all networks are subject to attacks and collapse, safety protocols should be designed to provide tools to mitigate possible network failures. Many networks suffer attacks periodically: Twitter, Amazon, eBay have experienced denial-of-service for hours and even days, power grids have undergone massive blackouts, and similar incidents have happened for many other real networks. The failure usually propagates from one component to another in a cascade manner, known as cascade failure. Cascading failure studies investigate potential solutions to make networks more robust. There are some vital nodes within each network that have a profound influence on cascading phenomena. In this TFM, giving focus to cascade failure analysis, we explore several network structural properties that might impact the network performance when it is under attack, in particular k-core measure. Moreover, a recently proposed deterministic hierarchical graph family, which appears to be a good model for real networks, has been examined under attacks along with some other graph models. By comparing their relative performance, we can assess if this network can be a model to improve future network designs. Our findings show that networks with a high minimum k-core and negative degree-degree correlation (disassortative) perform better under attacks than assortative networks with low minimum k-core. To enhance the robustness of existing networks, we can modify them in a way to have less assorta

Computing a mapping between two process models is a crucial technique, since it enables reasoning and operating across processes, like providing a similarity score between two processes, or merging different process variants to generate a consolidated process model. In this paper we present a new flexible technique for process model mapping, based on the relaxation labeling constraint satisfaction algorithm. The technique can be instantiated so that different modes are devised, depending on the context. For instance, it can be adapted to the case where one of the mapped process models is incomplete, or it can be used to ground an adaptable similarity measure between process models. The approach has been implemented inside the open platform NLP4BPM, providing a visualization of the performed mappings and computed similarity scores. The experimental results witness the flexibility and usefulness of the technique proposed., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed, Postprint (author's final draft)

Al llarg dels últims anys, hem pogut comprovar el gran potencial que tenen les Graph Neural Networks (GNN) al aplicar-se a una gran varietat de problemes que es formalitzen en forma de grafs (e.g xarxes de telecomunicacions, química, física..). Normalment, la aplicació de GNNs a cadascun d'aquests camps implica un procés de personalització del model per tal d'adaptar-lo al problema en qüestió. En aquest context, aquesta sol ser una tasca molt complexa i que, en conseqüència, requereix d'experts en aprenentatge automàtic per a dur-la a terme. Més concretament, per a implementar la solució en llenguatges basats en operacions de tensors, com per exemple Tensorflow o PyTorch. Tot i així, nosaltres argumentem que és imprescindible la creació d'eines que permetin dur a terme una abstracció del problema de manera automàtica, simplificant així la seva creació per part de l'usuari. Per aquest motiu, en aquesta tèsis introduïm un nou framework que anomenem IGNNITION, que permet crear GNNs ràpidament i de manera molt entenedora. IGNNITION, doncs, està enfocat a oferir flexibilitat per a la creació d'una gran varietat de GNNs, especialment als usuaris amb molts pocs coneixements d'aprenentatge automàtic. Per a fer-ho, el framework que proposem permet definir models a través d'una simple descripció de les seves parts i la manera en que aquestes es relacionen. A més a més, per tal d'assistir als usuaris, el framework inclou un sistema de debug que permet identificar ràpidament els possibles errors. Els nostres resultats experimentals, quelcom, demostren que la precisió dels models de GNN generats per IGNNITION són equivalents a la implementació original, així com que no es produeix cap pèrdua significativa d'eficiència., Recent years have witnessed the vast potential of Graph Neural Networks (GNN) to be applied to a plethora of problems where data is structured as graphs (e.g., computer networks, chemistry, physics). Typically, each new application requires custom GNN models adapted to the problem environment. In this context, implementing a GNN model is a cumbersome task that currently requires Machine Learning (ML) experts with high skills in neural network programming. For instance, to translate the model to complex tensor-wise operations in languages such as TensorFlow or PyTorch. We claim that to approach GNNs to real-world applications it is essential to count on tools that abstract users from the complexity behind the implementation of such models. In this thesis, we propose IGNNITION, a novel framework to fast prototype complex GNN models. IGNNITION targets users with little to no background on neural network programming, while still providing great flexibility to implement a broad variety of GNN architectures. Our framework enables us to define a GNN model as an intuitive human-readable description of the objects present in graphs and the type of relations they may have, and it automatically generates an efficient TensorFlow implementation of the model. To assist users, it provides advanced debugging mechanisms to easily identify and correct possible errors in GNN models. Our experimental results show that GNN models generated by our framework do not incur performance loss compared to native implementations in TensorFlow.

The Sacking index of a tree is a measure of balance which has beenintroduced in applications to phylogenetics. The study of this parameterin rooted binary trees, identifying its extremal values and enumerationof trees with given index, has been recently achieved by MareikeFischer. The goal of this project is to extend this analysis to particularly for the classes of rootedk-ary trees for general k. Finally, we will study the symmetry of the binary trees and we will propose some indexes to measure how symmetric is a tree

© 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0, In this paper, we present a method to obtain regular (or equitable) partitions of Cayley (di)graphs (that is, graphs, digraphs, or mixed graphs) of permutation groups on n letters. We prove that every partition of the number n gives rise to a regular partition of the Cayley graph. By using representation theory, we also obtain the complete spectra and the eigenspaces of the corresponding quotient (di)graphs. More precisely, we provide a method to find all the eigenvalues and eigenvectors of such (di)graphs, based on their irreducible representations. As examples, we apply this method to the pancake graphs and to a recent known family of mixed graphs (having edges with and without direction). As a byproduct, the existence of perfect codes in allows us to give a lower bound for the multiplicity of its eigenvalue -1., Peer Reviewed, Postprint (author's final draft)

In spatial networks vertices are arranged in some space and edges may cross. When arranging vertices in a 1D lattice edges may cross when drawn above the vertex sequence as it happens in linguistic and biological networks. Here we investigate the general problem of the distribution of edge crossings in random arrangements of the vertices. We generalize the existing formula for the expectation of this number in random linear arrangements of trees to any network and derive an expression for the variance of the number of crossings in an arbitrary layout relying on a novel characterization of the algebraic structure of that variance in an arbitrary space. We provide compact formulae for the expectation and the variance in complete graphs, complete bipartite graphs, cycle graphs, one-regular graphs and various kinds of trees (star trees, quasi-star trees and linear trees). In these networks, the scaling of expectation and variance as a function of network size is asymptotically power-law-like in random linear arrangements. Our work paves the way for further research and applications in one-dimension or investigating the distribution of the number of crossings in lattices of higher dimension or other embeddings., Peer Reviewed, Postprint (author's final draft)

The main purpose of this thesis is to nd a method that allows to systematically adapt GSP techniques so they can be used on most non-diagonalizable graph operators. In Chapter 1 we begin by presenting the framework in which GSP is developed, giving some basic de nitions in the eld of graph theory and in relation with graph signals. We also present the concept of a Graph Fourier Tranform (GFT), which will be of great importance in the proposed solution. Chapter 2 presents the actual motivation of the research: Why the computation of the GFT is problematic for some directed graphs, and the speci c cases in which this happen. We will see that the issue can not be assigned to a very speci c graph topography, and therefore it is important to develop solutions that can be applied to any directed graph. In Chapter 3 we introduce our proposed new method, which can be used to form, based on the spectral decomposition of a matrix obtained through its Schur decomposition, a complete basis of vectors that can be used as a replacement of the previously mentioned Graph Fourier Transform. The proposed method, the Graph Schur Transform (GST), aims to o er a valid operator to perform a spectral decomposition of a graph that can be used even in the case of defective matrices. Finally, in Chapter 4 we study the main properties of the proposed method and compare them with the corresponding properties o ered by the Di usion Wavelets design. In the last section we prove, for a large set of directed graphs, that the GST provides a valid solution for the problem

For any r-graph H, we consider the problem of finding a rainbow H-factor in an r-graph G with large minimum l-degree and an edge-colouring that is suitably bounded. We show that the asymptotic degree threshold is the same as that for finding an H-factor., Peer Reviewed, Postprint (author's final draft)

© 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0, In a visibility representation of a graph G, the vertices are represented by nonoverlapping geometric objects, while the edges are represented as segments that only intersect the geometric objects associated with their end-vertices. Given a set P of n points, an Anchored Visibility Representation of a graph G with n vertices is a visibility representation such that for each vertex v of G, the geometric object representing v contains a point of P. We prove positive and negative results about the existence of anchored visibility representations under various models, both in 2D and in 3D space. We consider the case when the mapping between the vertices and the points is not given and the case when it is only partially given., Peer Reviewed, Postprint (author's final draft)

Aquest document està dedicat a la història, les motivacions i algunes solu-cions alproblema dels codis de Gauss.Una corba tancada al pla pot contenir punts d’autointersecció; en suposem unnombre finit, suposem els talls no tangencials i suposem que la corba recorre cadapunt del pla un màxim de dos cops. Si etiquetem els punts de tall amb símbols diferents,triem un punt a la corba, un sentit, i, en recórrer la corba, anotem la seqüència desímbols que anem trobant, aleshores generem una paraula que s’anomena genèricamentcodi de Gauss.El problema dels codis de Gauss és el de caracteritzar quines són les possiblesparaules generades per corbes al pla. Com veurem, les solucions al problema demanengirar la cantonada., Peer Reviewed, Postprint (published version)

In recent years, researchers have realized the difficulties of fitting power-law distributions properly. These difficulties are higher in Zipfian systems, due to the discreteness of the variables and to the existence of two representations for these systems, i.e., two versions depending on the random variable to fit: rank or size. The discreteness implies that a power law in one of the representations is not a power law in the other, and vice versa. We generate synthetic power laws in both representations and apply a state-of-the-art fitting method to each of the two random variables. The method (based on maximum likelihood plus a goodness-of-fit test) does not fit the whole distribution but the tail, understood as the part of a distribution above a cutoff that separates non-power-law behavior from power-law behavior. We find that, no matter which random variable is power-law distributed, using the rank as the random variable is problematic for fitting, in general (although it may work in some limit cases). One of the difficulties comes from recovering the “hidden” true ranks from the empirical ranks. On the contrary, the representation in terms of the distribution of sizes allows one to recover the true exponent (with some small bias when the underlying size distribution is a power law only asymptotically)., Support from projects FIS2012-31324, FIS2015-71851-P, TIN2017-89244-R, PGC-FIS2018-099629-B-I00, María de Maeztu Program MDM-2014-0445, from Spanish MINECO; 2014SGR-1307, 2017SGR-856 (MACDA) from AGAUR; and the Collaborative Mathematics Project from Fundación La Caixa (I.S.) is acknowledged., Peer Reviewed, Postprint (author's final draft)

Let D(n, r) be a random r-out regular directed multigraph on the set of vertices {1, . . . , n}. In this work, we establish that for every r = 2, there exists ¿r > 0 such that diam(D(n, r)) = (1 + ¿r + o(1)) logr n. The constant ¿r is related to branching processes and also appears in other models of random undirected graphs. Our techniques also allow us to bound some extremal quantities related to the stationary distribution of a simple random walk on D(n, r). In particular, we determine the asymptotic behaviour of pmax and pmin, the maximum and the minimum values of the stationary distribution. We show that with high probability pmax = n -1+o(1) and pmin = n -(1+¿r)+o(1). Our proof shows that the vertices with p(v) near to pmin lie at the top of “narrow, slippery towers”; such vertices are also responsible for increasing the diameter from (1+o(1)) logr n to (1 + ¿r + o(1)) logr n., Postprint (author's final draft)

Electronic version of an article published as International journal of computational geometry and applications, 5 May 2020, vol. 29, núm. 4, p. 289-299. Article DOI 10.1142/S0218195919500109 © 2020 copyright World Scientific Publishing Company. Journal URL: https://www.worldscientific.com/doi/abs/10.1142/S0218195919500109, We consider quadrangulations of red and blue points in the plane where each face is convex and no edge connects two points of the same color. In particular, we show that the following problem is NP-hard: Given a finite set S of points with each point either red or blue, does there exist a convex quadrangulation of S in such a way that the predefined colors give a valid vertex 2-coloring of the quadrangulation? We consider this as a step towards solving the corresponding long-standing open problem on monochromatic point sets., This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922, Peer Reviewed, Postprint (author's final draft)

© 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0, We consider the case in which mixed graphs (with both directed and undirected edges) are Cayley graphs of Abelian groups. In this case, some Moore bounds were derived for the maximum number of vertices that such graphs can attain. We first show these bounds can be improved if we know more details about the order of some elements of the generating set. Based on these improvements, we present some new families of mixed graphs. For every fixed value of the degree, these families have an asymptotically large number of vertices as the diameter increases. In some cases, the results obtained are shown to be optimal., The first two authors have been partially supported by the project 2017SGR1087 of the Agency for the Management of University and Research Grants (AGAUR) of the Catalan Government, and by MICINN from the Spanish Government under project PGC2018- 095471-B-I00. The first and the third authors have been supported in part by grant MTM2017-86767-R of the Spanish Government., Peer Reviewed, Postprint (author's final draft)

In this thesis we characterize all intervals in the homomorphism order of digraphs in terms of universality. To do this, we first show that every interval of the class of digraphs containing cycles is universal. Then we focus our interest in the class of oriented trees (digraphs with no cycles). We give a density theorem for the class of oriented paths and a density theorem for the class of oriented trees, and we strengthen these results by characterizing all universal intervals in these classes. We conclude by summarising all statements and characterizing the universal intervals in the class of digraphs. This solves an open problem in the area.

Let Xv for v∈V be a family of n iid uniform points in the square (Formula presented.). Suppose first that we are given the random geometric graph (Formula presented.), where vertices u and v are adjacent when the Euclidean distance dE(Xu,Xv) is at most r. Let n3/14≪r≪n1/2. Given G (without geometric information), in polynomial time we can with high probability approximately reconstruct the hidden embedding, in the sense that “up to symmetries,” for each vertex v we find a point within distance about r of Xv; that is, we find an embedding with “displacement” at most about r. Now suppose that, instead of G we are given, for each vertex v, the ordering of the other vertices by increasing Euclidean distance from v. Then, with high probability, in polynomial time we can find an embedding with displacement (Formula presented.)., This research was supported by the grants GRAMM, TIN2017-86727-C2-1-R (J.D.), and by IDEXLYON of Université de Lyon (Programme Investissements d’Avenir, ANR16-IDEX-0005), and by LABEXMILYON (ANR-10-LABX-0070) of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007) (D.M.), Peer Reviewed, Postprint (author's final draft)

The spectrum of a graph usually provides a lot of information about its combinatorial structure. Moreover,from the spectrum, the so-called predistance polynomials can be defined, as a generalization, for any graph, of the distancepolynomials of a distance-regular graph. Going further, the preintersection numbers generalize the intersection numbers ofa distance-regular graph. This paper describes, for any graph, the closed relationships between its spectrum, predistancepolynomials, and preintersection numbers. Then, some applications to derive combinatorial properties of the given graph,most of them related to some fundamental characterizations of distance-regularity, are presented. In particular, the so-called‘spectral excess theorem’ is revisited. This result states that a connected regular graph is distance-regular if and only if itsspectral excess, which is a value computed from the spectrum, equals the average excess, that is, the mean of the numbers ofvertices at maximum distance from every vertex., Peer Reviewed, Postprint (author's final draft)

La constante de acoplamiento es el resultado de la interacción entre dos momentos magnéticos de dos átomos de una molécula. Usando métodos de vanguardia, en lo que a la mecánica cuántica se refiere, es posible calcular con precisión las constantes de acoplamiento escalar dada sólo una estructura molecular 3D como entrada. Sin embargo, estos cálculos de mecánica cuántica son extremadamente caros (conllevan días o semanas por molécula) y, por lo tanto, tienen una aplicabilidad limitada en los flujos de trabajo diarios. La propuesta en este proyecto es utilizar diferentes metodologías con redes neuronales para predecir constantes de acoplamiento. En este trabajo, se emplean técnicas tales como la Fully Connected Network (FC), Graph Convolutional Neural Network (GCN) y la Graph Attention Neural Network (GAT). De esta forma, se quiere predecir la constante de acoplamiento obteniendo distintos tipos de datos de la estructura química 3D de la molécula. Para poder llevar a cabo todas las pruebas realizadas en este trabajo, se ha utilizado la base de datos CHAMPS Scalar Coupling dataset [1] que contiene 135.000 moléculas clasificadas. Con los resultados obtenidos en este proyecto se observa que las redes de grafos obtienen mejores resultados que el baseline. Sin embargo, la metodología propuesta no consigue superar el estado del arte en la predicción de la constante de acoplamiento. Debido a que durante el desarrollo de este proyecto solo se ha contemplado el uso de enlaces dobles y J-Coupling, para simplificar y reducir la carga computacional.

The final publication is available at Springer via http://dx.doi.org/10.1007/s00026-020-00496-2, Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this paper, we consider the case where such graphs are Cayley graphs of Abelian groups. Such groups can be constructed by using a generalization to Z n of the concept of congruence in Z. Here we use this approach to present some families of mixed graphs, which, for every fixed value of the degree, have an asymptotically large number of vertices as the diameter increases. In some cases, the results obtained are shown to be optimal., Peer Reviewed, Postprint (author's final draft)

Metamaterials have become the target of many researchers due to the vast potential applications they offer, from micro antennas to invisibility cloaks. Experiments for assessing the characteristics of metamaterial designs are resource intensive. The scope of this project is to propose a series of image processing techniques and mathematical models that will allow assessing metamaterial features, reducing this way the experimental burden. As a result, we propose a series of descriptors that define the metamaterial structure. Future research is essential to validate and extend the methods described in this project., Los metamateriales están en el punto de mira de muchos proyectos de investigación por el amplio abanico de posibilidades que ofrecen, desde micro antenas hasta capas de invisibilidad. El diseño de metamateriales es un proceso que requiere de cantidades importantes de tiempo y de financiación dedicados a la evaluación experimental de sus características. El ámbito de este proyecto es el de proponer una serie de técnicas de procesado de imagen y de modelos matemáticos que permitirán la evaluación de las características del metamaterial, reduciendo así la carga experimental. Como resultado, proponemos una serie de descriptores que definan el metamaterial. La continuidad en la investigación que abarca este proyecto es esencial para validar y extender los métodos propuestos., Els metamaterials s'han posat en el punt de mira de molts projectes de recerca per l'ampli ventall de possibilitats que ofereixen, des de micro antenes fins a capes d'invisibilitat. El diseny de metamaterials és un procés que requereix de quantitats importants de temps i de finançament dedicats a l'evaluació experimental de les seves característiques. L'àmbit d'aquest projecte és el de proposar una sèrie de tècniques de processat d'imatge i de models matemàtics que permetran l'evaluació de les característiques del metamaterial, reduïnt així la càrrega experimental. Com a resultat, proposem una sèrie de descriptors que defineixin el metamaterial. La continuïtat en la recerca que abarca aquest projecte és essencial per a validar i extendre els mètodes proposats.

This is an Accepted Manuscript of an article published by Taylor & Francis Group in Journal of mathematics and music on march 2020, available online at: http://www.tandfonline.com/10.1080/17459737.2020.1726690., scales are formalized as a cyclic group of classes of projection functions related to iterations of the scale generator. Their representatives in the frequency domain are used to built cyclic sequences of tone iterates satisfying the closure condition. The refinement of cyclic sequences with regard to the best closure provides a constructive algorithm that allows to determine cyclic scales avoiding continued fractions. New proofs of the main properties are obtained as a consequence of the generating procedure. When the scale tones are generated from the two elementary factors associated with the generic widths of the step intervals we get the partition of the octave leading to the fundamental Bézout’s identity relating several characteristic scale indices. This relationship is generalized to prove a new relationship expressing the partition that the frequency ratios associated with the two sizes composing the different step-intervals induce to a specific set of octaves., Peer Reviewed, Postprint (author's final draft)

Comparing business process variants using event logs is a common use case in process mining. Existing techniques for process variant analysis detect statistically-significant differences between variants at the level of individual entities (such as process activities) and their relationships (e.g. directly-follows relations between activities). This may lead to a proliferation of differences due to the low level of granularity in which such differences are captured. This paper presents a novel approach to detect statistically-significant differences between variants at the level of entire process traces (i.e. sequences of directly-follows relations). The cornerstone of this approach is a technique to learn a directly-follows graph called mutual fingerprint from the event logs of the two variants. A mutual fingerprint is a lossless encoding of a set of traces and their duration using discrete wavelet transformation. This structure facilitates the understanding of statistical differences along the control-flow and performance dimensions. The approach has been evaluated using real-life event logs against two baselines. The results show that at a trace level, the baselines cannot always reveal the differences discovered by our approach, or can detect spurious differences., This research is partly funded by the Australian Research Council (DP180102839) and Spanish funds MINECO and FEDER (TIN2017-86727-C2-1-R)., Peer Reviewed, Postprint (author's final draft)

This thesis studies the problem of inferring topology from signal graphs. For this reason, the Master's Thesis is part of the current of thought, growing in recent years, in which the structure of the network is not assumed to be known. The problem of inferring topology is approached from two angles. The first one, studies how to find the structure of a graph from spectral templates which can be noisy. Thus, from observations of the network, the spectral template of the graph that makes up the network is inferred. In previous works, like my Degree's Thesis, the algorithms for the inference of incomplete spectral templates were studied. In this Master's thesis, we go one step further by demonstrating why the techniques studied do not always work and proposing an algorithm based on LASSO to infer the network topology when the spectral templates are noisy. The proposed algorithm is compared with those previously studied obtaining better results in terms of RMSE and reliability. The second point of view addressed in this thesis is the inference of the network from statistical techniques. It is common to find networks whose nodes have some relation. These techniques are based on, from some observations of the network, trying to find the existing relationships between the different nodes of the graph. These techniques can be used in a more generic way than those based on spectral templates. Statistical methods are studied in more depth in this Master's Thesis. Initially, the Pearson correlation coefficient is explained. After studying it, some limitations are found. Thus, a new approach is proposed based on the conditional covariance. Then, it is assumed that the signals follow a Gaussian distribution which brings us to study the Maximum Likelihood estimator while considering the graph's sparsity. Although, the previous approach was improved, we are interested in finding even a better one. Hence, we study an approach based on linear regression. In this last algorithm, we, Esta tesis estudia el problema de inferir la topología de la red a partir de las señales grafo. Por esta razón, la Tesis Final de Máster se inscribe en la corriente actual de pensamiento, creciente en los últimos años, en la que se supone no conocida la estructura de la red. El problema de la inferencia de la topología se aborda desde dos ángulos. El primero, estudia cómo encontrar la estructura de un grafo a partir de plantillas espectrales que pueden ser ruidosas o no. Así, a partir de las observaciones, se infiere la plantilla espectral del grafo que compone la red. En trabajos anteriores, como mi Tesis de Final de Grado, se estudiaron los algoritmos para la inferencia de plantillas espectrales incompletas. En esta trabajo, vamos un paso más allá demostrando por qué las técnicas estudiadas no siempre funcionan. Seguimos, proponiendo un algoritmo basado en LASSO para inferir la topología de la red cuando las plantillas espectrales son ruidosas. El algoritmo propuesto se compara con los anteriormente estudiados obteniendo mejores resultados en términos de RMSE y fiabilidad. El segundo punto de vista abordado en esta tesis es la inferencia de la red a partir de técnicas estadísticas. Es común encontrar redes cuyos nodos tienen alguna relación entre ellos. Estas técnicas se basan, a partir de algunas observaciones de la red, en tratar de encontrar las relaciones existentes entre los diferentes nodos del grafo. Estas técnicas pueden ser utilizadas de manera más genérica que las basadas en plantillas espectrales. Por ese motivo, los métodos estadísticos se estudian con más profundidad en esta Tesis de Máster. Inicialmente, se explica el coeficiente de correlación de Pearson. Después de estudiarlo, se detecta una limitación. Por ese motivo, se propone un nuevo enfoque basado en la covarianza condicional. Luego, se asume que las señales siguen una distribución Gaussiana, lo que nos lleva a estudiar el estimador de Máxima Verosimilitud, también considerando que la matriz, Aquesta tesi estudia el problema d'inferir la topologia d'una xarxa a partir dels senyals graf. Per aquesta raó, la Tesi Final de Màster s'inscriu en el corrent actual de pensament, creixent en els darrers anys, en la que se suposa no coneguda l'estructura de la xarxa. El problema d'inferència de la topologia s'aborda des de dos angles. El primer, estudia com trobar l'estructura d'un graf a partir de plantilles espectrals que poden ser sorolloses o no. Així, a partir de les observacions, s'infereix la plantilla espectral del graf que compon la xarxa. En treballs anteriors, com la meva Tesi de Final de Grau, es van estudiar els algoritmes per a la inferència de plantilles espectrals incompletes. En aquest treball, anem un pas més enllà demostrant per què les tècniques estudiades no sempre funcionen. Seguim, proposant un algoritme basat en LASSO per inferir la topologia de la xarxa quan les plantilles espectrals són sorolloses. L'algoritme proposat es compara amb els anteriorment estudiats obtenint millors resultats en termes de RMSE i fiabilitat. El segon punt de vista abordat en aquesta tesi és la inferència de la xarxa a partir de tècniques estadístiques. És comú trobar xarxes on els nodes tenen alguna relació entre ells. Aquestes tècniques es basen, a partir d'algunes observacions de la xarxa, a tractar de trobar les relacions existents entre els diferents nodes del graf. Aquestes tècniques poden ser utilitzades de manera més genèrica que les basades en plantilles espectrals. Per aquest motiu, els mètodes estadístics s'estudien amb més profunditat en aquesta Tesi de Màster. Inicialment, s'explica el coeficient de correlació de Pearson. Després d'estudiar-lo, es detecta una limitació. Per aquest motiu, es proposa un nou enfocament basat en la covariància condicional. Després, s'assumeix que els senyals segueixen una distribució Gaussiana, el que ens porta a estudiar l'estimador de Màxima Versemblança, també considerant que la matriu solució és dispersa. Encara que

We develop splitting techniques to study the Lyubeznik numbers of cover ideals of graphs which allow us to describe them for large families of graphs including forests, cycles, wheels and cactus graphs. More generally, we are able to compute all the Bass numbers and the shape of the injective resolution of local cohomology modules by considering the connected components of all the induced subgraphs. Indeed, our method gives us a very simple criterion for the vanishing of these local cohomology modules in terms of the number of connected components of the induced subgraphs., Peer Reviewed, Postprint (author's final draft)