Search

This is a post-peer-review, pre-copyedit version of an article published in Journal of algebraic combinatorics. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10801-021-01049-3 We describe, in a very explicit way, a method for determining the spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not). The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. The research of C. Dalf´o and M. A. Fiol 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. The research of C. Dalf´o has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The authors S. Pavl´ıkov´a and J. Sir´aˇn acknowledge support from the ˇ APVV Research Grants 15-0220 and 17-0428, and the VEGA Research Grants 1/0142/17 and 1/0238/19.

Let S be a set of n points in general position in the plane, and let $$X_{k,\ell }(S)$$ X k , ℓ ( S ) be the number of convex k-gons with vertices in S that have exactly $$\ell $$ ℓ points of S in their interior. We prove several equalities for the numbers $$X_{k,\ell }(S)$$ X k , ℓ ( S ) . This problem is related to the Erdős–Szekeres theorem. Some of the obtained equations also extend known equations for the numbers of empty convex polygons to polygons with interior points. Analogous results for higher dimension are shown as well.

We obtain a new family of digraphs with minimal diameter, that is, given the number of vertices and out-degree, there is no other digraph with a smaller diameter. This new family of digraphs are called `modified cyclic digraphs' $MCK(d,\ell)$, and it is derived from the Kautz digraphs $K(d,\ell)$ and from the so-called cyclic Kautz digraphs $CK(d,\ell)$. The cyclic Kautz digraphs $CK(d,\ell)$ were defined as the digraphs whose vertices are labeled by all possible sequences $a_1\ldots a_\ell$ of length $\ell$, such that each character $a_i$ is chosen from an alphabet of $d+1$ distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and also requiring that $a_1\neq a_\ell$. Their arcs are between vertices $a_1 a_2\ldots a_\ell$ and $a_2 \ldots a_\ell a_{\ell+1}$, with $a_1\neq a_\ell$ and $a_2\neq a_{\ell+1}$. Since $CK(d,\ell)$ do not have minimal diameter for their number of vertices, we construct the modified cyclic Kautz digraphs to obtain the same diameter as in the Kautz digraphs, and we also show that $MCK(d,\ell)$ are $d$-out-regular. Moreover, for $t\geq1$, we compute the number of vertices of the iterated line digraphs $L^t(CK(d,\ell))$., Contributions to Discrete Mathematics, Vol. 16 No. 3 (2021)

Let U be a ( k − 1 2 − 1 ) -dimensional subspace of quadratic forms defined on F k with the property that U does not contain any reducible quadratic form. Let V ( U ) be the points of PG ( k − 1 , F ) which are zeros of all quadratic forms in U . We will prove that if there is a group G which fixes U and no line of PG ( k − 1 , F ) and V ( U ) spans PG ( k − 1 , F ) then any hyperplane of PG ( k − 1 , F ) is incident with at most k points of V ( U ) . If F is a finite field then the linear code generated by the matrix whose columns are the points of V ( U ) is a k -dimensional linear code of length | V ( U ) | and minimum distance at least | V ( U ) | − k . A linear code with these parameters is an MDS code or an almost MDS code. We will construct examples of such subspaces U and groups G , which include the normal rational curve, the elliptic curve, Glynn’s arc from Glynn (1986) and other examples found by computer search. We conjecture that the projection of V ( U ) from any k − 4 points is contained in the intersection of two quadrics, the common zeros of two linearly independent quadratic forms. This would be a strengthening of a classical theorem of Fano, which itself is an extension of a theorem of Castelnuovo, for which we include a proof using only linear algebra.

We use production matrices to count several classes of geometric graphs. We present novel production matrices for non-crossing partitions, connected geometric graphs, and k-angulations, which provide another, simple and elegant, way of counting the number of such objects. Counting geometric graphs is then equivalent to calculating the powers of a production matrix. Applying the technique of Riordan Arrays to these production matrices, we establish new formulas for the numbers of geometric graphs as well as combinatorial identities derived from the production matrices. Further, we obtain the characteristic polynomial and the eigenvectors of such production matrices. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922. This research is also supported by PID2019-104129GB-I00/MCIN/AEI/10.13039/501100011033. C. H. and R. I. S. were supported by MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1336 and 2017SGR1640. G. E. is also funded by an FPU of the Universidad de Alcalá.

In this paper we consider a subdivision of a given network and we show how the group inverse matrix of the normalized laplacian of the subdivision network is related to the group inverse matrix of the normalized laplacian of the initial given network. Our approach establishes a relationship between solutions of related Poisson problems on both structures and takes advantage on the properties of the group inverse matrix. As a consequence we get formulae for effective resistances and the Kirchhoff Index of the subdivision network expressed in terms of its corresponding in the base network. Finally, we study two examples where the base network are the star and the wheel, respectively.

For any $r$-graph $H$, we consider the problem of finding a rainbow $H$-factor in an $r$-graph $G$ with large minimum $\ell$-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., Comment: 10 pages

Segre's lemma of tangents dates back to the 1950's when he used it in the proof of his “arc is a conic” theorem. Since then it has been used as a tool to prove results about various objects including internal nuclei, Kakeya sets, sets with few odd secants and further results on arcs. Here, we survey some of these results and report on how re-formulations of Segre's lemma of tangents are leading to new results.

We study the existence of rainbow perfect matching and rainbow Hamiltonian cycles in edge–colored graphs where every color appears a bounded number of times. We derive asymptotically tight bounds on the minimum degree of the host graph for the existence of such rainbow spanning structures. The proof uses a probabilisitic argument combined with switching techniques.

© 2019. 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 matchings with diametral disks between two sets of points R and B. More precisely, for each pair of matched points p ¿ R and q ¿ B, we consider the disk through p and q with the smallest diameter. We prove that for any R and B such that |R| = |B|, there exists a perfect matching such that the diametral disks of the matched point pairs have a common intersection. In fact, our result is stronger, and shows that a maximum weight perfect matching has this property.

Let Δ = { δ 1 , δ 2 , … , δ m } be a finite set of 2-connected patterns, i.e. graphs up to vertex relabelling. We study the generating function D Δ ( z , u 1 , u 2 , … , u m ) , which counts polygon dissections and marks subgraph copies of δ i with the variable u i . We prove that this is always algebraic, through an explicit combinatorial decomposition depending on Δ . The decomposition also gives a defining system for D Δ ( z , 0 ) , which encodes polygon dissections that avoid these patterns as subgraphs. In this way, we are able to extract normal limit laws for the patterns when they are encoded, and perform asymptotic enumeration of the resulting classes when they are avoided. The results can be transferred to the case of labelled outerplanar graphs. We give examples and compute the relevant constants when the patterns are small cycles or dissections.

Kautz digraphs K(d, l) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related with these, the cyclic Kautz digraphs CK(d, l) were recently introduced by Böhmová, Huemer and the author, and some of its distance-related parameters were fixed. In this paper we propose a new approach to cyclic Kautz digraphs by introducing the family of subKautz digraphs sK(d, l), from where the cyclic Kautz digraphs can be obtained as line digraphs. This allows us to give exact formulas for the distance between any two vertices of both sK(d, l) and CK(d, l). Moreover, we compute the diameter and the semigirth of both families, also providing efficient routing algorithms to find the shortest path between any pair of vertices. Using these parameters, we also prove that sK(d, l) and CK(d, l) are maximally vertex-connected and super-edge-connected. Whereas K(d, `) are optimal with respect to the diameter, we show that sK(d, l) and CK(d, l) are optimal with respect to the mean distance, whose exact values are given for both families when l = 3. Finally, we provide a lower bound on the girth of CK(d, l and sK(d, l). This research is supported by MINECO under project MTM2014-60127-P, and the Catalan Research Council under project 2014SGR1147. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.

During cardiac diseases many types of anatomical and functional remodeling of cardiac tissue can occur. In this work, we focus on two conditions: hypoxia and fibrosis, which are part of complex pathological modifications that take place in many cardiac diseases (hypertrophic cardiomyopathy, hypertensive heart disease, and recurrent myocardial infarction) and respiratory diseases (obstructive pulmonary disease, obstructive sleep apnea, and cystic fibrosis). Using computational models of cardiac electrophysiology, we evaluate if the interplay between hypoxia and fibrosis is sufficient to trigger cardiac arrhythmia. We study the mechanisms behind the generation of ectopic beats, an arrhythmic trigger also known as premature ventricular contractions (PVCs), in regions with high hypoxia and fibrosis. First, we modify an electrophysiological model of myocytes of the human left ventricle to include the effects of hypoxia. Second, diffuse fibrosis is modeled by randomly replacing cardiac myocytes by non-excitable and non-conducting cells. The Monte Carlo method is used to evaluate the probability of a region to generate ectopic beats with respect to different levels of hypoxia and fibrosis. In addition, we evaluate the minimum size of three-dimensional slabs needed to sustain reentries for different stimulation protocols. The observed mechanism behind the initiation of ectopic beats is unidirectional block, giving rise to sustained micro-reentries inside the region with diffuse fibrosis and hypoxia. In summary, our results suggest that hypoxia and fibrosis are sufficient for the creation of a focal region in the heart that generates PVCs. We acknowledge support from CAPES by the grant 88881.065002/2014-01 of the Brazilian program Science without borders, and from MINECO of Spain under the Ramon y Cajal program with the grant number RYC-2012-11265

Let q >= 2 be a prime power. In this note we present an alternate description of the known (q + 1; 8)-cages which has allowed us to construct small (k; g)–graphs for k =q, q-1, and g = 7; 8 in other papers on this same topic.

We study the class L of link types that admit a K4-minor-free diagram, i.e., they can be projected on the plane so that the resulting graph does not contain any subdivision of K4. We prove that L is the closure of a subclass of torus links under the operation of connected sum. Using this structural result, we enumerate L and subclasses of it, with respect to the minimal number of crossings or edges in a projection of L ∈ L . Further, we enumerate (both exactly and asymptotically) all connected K4-minor-free link diagrams, all minimal connected K4-minor-free link diagrams, and all K4-minor-free diagrams of the unknot.

Gallian's survey shows that there is a big variety of labelings of graphs. By means of (di)graphs products we can establish strong relations among some of them. Moreover, due to the freedom of one of the factors, we can also obtain enumerative results that provide lower bounds on the number of nonisomorphic labelings of a particular type. In this paper, we will focus in three of the (di)graphs products that have been used in these duties: the ⊗h-product of digraphs, the weak tensor product of graphs and the weak ⊗h-product of graphs. Reseach supported by the Spanish Government under project MTM2014-60127-P and symbolically by the Catalan Research Council under grant 2014SGR1147.

This paper aims to study a family of distances in networks associated with effective resistances. Specifically, we consider the effective resistance distance with respect to a positive parameter and a weight on the vertex set; that is, the effective resistance distance associated with an irreducible and symmetric M-matrix whose lowest eigenvalue is the parameter and the weight function is the associated eigenfunction. The main idea is to consider the network embedded in a host network with additional edges whose conductances are given in terms of the mentioned parameter. The novelty of these distances is that they take into account not only the influence of shortest and longest weighted paths but also the importance of the vertices. Finally, we prove that the adjusted forest metric introduced by P. Chebotarev and E. Shamis is nothing else but a distance associated with a Schr?dinger operator with constant weight.

We consider a variant of a question of Erdos on the number of empty k-gons (k-holes) in a set of n points in the plane, where we allow the k-gons to be non-convex. We show bounds and structural results on maximizing and minimizing the number of general 4-holes, and maximizing the number of non-convex 4-holes. In particular, we show that for n >= 9, the maximum number of general 4-holes is ((pi)(4)); the minimum number of general 4-holes is at least 5/2 n(2) - circle minus(n); and the maximum number of non-convex 4-holes is at least 1/2 n(3) - circle minus(n(2) logn) and at most 1/2 n(3) - circle minus(n(2)). 2014 (c) Elsevier B.V. All rights reserved.

In this paper we find an exact analytical expression for the number of spanning trees in Apollonian networks. This parameter can be related to significant topological and dynamic properties of the networks, including percolation, epidemic spreading, synchronization, and random walks. As Apollonian networks constitute an interesting family of maximal planar graphs which are simultaneously small-world, scale-free, Euclidean and space filling and highly clustered, the study of their spanning trees is of particular relevance. Our results allow also the calculation of the spanning tree entropy of Apollonian networks, which then we compare with those of other graphs with the same average degree., Manuscript accepted for publication (Discrete Applied Mathematics)

Let q >= 2 be a prime power. In this note we present an alternate description of the known (q + 1; 8)-cages which has allowed us to construct small (k; g)–graphs for k =q, q-1, and g = 7; 8 in other papers on this same topic.

Let ℱ be a family of graphs and letdbe large enough. For everyd-regular graphG, we study the existence of a spanning ℱ-free subgraph ofGwith large minimum degree. This problem is well understood if ℱ does not contain bipartite graphs. Here we provide asymptotically tight results for many families of bipartite graphs such as cycles or complete bipartite graphs. To prove these results, we study a locally injective analogue of the question.

We present a robust and compact meta-module for edge-hinged modular robot units such as M-TRAN, SuperBot, SMORES, UBot, PolyBot and CKBot, as well as for central-point-hinged ones such as Molecubes and Roombots. Thanks to the rotational degrees of freedom of these units, the novel meta-module is able to expand and contract, as to double/halve its length in each dimension. Moreover, for a large class of edge-hinged robots the proposed meta-module also performs the scrunch/relax and transfer operations required by any tunneling-based reconfiguration strategy, such as those designed for Crystalline and Telecube robots. These results make it possible to apply efficient geometric reconfiguration algorithms to this type of robots. We prove the size of this new meta-module to be optimal. Its robustness and performance substantially improve over previous results.

In this note we present a general approach to construct large digraphs from small ones. These are called expanded digraphs, and, as particular cases, we show their close relationship between voltage digraphs and line digraphs, which are two known approaches to obtain dense digraphs. In the same context, we show the equivalence between the vertex-splitting and partial line digraph techniques. Then, we give a sufficient condition for a lifted digraph of a base line digraph to be again a line digraph. Some of the results are illustrated with two well-known families of digraphs. Namely, De Bruijn and Kautz digraphs.

Our aim is to characterize those matrices that are the response matrix of a semi-positive definite Schr?dinger operator on a circular planar network. Our findings generalize the known results and allow us to consider both nonsingular and non diagonally dominant matrices as response matrices. To this end, we define the Dirichlet-to-Robin map associated with a Schr?dinger operator on general networks, and we prove that it satisfies the alternating property which is essential to characterize the response matrices.

A prominent problem in Graph Theory is to find extremal graphs or digraphs with restrictions in their diameter, degree and number of vertices. Here we obtain a new family of digraphs with minimal diameter, that is, given the number of vertices and out-degree there is no other digraph with a smaller diameter. This new family is called modified cyclic digraphs MCK(d, `) and it is derived from the Kautz digraphs K(d, `). It is well-known that the Kautz digraphs K(d, `) have the smallest diameter among all digraphs with their number of vertices and degree. We define the cyclic Kautz digraphs CK(d, `), whose vertices are labeled by all possible sequences a1 . . . a` of length `, such that each character ai is chosen from an alphabet containing d + 1 distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and now also requiring that a1 6= a`. The cyclic Kautz digraphs CK(d, `) have arcs between vertices a1a2 . . . a` and a2 . . . a`a`+1, with a1 6= a` and a2 6= a`+1. Unlike in Kautz digraphs K(d, `), any label of a vertex of CK(d, `) can be cyclically shifted to form again a label of a vertex of CK(d, `). We give the main parameters of CK(d, `): number of vertices, number of arcs, and diameter. Moreover, we construct the modified cyclic Kautz digraphs MCK(d, `) to obtain the same diameter as in the Kautz digraphs, and we show that MCK(d, `) are d-out-regular. Finally, we compute the number of vertices of the iterated line digraphs of CK(d, `).

One important result in secret sharing is the Brickell-Davenport Theorem: every ideal perfect secret sharing scheme de nes a matroid that is uniquely determined by the access structure. Even though a few attempts have been made, there is no satisfactory de nition of ideal secret sharing scheme for the general case, in which non-perfect schemes are considered as well. Without providing another unsatisfactory de nition of ideal non-perfect secret sharing scheme, we present a generalization of the Brickell-Davenport Theorem to the general case. After analyzing that result under a new point of view and identifying its combinatorial nature, we present a characterization of the (not necessarily perfect) secret sharing schemes that are associated to matroids. Some optimality properties of such schemes are discussed.

This paper presents a distributed, streaming graph parti- tioner, Graph Streaming Partitioner (GraSP), which makes partition decisions as each vertex is read from memory, sim- ulating an online algorithm that must process nodes as they arrive. GraSP is a lightweight high-performance comput- ing (HPC) library implemented in MPI, designed to be easily substituted for existing HPC partitioners such as ParMETIS. It is the rst MPI implementation for streaming partition- ing of which we are aware, and is empirically orders-of- magnitude faster than existing partitioners while providing comparable partitioning quality. We demonstrate the scala- bility of GraSP on up to 1024 compute nodes of NERSC's Edison supercomputer. Given a minute of run-time, GraSP can partition a graph three orders of magnitude larger than ParMETIS can.

Technology mapping is the task to transform a technology independent logic network into a mapped network using gates from a library, optimizing some objective function such total area, delay or power consumption. As stated, the problem is completely intractable. Therefore, different techniques are applied to solve the problem, such as using different simplified representations. The usual approach consists of using a fixed library, typically partially handmade. Designing such libraries is a costly process, specially because of the lack of good automatic techniques to perform it. This is the main motivation for this work and the goal is to move from fixed-library technology mapping to library-free technology mapping. This thesis presents different algorithms and techniques to move to library-free technology mapping for area and for delay optimization

An arc colored eulerian multidigraph with $l$ colors is rainbow eulerian if there is an eulerian circuit in which a sequence of $l$ colors repeats. The digraph product that refers the title was introduced by Figueroa-Centeno et al. as follows: let $D$ be a digraph and let $\Gamma$ be a family of digraphs such that $V(F)=V$ for every $F\in \Gamma$. Consider any function $h:E(D)\longrightarrow\Gamma $. Then the product $D\otimes_{h} \Gamma$ is the digraph with vertex set $V(D)\times V$ and $((a,x),(b,y))\in E(D\otimes_{h}\Gamma)$ if and only if $ (a,b)\in E(D)$ and $ (x,y)\in E(h (a,b))$. In this paper we use rainbow eulerian multidigraphs and permutations as a way to characterize the $\otimes_h$-product of oriented cycles. We study the behavior of the $\otimes_h$-product when applied to digraphs with unicyclic components. The results obtained allow us to get edge-magic labelings of graphs formed by the union of unicyclic components and with different magic sums., Comment: 12 pages, 5 figures

Let GG be a graph and let kk and jj be positive integers. A subset DD of the vertex set of GG is a kk-dominating set if every vertex not in DD has at least kk neighbors in DD. The kk-domination numberγk(G)γk(G) is the cardinality of a smallest kk-dominating set of GG. A subset I⊆V(G)I⊆V(G) is a jj-independent set of GG if every vertex in II has at most j−1j−1 neighbors in II. The jj-independence numberαj(G)αj(G) is the cardinality of a largest jj-independent set of GG. In this work, we study the interaction between γk(G)γk(G) and αj(G)αj(G) in a graph GG. Hereby, we generalize some known inequalities concerning these parameters and put into relation different known and new bounds on kk-domination and jj-independence. Finally, we will discuss several consequences that follow from the given relations, while always highlighting the symmetry that exists between these two graph invariants.

We study the existence of perfect matchings in suitably chosen induced subgraphs of random biregular bipartite graphs. We prove a result similar to a classical theorem of Erdös and Rényi about perfect matchings in random bipartite graphs. We also present an application to commutative graphs, a class of graphs that are featured in additive number theory.

International audience; A p-adaptive Hybridizable Discontinuous Galerkin method for the solution of wave problems is presented in a challenging engineering problem. Moreover, its performance is compared with a high-order continuous Galerkin. The hybridization technique allows to reduce the coupled degrees of freedom to only those on the mesh element boundaries, while the particular choice of the numerical fluxes opens the path to a super-convergent post-processed solution. This super-convergent post-processed solution is used to construct a simple and inexpensive error estimator. The error estimator is employed to obtain solutions with the prescribed accuracy in the area (or areas) of interest and also drives a proposed iterative mesh adaptation procedure. The proposed method is applied to a non-homogeneous scattering problem in an unbounded domain. This is a challenging problem because, on one hand, for high frequencies numerical difficulties are an important issue due to the loss of the ellipticity and the oscillatory behavior of the solution. And on the other hand, it is applied to real harbor agitation problems. That is, the Mild Slope equation in frequency domain (Helmholtz equation with non-constant coefficients) is solved on real geometries with the corresponding perfectly matched layer to damp the diffracted waves. The performance of the method is studied on two practical examples. The adaptive Hybridizable Discontinuous Galerkin method exhibits better efficiency compared to a high-order continuous Galerkin method using static condensation of the interior nodes.

The aim of this contribution is to pr esent teaching material elaborated to work with a very simple discrete model, the cellular automata called “Voting” (free access from the social science section of NetLogo library), and its use in the classroom.

This paper deals with the question of completing a monotone increasing family of subsets to obtain the dependent sets of a matroid. More precisely, we provide several natural ways of transforming the clutter of the inclusion minimal subsets of the family into the set of circuits of a matroid.

Let $S$ be a $k$-colored (finite) set of $n$ points in $\mathbb{R}^d$, $d\geq 3$, in general position, that is, no {$(d + 1)$} points of $S$ lie in a common $(d - 1)$}-dimensional hyperplane. We count the number of empty monochromatic $d$-simplices determined by $S$, that is, simplices which have only points from one color class of $S$ as vertices and no points of $S$ in their interior. For $3 \leq k \leq d$ we provide a lower bound of $\Omega(n^{d-k+1+2^{-d}})$ and strengthen this to $\Omega(n^{d-2/3})$ for $k=2$. On the way we provide various results on triangulations of point sets in $\mathbb{R}^d$. In particular, for any constant dimension $d\geq3$, we prove that every set of $n$ points ($n$ sufficiently large), in general position in $\mathbb{R}^d$, admits a triangulation with at least $dn+\Omega(\log n)$ simplices.

Let $G$ be a connected graph with vertex set $V$ and a {\em weight function} $\rho$ that assigns a nonnegative number to each of its vertices. Then, the {\em $\rho$-moment} of $G$ at vertex $u$ is defined to be $M_G^{\rho}(u)=\sum_{v\in V} \rho(v)\dist (u,v) $, where $\dist(\cdot,\cdot)$ stands for the distance function. Adding up all these numbers, we obtain the {\em $\rho$-moment of $G$}: $$ M_G^{\rho}=\sum_{u\in V}M_G^{\rho}(u)=1/2\sum_{u,v\in V}\dist(u,v)[\rho(u)+\rho(v)]. $$ This parameter generalizes, or it is closely related to, some well-known graph invariants, such as the {\em Wiener index} $W(G)$, when $\rho(u)=1/2$ for every $u\in V$, and the {\em degree distance} $D'(G)$, obtained when $\rho(u)=\delta(u)$, the degree of vertex $u$. In this paper we derive some exact formulas for computing the $\rho$-moment of a graph obtained by a general operation called graft product, which can be seen as a generalization of the hierarchical product, in terms of the corresponding $\rho$-moments of its factors. As a consequence, we provide a method for obtaining nonisomorphic graphs with the same $\rho$-moment for every $\rho$ (and hence with equal mean distance, Wiener index, degree distance, etc.). In the case when the factors are trees and/or cycles, techniques from linear algebra allow us to give formulas for the degree distance of their product.

A la hora de poder aplicar algoritmos te oricos a casos reales, no solo resulta conveniente que el algoritmo sea e ciente sino tambi en que sea lo m as comprensible posible y que no requiera de comple- jos procesos de parametrizaci on. Siguiendo esta l ogi- ca, proponemos aqu un algoritmo h brido que reune las caracter sticas anteriores para resolver el proble- ma del Flow-Shop (FSP). El algoritmo, que no re- quire de parametrizaci on alguna, combina estrategias de randomizaci on con una B usqueda Local Iterativa (ILS), logrando ser competitivo con otros conocidos algoritmos que se encuentran entre los m as simples y e cientes para el FSP. Nuestro enfoque de ne (1) un nuevo operador para el proceso de perturbaci on ILS, (2) un nuevo criterio de aceptaci on basado en reglas simples y transparentes, y (3) un proceso de random- izaci on sesgada de la soluci on inicial. Los resultados preliminares obtenidos con las instancias de Taillard permiten concluir que la soluci on propuesta puede ser una excelente alternativa en aplicaciones reales

L'objectiu d'aquest treball és estudiar la relació que hi ha entre el Teorema dels Quatre Colors i els grups de Thompson. Principalment, es construeix el procés que permet passar d'un mapa a un (o més) elements del grup F, i com a partir d'un element del grup en podem obtenir un mapa. També es veu en quin sentit això permet definir una equivalència en el sentit de les coloracions. Després, usant aquesta equivalència que s'ha construït, es realitzen alguns intents de demostració que malgrat no funcionar, ajuden a entendre aquesta relació i a entendre el Grup de Thompson. S'estudia per quin motiu aquests intents fracassen, i es veuen possibles vies que resten obertes en aquest sentit. . Els elements del grup de Thompson es poden representar amb arbres binaris. Per altra banda, per un famós teorema de Tait de 1880, el teorema dels quatre colors és equivalent a demostrar que tot graf cúbic i planar és 3-aresta-colorable. Els arbres binaris dels elements del grup de Thompson presenten estructura de graf cúbic planar, i per tant poden ser susceptibles de ser utilitzats per estudiar el teorema dels quatre colors. L'objectiu d'aquest treball és entendre la relació que hi pugui haver entre el teorema dels quatre colors, el teorema de Tait i el grup de Thompson. Entendre bé i exposar l'equivalència entre els dos teoremes, i la seva reescriptura, si s'escau, en termes del grup. Òptimament, es tractaria de trobar una demostració alternativa del teorema dels quatre colors mitjançant el grup de Thompson, però si això no és possible, serà suficient entendre la situació i plantejar les dificultats que presenta aquesta via d'aproximació al teorema dels quatre colors.

This paper discusses the convenience of predicting, quantitatively, time-dependent reliability and availability levels asso-ciated with most building or civil engineering structures. Then, the paper reviews different approaches to these problems and proposes the use of discrete-event simulation as the most realistic way to deal with them, specially during the design stage. The paper also reviews previous work on the use of both Monte Carlo simulation and discrete-event simulation in this area and shows how discrete-event simulation, in particular, could be employed to solve uncertainty in time-dependent structural reliability problems. Finally, a case study is developed to illustrate some of the concepts previously covered in the paper.

Presentamos el algoritmo OCA para buscar comunidades solapadas en grafos grandes, como por ejemplo la Wikipedia con 1,6×107 nodos y 1,8×108 aristas. OCA se basa en la búsqueda iterativa de subconjuntos localmente óptimos para una función objetivo, representando los subconjuntos como vectores suma de una configuración virtual de vectores. Analizamos el comportamiento de dos funciones objetivo, la Laplaciana asociada a la longitud del vector suma, y la conductividad.

We aim here at obtaining bounds on the first non-null eigenvalue for self-adjoint boundary value problems on a weighted network by means of equilibrium measures, that includes the study of Dirichlet, Neumann and Mixed problems. We also show the sharpness of these bounds throughout the analysis of some known examples. In particular, we emphasize the case of distance-regular graphs, and we show that the bounds obtained are better than the known until now.

In this work we study the different types of regular boundary value problems on a path associated with the Schrödinger operator. In particular, we obtain the Green function for each problem and we emphasize the case of Sturm-Liouville boundary conditions. In addition, we study the periodic boundary value problem that corresponds to the Poisson equation in a cycle. In any case, the Green functions are given in terms of Chebyshev polynomials since they verify a recurrence law similar to the one verified by the Schrödinger operator on a path.

El método de los elementos discretos es una técnica numérica que permite la modelización de sólidos como una colección de partículas o elementos de distintas formas (discos, polígonos, esferas, poliedros) en dos y tres dimensiones. En contraposición con los métodos tradicionales basados en teorías del continuo (el método de los elementos finitos o de las diferencias finitas) el método de los elementos discretos presenta la clara ventaja de poder simular la rotura frágil y dúctil del material a un mismo tiempo. Esto ocurre como una consecuencia directa de la separación y deslizamiento entre partículas a escala microscópica. En general, en el método de los elementos discretos se especifican las propiedades a escala micro de las partículas y de los contactos entre partículas (rigideces y resistencias del contacto, coeficiente de fricción entre partículas, densidad, etc). A su vez, a escala macro el material se describe por sus constantes elásticas y la resistencia última a tracción y compresión, así como otros parámetros que no se tendrán en cuenta en este estudio. Dado que no existe una teoría completa para predecir las propiedades macroscópicas a partir de los parámetros micro y viceversa, el estudio de la relación entre los parámetros micro y las propiedades del material se convierte en un prerequisito para poder modelar mediante el método de los elementos discretos cualquier problema de ingeniería.

Aquesta obra presenta una col.lecció de problemes resolts corresponents als continguts i les assignatures de matemática discreta dels estudis d'informàtica, específicament per a la FIB de la UPC, i cobreix dues grans àrees d'interès per a aquests estudis: la teoria de grafs i la combinatòria. Està orientada específicament a l'alumnat i amb aquesta finalitat ofereix, d'una banda, solucions detallades d'un gran nombre d'exercicis i, d'altra banda, proporciona idees, tècniques i mètodes amb l'objectiu d'ensenyar a resoldre problemes de matemàtica discreta.

La matemàtica discreta és la part de les matemàtiques que tracta de les estructures finites i numerables. Aquesta nova branca de les matemàtiques ha rebut un impuls decisiu amb els progressos de la informàtica i de les tècniques de computació. Les línies bàsiques de les quals s'ocupa són les tècniques de numeració, les estructures combinatòries, la teoria de grafs i les estructures algebraiques. Així mateix, l'algorítmica és una eina imprescindible per a la construcció de solucions en els problemes que es tracten. Aquest llibre pretén presentar un visió concisa i completa de tots aquests temes.

Comunicació presentada a: ASIACRYPT 2016, celebrat a Hanoi, Vietnam, del 4 al 6 de desembre de 2016. We put forward a new family of computational assumptions, the Kernel Matrix Diffi-Hellman Assumption. Given some matrix A sampled from some distribution D, the kernel assumption says that it is hard to find \in the exponent" a nonzero vector in the kernel of A>. This family is a natural computational analogue of the Matrix Decisional Diffie-Hellman Assumption (MDDH), proposed by Escala et al. As such it allows to extend the advantages of their algebraic framework to com- putational assumptions. The k-Decisional Linear Assumption is an example of a family of de- cisional assumptions of strictly increasing hardness when k grows. We show that for any such family of MDDH assumptions, the corresponding Kernel assumptions are also strictly increasingly weaker. This requires ruling out the existence of some black-box reductions between exible problems (i.e., computational problems with a non unique solution).

In a witness rectangle graph (WRG) on vertex point set P with respect to witness points set W in the plane, two points x, y in P are adjacent whenever the open isothetic rectangle with x and y as opposite corners contains at least one point in W. WRGs are representative of a a larger family of witness proximity graphs introduced in two previous papers. We study graph-theoretic properties of WRGs. We prove that any WRG has at most two non-trivial connected components. We bound the diameter of the non-trivial connected components of a WRG in both the one-component and two-component cases. In the latter case, we prove that a graph is representable as a WRG if and only if each component is a connected co-interval graph, thereby providing a complete characterization of WRGs of this type. We also completely characterize trees drawable as WRGs. In addition, we prove that a WRG with no isolated vertices has domination number at most four. Moreover, we show that any combinatorial graph can be drawn as a WRG using a combination of positive and negative witnesses. Finally we conclude with some related results on the number of points required to stab all the rectangles defined by a set of n point., In Proceedings of the 12th International Symposium on Algorithms and Data Structures (WADS), p.73-85, August 2011, New York, NY, USA

Utilizando técnicas relacionadas con la resolución de problemas de contorno para ecuaciones en diferencias de segundo orden, se dan condiciones necesarias y suficientes cientes para la invertibilidad de matrices circulantes que dependen de tres parámetros. En los casos que existe, se da la expresión de los coeficientes de la matriz inversa reduciendo significativamente el coste computacional. Como aplicación, se obtiene la matriz inversa de circulantes cuyos coeficientes son progresiones aritméticas o geométricas entre otros. Se obtiene también, la matriz inversa de una matriz tridiagonal circulante sin necesidad de suponer la hipótesis de dominancia diagonal

We aim here at analyzing self-adjoint boundary value problems on finite networks associated with positive semi-definite Schrödinger operators. In addition, we study the existence and uniqueness of solutions and its variational formulation. Moreover, we will tackle a well-known problem in the framework of Potential Theory, the so-called condenser principle. Then, we generalize of the concept of effective resistance between two vertices of the network and we characterize the Green function of some BVP in terms of effective resistances.

© 2018. 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 [7] Monod introduced examples of groups of piecewise projective homeomorphisms which are not amenable and which do not contain free subgroups, and in [6] Lodha and Moore introduced examples of finitely presented groups with the same property. In this article we examine the normal subgroup structure of these groups. Two important cases of our results are the groups H and . We show that the group H of piecewise projective homeomorphisms of has the property that is simple and that every proper quotient of H is metabelian. We establish simplicity of the commutator subgroup of the group , which admits a presentation with 3 generators and 9 relations. Further, we show that every proper quotient of is abelian. It follows that the normal subgroups of these groups are in bijective correspondence with those of the abelian (or metabelian) quotient.