Un digrafo o grafo dirigido se dice que es k-arco transitivo si tiene grupo de automorfismos que actúa transitivamente en el conjunto de k-arcos. Para un entero positivo k, un k-arco de un digrafo es una secuencia (x0,x1,.,xk) de k+1 vértices del digrafo tal que para cada i=0,.,k, (xi,xi+1) es un arco del digrafo. Los digrafos de esta clase tienen una alta simetría y por lo tanto pueden ser útiles como modelos de transmisión y de difusión de la información. Uno de los problemas de que nos ocupamos en esta Tesis es la modelización de topologías de redes de interconexión altamente simétricas mediante digrafos k-arco transitivos. Así, una primera parte de la tesis se dedica precisamente a la construcción de digrafos k-arco transitivos, que es una de las principales contribuciones de la tesis. La forma en que se estructura esta memoria es la siguiente:En los primeros Capítulos incluimos la notación y terminología básica de digrafos que utilizaremos a lo largo de la Tesis, así como un estado del arte de otras construcciones de digrafos k-arco transitivos conocidas hasta la fecha. Introducimos también las herramientas claves para nuestra construcción de digrafos k-arco transitivos como son las 1-factorizaciones y los recubrimientos de digrafos. En particular, definimos los recubrimientos de Cayley de digrafos arco-coloreados.En el Capítulo 3 presentamos nuestra construcción de digrafos k-arco transitivos, que es también una técnica de construcción de recubrimientos k-arco transitivos de digrafos conexos regulares arbitrarios para cada entero positivo k. Como técnica de contrucción de recubrimientos k-arco transitivos, generaliza los resultados de Babai de 1985 para los casos k=0,1. La idea de la construcción consiste en escoger recubrimientos vértice transitivos "apropiados" del digrafo línea k-línea iterado del digrafo de partida, de manera que estos recubrimientos sean también digrafos k-línea iterados. Además, los digrafos k-arco transitivos de los que son k-línea iterados resultan ser además recubrimientos del digrafo de partida. Los recubrimientos "apropiados" de los digrafos k-línea iterados son recubrimientos de Cayley de los digrafos con 1-factorizaciones k-uniformes. Previamente, definimos las 1-factorizaciones k-uniformes de digrafos k-línea iterados y probamos que todo digrafo k-línea iterado admite 1-factorizaciones de este tipo. En el Capítulo 4 introducimos el concepto de cuadrado latino uniforme y damos una caracterización de las 1-factorizaciones 1-uniformes de digrafos línea en términos de cuadrados latinos uniformes. En particular, obtenemos el número de 1-factorizaciones 1-uniformes de un digrafo línea en función del número de cuadrados latinos uniformes de manera constructiva. Se demuestra también que los cuadrados latinos uniformes son isomorfos al cuadrado latino de la tabla de composición de un grupo del mismo orden. Como consecuencia, calculamos explicítamente los cuadrados latinos uniformes de orden pequeño y obtenemos las 1-factorizaciones 1-uniformes de digrafos línea de grado pequeño de algunas familias de digrafos. La última parte del capítulo la dedicamos a la representación de grupos de permutaciones que actúan regularmente en el conjunto de arcos de un digrafo. En el Capítulo 5 estudiamos el grupo de automorfismos de los recubrimientos k-arco transitivos que obtenemos con nuestra técnica. Se dan resultados interesantes en términos de la normalidad para los recubrimientos de Cayley de grado dos. Por último en este capítulo, estudiamos la estructura del grupo de automorfismos de los digrafos k-arco transitivos que son homeomorfos a un ciclo y en particular, vemos que un digrafo de Cayley es homeomorfo a un ciclo si y sólo si existe un subgrupo normal del grupo base tal que los generadores están contenidos en una de las clases laterales del subgrupo. / A digraph or directed graph is said k-arc transitive if it has automorphism group that acts transitively on the set of k-arcs. For a positive integer k, a k-arc of a digraph is a sequence (x0,x1,.,xk) of k+1 vertices of the digraph such that for each i=0,.,k, (xi,xi+1) is an arc of the digraph. Digraphs in this class have high symmetry and so they can be useful as models of transmission and diffusion of the information. One of the problems we work on this Thesis is the modelation of topologies of highly symmetric interconnection networks using k-arc transitive digraphs. Thus, the first part of the Thesis is devoted to the construction of k-arc transitive digraphs, which is one of the main contributions of this Thesis. The memory of the Thesis is structured as follows.In the firstly chapters we introduced the notation and basic terminology about graphs that we are going to use throughout the Thesis. Moreover, we include a short background about another constructions of k-arc transitive digraphs known up to now. We also include the main ingredients for our construction of k-arc transitive digraphs as the 1-factorizations and covers of digraphs. In particular, we define the Cayley covers of arc-colored digraphs.In Chapter 3 we present our construction of k-arc transitive digraphs, which is also a technique to construct k-arc transitive covers of connected regular arbitrary digraphs for every positive integer k. As a construction tecnique of k-arc transitive digraphs, it generalizes results of Babai of 1995 for the cases k=0,1. The idea of the construction consists of choosing 'appropiate' vertex transitive covers of the k-line iterated digraph of the starting digraph in such a way that this covers are also k-line iterated digraphs. Furthermore, the k-arc transitive digraphs of which they are k-line iterated digraphs turn out to be covers of the starting digraph. The 'appropiate' covers of k-line iterated digraphs are Cayley covers of digraphs with k-uniform 1-factorization. Previously, we define a k-uniform 1-factorization of a k-line iterated digraph and we prove that every regular digraph admits 1-factorizations of this kind. In Chapter 4 we introduce the concept of uniform latin square and we give a characterization of the 1-uniform 1-factorizations of line digraphs in terms of uniform latin squares. In particular, we obtain the number of 1-uniform 1-factorizations of a line digraph as a function of the number of uniform latin squares in a constructive way. We also prove that uniform latin squares are isomorphic to a latin square of the composition table of a group of the same size (in fact, the group is the complete set of discordant permutations obtained by the columns of the latin square). As a consequence, we calculate explicitly the uniform latin squares of small order and we obtain the 1-uniform 1-factorization of line digraphs of small degree of some families of digraphs. The last part of this chapter is devoted to the representation of permutation groups that acts regularly on the set of arcs of a digraph. In Chapter 5 we study the automorphism group of the k-arc transitive covers we obtain with our technique. We give some results in terms of the normality for the Cayley covers of degree two. Finally in this chapter, we study the structure of the automorphism group of the k-arc transitive digraphs homomorphic to a directed cycle. In particular, we see that a Cayley digraph is homomorphic to a cycle if and only if there exists a normal subgroup of the base group such that the generators are contained in one of the cosets of the subgroup.

Mitjançant tècniques geomètriques, abordem les qüestions següents:(i) Estudi (caracterització, classificació, famílies diferenciables,...) d'una classe destacada de subespais invariants, els anomenats "marcats".(ii) Existència i construcció de solucions de l'anomenat problema de Carlson.(iii) Pertorbacions de matrius conservant un subespai invariant.I. Gohberg, P. Lancaster i L. Rodman defineixen una classe de subespais invariants, els marcats, com els que admeten una base de Jordan relativa a la restricció que sigui extensible a una base de Jordan de l'espai.J. Ferrer-F. Puerta-X. Puerta caracteritzen els subespais marcats en termes geomètrics i els classifiquen. Aquí, els caracteritzem de dues formes diferents: la primera utilitza la filtració doble de Jordan formada per les interseccions dels nuclis i les imatges de les potències de l'endomorfisme, i en particular retroba el resultat abans referit; la segona és en termes de la filtració triple, que resulta d'intersecar l'anterior amb les imatges de les potencies de la restricció, que permet generalitzar el teorema de classificació anterior.En relació amb la segona qüestió, recordem que el problema de Carlson consisteix en preguntar-se per l'existència d'una matriu amb una forma de Jordan determinada si són fixades les formes de Jordan d'un subespai invariant i del quocient. Mitjançant T. Klein es redueix el problema de Carlson a l'existència de les successions de Littlewood-Richardson. Recentment, com es pot veure en un article resum de W. Fulton, s'han trobat condicions a l'efecte. No obstant, no hi ha algorismes per construir solucions explícites. Aquí presentem una demostració geomètrica constructiva del resultat anterior que permet un algorisme per a l'obtenció de solucions.Com una aplicació important, obtenim que, fixades les característiques de Segre del subespai i del quocient, totes les característiques de Segre compatibles tenen alguna realització en qualsevol entorn de les que corresponen a un subespai marcat. Resulta, doncs, que totes les solucions al problema de Carlson apareixen pertorbant les solucions marcades elementals.Això motiva que en la tercera part d'aquest treball estudiem les deformacions d'una matriu que deixa invariant un subespai. Apliquem les tècniques usades per V.I. Arnold per a matrius quadrades per estudiar les matrius del mateix tipus que li són properes. N'obtenim l'expressió implícita d'una deformació miniversal i l'apliquem per obtenir explícitament una deformació miniversal d'una matriu marcada.Els dos primers problemes els tractem també per al cas de sistemes lineals, representats per parelles horitzontals de matrius (A,B). Per dualitat, és equivalent considerar parelles verticals, habitualment escrites (C,A), les quals es poden tractar com a aplicacions lineals definides en un subespai.I. Gohberg, P. Lancaster i L. Rodman estenen la definició de subespai invariant per una parella de matrius. Els subespais (C,A)-invariants també reben el nom de subespais invariants condicionats.Un subespai invariant condicionat es diu marcat si existeix una base de Brunovsky relativa a la restricció extensible a una base de Brunovsky del total. Obtenim una caracterització geomètrica dels subespais (C,A)-marcats, una família completa d'invariants que els classifiquen i condicions suficients per a la existència d'una base global de Brunovsky per a una família diferenciable de subespais (C,A)-marcats.El problema de Carlson també es generalitza de forma natural a parelles de matrius. Aquí, demostrem un teorema, anàleg al fet en el cas quadrat, quan la parella és observable i el quocient és un endomorfisme amb un sol valor propi. Aquest últim problema també ha estat resolt per I. Baragaña i I. Zaballa usant mètodes matricials. És remarcable que una relació directa entre les particions que caracteritzen els blocs de les matrius, que en el cas quadrat és solament necessària, és suficient per a garantir l'existència de solucions en aquest cas. Igualment generalitzem l'algorisme per a l'obtenció explícita de solucions. / We study the next items geometrically:(iv) Characterization, classification, differentiable families,...of an important type of invariant subspaces called marked subspaces.(v) Existence and construction of Carlson problem solutions. (vi) Deformations of matrices that preserve a subspace.(vii) I. Gohberg, P. Lancaster and L. Rodman define the marked subspaces as the ones that have a Jordan basis of the restriction extensible to a Jordan basis of the whole space.J. Ferrer, F. Puerta, and X. Puerta characterize the marked subspaces geometrically and classify them. Here, we characterize them in two different forms: the first one uses the Jordan double filtration formed by kernels and images intersections of the powers of the endomorphism, and in particular find the above result again; the second one is in terms of the triple filtration formed by the intersection of the sets of the above filtration with the images of the powers of the restriction, that allows us to generalize the above classification theorem. In relation to the second item, we recall that the Carlson problem consists of asking by the existence of a matrix with a certain Jordan form if the Jordan form of an invariant subspace and his quotient are fixed. T. Klein reduces the Carlson problem to the existence of the Littlewood-Richardson sequences. Recently, as we can see in a W. Fulton summary paper, existence conditions for them are obtained. However there are not algorithms to construct explicit solutions. Here we present a geometrical proof of the above result that allows us an algorithm for that.As an important application, we obtain that, if the Segre characteristic of the subspace and the quotient are fixed, all the compatible Segre characteristics can be realized in a neighbourhood of some realization corresponding to a marked subspace. It follows that all the Carlson problem solutions appear perturbing the marked solutions.This fact causes that we study the deformations of matrices preserving a subspace in the third part of this paper. We apply the techniques used by V.I. Arnold in the study of deformations of square matrices to study the same kind of matrices that are near them. We obtain the explicit form of a miniversal deformation of a marked matrix.We also study the two first items in the linear system case, done by horizontal pairs of matrices (A,B). By duality, it is equivalent to considerate vertical pairs written habitually (C,A), that we can see as linear maps defined in a subspace.I. Gohberg, P. Lancaster and L. Rodman give the definition of an invariant subspace by a pair of matrices. The (C,A)-invariant subspaces are also known as conditioned invariant subspaces.We say that a conditioned invariant subspace is marked if there is a Brunovsky basis of the restriction extendible to a Brunovsky basis of the whole space. We obtain a geometrical characterization of (C,A)-marked subspaces, a complete family of invariants and sufficient conditions in order to guarantee the existence of a global Brunovsky basis of a differentiable family of (C,A)-marked subspaces.We can also generalize the Carlson problem for pairs of matrices in a natural way. Here, we prove a theorem, similar to the one for the square case, when the pair is observable and the quotient is an endomorphism with an only eigenvalue. I. Baragaña and I. Zaballa also solved this problem using matricial methods. We want to note that a direct relation between the partitions that characterize the blocks of the matrices is sufficient to guarantee the existence of solutions while it is only necessary in the square case. Also we generalize the algorithm to obtain explicit solutions.

El objetivo del trabajo consiste en la generalización y el estudio de modelos y métodos que han mostrado su eficiencia respecto a las soluciones para los juegos cooperativos propuestas por Shapley o por Banzhaf, así como el desarrollo de propiedades derivadas de su generalización. Estos y otros conceptos se extienden a una clase más amplia de soluciones para los juegos cooperativos: los semivalores. Conforme a la idea general que se ha establecido, la memoria se estructura en seis capítulos. El primer capítulo contiene una introducción a los conceptos básicos de la teoría de juegos cooperativos con utilidad transferible. El segundo capítulo aborda el estudio de los semivalores y las estructuras de coalición. Aquí se consideran familias de semivalores a partir de las cuales se forman sistemas de referencia consiguiendo, además, establecer semivalores inducidos en espacios de juegos con menor cardinal del conjunto de jugadores, con independencia del sistema de referencia escogido. Estas actuaciones permiten generalizar el proceso que lleva del valor de Shapley al valor coalicional de Owen, dando lugar al concepto de semivalor modificado para juegos con estructura de coalición. El capítulo finaliza estableciendo unas propiedades que consiguen caracterizar axiomáticamente la modificación de la solución de Banzhaf para juegos con estructura de coalición. En el tercer capítulo se emplean de modo particular técnicas y resultados provenientes del segundo con el objetivo de estudiar, desde el punto de vista de cualquier semivalor, las consecuencias de la formación de una única coalición bipersonal estable. Además de conseguir el cálculo efectivo de los resultados tanto a partir de la función característica como de la EML, este estudio consigue caracterizar diferentes semivalores en atención a su comportamiento respecto a esta situación de cooperación modificada. El cuarto capítulo se centra en otra situación de cooperación modificada: la cooperación parcial modelizada por grafos. Allí se prueba que todo semivalor cumple propiedades deseables según la formulación de Myerson (1977). También se afirma que la normalización aditiva de cualquier semivalor verifica esas mismas propiedades, resultando que normalización aditiva y cooperación parcial son conceptos ampliamente compatibles. Además, se consigue determinar qué jugadores resultan más beneficiados o más perjudicados por la supresión de una arista de un grafo de cooperación. El quinto capítulo está dedicado al potencial. Se define y estructura un concepto de potencial para cada semivalor construido de modo recurrente, en modo análogo a como Hart y Mas-Colell (1988) y Dragan (1995) introducen esos conceptos para las soluciones de Shapley y de Banzhaf, respectivamente. También se ofrece un procedimiento para calcular el potencial para cada semivalor mediante manipulaciones adecuadas de la EML. Otras nociones derivadas del potencial, como base potencial o espacio nulo, se extienden a todos los semivalores. Se resuelven problemas inversos como la determinación de los juegos que tienen una solución prefijada o la determinación del juego conocido el poder de éste y de sus juegos restringidos. El sexto capítulo trata el problema de la determinación del subespacio intersección de todos los espacios nulos por semivalores. En esta intersección se encuentran los juegos que no pueden distinguirse del nulo por ningún semivalor. Resuelto el problema anterior con la introducción de los juegos de conmutación, se consideran semivalores modificados para juegos con estructura de coalición y se busca determinar el subespacio de indistinguibles del nulo por este tipo de soluciones. Para los juegos de más de cuatro jugadores, la introducción de las estructuras de coalición consigue reducir de modo significativo la dimensión de cada subespacio de juegos indistinguibles del nulo. / The objective of the work consists of the generalization and the study of models and methods that have shown their efficiency with respect to the solutions for the cooperative games proposed by Shapley or Banzhaf, as well as the development of properties derived from its generalization. These and other concepts extend to a more ampler class of solutions for the cooperative games: the semivalues. According to the general objective that one has settled down, the memory structure in six chapters.The first chapter contains an introduction to the basic concepts of the theory of cooperative games with transferable utility. The second chapter undertakes the study of the semivalues and the coalition structures. Here, we consider families of semivalues obtaining reference systems for semivalues; in addition, we establish induced semivalues in spaces of games with minor cardinal of the set of players, independently of the chosen system of reference. These performances allow to generalize the process that takes of the value of Shapley to the coalition value of Owen, giving rise to the concept of modified semivalue for games with coalition structure. The chapter finalizes establishing properties that are able axiomatically to characterize the modification of the solution of Banzhaf for games with coalition structure.In the third chapter it is used, of particular way, technical and results of the second with the objective of to study, from the point of view of any semivalue, the consequences of the formation of a unique stable two-person coalition. We obtain the effective calculation of the results from the function characteristic and from the EML; this study it is able to characterize different semivalues in attention from his payment with respect to this situation of modified cooperation. In the fourth chapter one studies another situation of modified cooperation: the partial cooperation expressed by graphs. There, we prove that all semivalue, as allocation rule for these situations of cooperation, verify desirable properties according to the formulation of Myerson (1977). Also, one affirms that the normalization additive of any semivalue verifies those same properties; thus, normalization additive and partial cooperation are widely compatible concepts. In addition, one is able to determine what players are more benefited or more harmed by the suppression of an edge of a graph of cooperation.The fifth chapter is dedicated to the potential. A concept of potential for each semivalue is defined and constructed of recurrent way, in analogous way to as Hart and Mas-Colell (1988) and Dragan (1995) introduce those concepts for the solutions of Shapley and Banzhaf, respectively. Also a procedure is offered to calculate the potential for each semivalue by means of suitable manipulations of the EML. Other notions derived from the potential, as potential basis or null space, extend to all semivalues. Inverse problems like the determination of the games that have a concrete solution or the determination of the game from the power, are solved. The sixth chapter deals with the problem of the determination of the subspace intersection of all the null spaces by semivalues. In this intersection are the games that cannot be distinguished from the null game by semivalues. Solved the previous problem with the introduction of the commutation games, semivalues modified for games with coalition structure are considered and it looks for to determine the subspace of indistinguishable from the null game by this type of solutions. For games with five or more players, the introduction of coalition structures is able to reduce of significant way the dimension of each subspace of indistinguishable games from the null game.

El tema d'aquesta tesi és l'enumeració de permutacions amb subseqüències prohibides respecte a certs estadístics, i l'enumeració de permutacions que eviten subseqüències generalitzades.Després d'introduir algunes definicions sobre subseqüències i estadístics en permutacions i camins de Dyck, comencem estudiant la distribució dels estadístics -nombre de punts fixos' i -nombre d'excedències' en permutacions que eviten una subseqüència de longitud 3. Un dels resultats principals és que la distribució conjunta d'aquest parell de paràmetres és la mateixa en permutacions que eviten 321 que en permutacions que eviten 132. Això generalitza un teorema recent de Robertson, Saracino i Zeilberger. Demostrem aquest resultat donant una bijecció que preserva els dos estadístics en qüestió i un altre paràmetre. La idea clau consisteix en introduir una nova classe d'estadístics en camins de Dyck, basada en el que anomenem túnel.A continuació considerem el mateix parell d'estadístics en permutacions que eviten simultàniament dues o més subseqüències de longitud 3. Resolem tots els casos donant les funcions generadores corresponents. Alguns casos són generalitzats a subseqüències de longitud arbitrària. També descrivim la distribució d'aquests paràmetres en involucions que eviten qualsevol subconjunt de subseqüències de longitud 3. La tècnica principal consisteix en fer servir bijeccions entre permutacions amb subseqüències prohibides i certs tipus de camins de Dyck, de manera que els estadístics en permutacions que considerem corresponen a estadístics en camins de Dyck que són més fàcils d'enumerar.Tot seguit presentem una nova família de bijeccions del conjunt de camins de Dyck a sí mateix, que envien estadístics que apareixen en l'estudi de permutacions amb subseqüències prohibides a estadístics clàssics en camins de Dyck, la distribució dels quals s'obté fàcilment. En particular, això ens dóna una prova bijectiva senzilla de l'equidistribució de punts fixos en les permutacions que eviten 321 i en les que eviten 132. A continuació donem noves interpretacions dels nombres de Catalan i dels nombres de Fine. Considerem una classe de permutacions definida en termes d'aparellaments de 2n punts en una circumferència sense creuaments. N'estudiem l'estructura i algunes propietats, i donem la distribució de diversos estadístics en aquests permutacions.En la següent part de la tesi introduïm una noció diferent de subseqüències prohibides, amb el requeriment que els elements que formen la subseqüència han d'aparèixer en posicions consecutives a la permutació. Més en general, estudiem la distribució del nombre d'ocurrències de subparaules (subseqüències consecutives) en permutacions. Resolem el problema en diversos casos segons la forma de la subparaula, obtenint-ne les funcions generadores exponencials bivariades corresponents com a solucions de certes equacions diferencials lineals. El mètode està basat en la representació de permutacions com a arbres binaris creixents i en mètodes simbòlics.La part final tracta de subseqüències generalitzades, que extenen tant la noció de subseqüències clàssiques com la de subparaules. Per algunes subseqüències obtenim nous resultats enumeratius. Finalment estudiem el comportament assimptòtic del nombre de permutacions de mida n que eviten una subseqüència generalitzada fixa quan n tendeix a infinit. També donem fites inferiors i superiors en el nombre de permutacions que eviten certes subseqüències.