Departament de Matemàtiques
http://hdl.handle.net/10803/328726
2024-03-29T10:03:33ZThe embedding problem for Markov matrices
http://hdl.handle.net/10803/672175
The embedding problem for Markov matrices
Roca Lacostena, Jordi
The goal of this thesis is to solve the embedding problem for Markov matrices, posed by Gustav Elfving in1937. A Markov matrix is non-negative square matrix whose rows sum to 1. We say that such a matrix M is embeddable if it can be written as the exponential of a rate matrix, that is a real square matrix with rows summing to zero and non-negative off-diagonal entries. In this case, we say that the rate matrix is a Markov generator for M. The embedding problem consists deciding whether a given Markov matrix is embeddable or not, thus solving the embedding problem results in giving a characterization of embeddablem matrices.
This problem is motivated by Markov processes, which are used to model the change of state of a random variable over time. under the assumption that future is independent from past given the present, that is, the assumption that the substitution probabilities do not depend on previous changes of state. In this framework, the entries of Markov matrices represent the substitution probabilities along a fixed time interval. When these probabilities ar considered to be continuous (and differentiable) functions depending on time, the Markov process is ruled by the instantaneous rates of substitution between states. In order to keep continuous-time Markov processes tractable, the substitution rates are usually assumed to be constant over time. In this case, we say that the process is a homogeneous continuous-time process and one displays all the rates together in a matrix called rate matrix Q. Moreover, the Markov matrix encoding the substitution probabilities after time t can be written as M(t) = exp(Qt) for all t=0. Thus, M(t) is embeddable and Qt is a Markov generator for it. Therefore, in the context of substitution processes, the embedding problem consists on deciding whether a given transicion matrix can be obtained from a homogeneous Markov process in continuous-time.
The embedding problem is solved for 2x2 and 3x3 Markov matrices and also for some particular cases such as matrices close to the identity or matrices with dferent real eigenvaleus. In this thesis we present a method to decide wheter a Markov matrix with different eigenvalues (real or not) is embeddable. This solves the embedding problem for a dense subset of nxn Markov matrices for any size n. We also study the rate identifiability problem, which is concerned about the unicity of Markov generators for a given embeddable matrix. Moreover, we give an explicit solution for the embedding problem for 4x4 Markov matrices. Not only this case was the smaller unsolved case, but it has practical consequences in phylogenetics as the embedding problem appears related to fundamental questions concerning the consistency of nucleotide substitution models. These models generally use a Markov process to describe the substitution of nucleotides over time in a given DNA sequence. We give the solution of the embedding problem restricted to some commonly used nucleotide substitution models such as Kimura models and the strand-symmetric model. For each of these models, one can define two different versions related by the embedding problem, a homogeneous continuous-time version and a more general version that avoids the time consideration. We shall see that the proportion of embeddale matrices (i.e. in the continuous-time version of the model) within the general version of the model decreases as the model hypothesis are relaxed. Indeed, we shall see that the proportion of embeddable matrix lies in the range between the 0.05% and the 75% depending on the complexity of the model. This shows that the time-continuous versions of these models are much more restrictive.; L'objectiu d'aquesta tesi és resoldre el problema d'embedding per a matrius de Markov, proposat per Gustav Elfving el 1937. Una matriu de Markov és una matriu quadrada, no negativa i amb files que sumen 1. Diem que una matriu de Markov M és embeddable si es pot expressar com l’exponencial d'una matriu de taxes, és a dir una matriu real, amb files que sumen 0 i amb entrades no negatives fora de la diagonal. En aquest cas, diem que la matriu de taxes és un generador de Markov de M. Tal i com el seu nom indica, el problema d'embedding consisteix en caracteritzar les matrius de Markov que són embeddable. La motivació del problema ve dels processos de Markov, els quals s'utilitzen per a modelar els canvis d'estat d'una variable aleatòria al llarg del temps sota la hipòtesi que el futur és independent del passat, és a dir, que les probabilitats de substitució no depenen dels canvis que hagin ocorregut en anteriorment. En aquest context, les entrades de les matrius de Markov representen les probabilitats de substitució després d'un període de temps fixat. Quan es considera que aquestes probabilitats són funcions contínues (i derivables) que depenen del temps, el procés de Markov es pot descriure en termes de les taxes instantànies de substitució entre estats. Per tal de mantenir el processos en temps continu tractables, sovint es considera que les taxes de substitució són constants. Sota aquesta hipòtesi d’homogeneïtat respecte el temps, les taxes de substitució es representen mitjançant les entrades d’una matriu de taxes Q i les matrius de Markov M(t) es poden escriure com l'exponencial de Qt per a tot t=0. En aquest cas, M(t) és embeddable i Qt n’és un generador de Markov. Per tant, el problema d’embedding consisteix en decidir si una matriu de transició pot sorgir d’un procés de Markov homogeni en temps continu. El problema d'embedding està resolt per a matrius 2x2 i 3x3 així com per a alguns casos particulars, com ara matrius properes a la identitat i matrius amb valors propis reals i diferents. En aquesta tesi presentem un mètode per determinar si una matriu de Markov amb valors propis diferents (reals o no) és embeddable, la qual cosa resol el problema per a un conjunt dens de matrius de Markov de qualsevol mida. També estudiem el problema d¿ identificabilitat de taxes, que consisteix en decidir si una matriu embeddable admet un únic generador de Markov. A més a més, resolem explícitament el problema d'embedding pel cas 4x4. Aquest cas és especialment rellevant, no només perquè era el cas més petit sense resoldre, sinó també per les seves implicacions en filogenètica, on el problema d'embedding està relacionat amb qüestions fonamentals respecte la definició i consistència dels models de substitució de nucleòtids utilitzats per modelar l¿ ' evolució de cadenes d'ADN. Per aquest motiu, també presentem la solució del problema d'embedding restringit a alguns dels models de substitució de nucleòtids més utilitzats, com per exemple, els models de Kimura o el model strand-symmetric. Per a cada un dels models considerats podem definir-ne dues versions relacionades pel problema d'embedding, una en temps continu i l'altra sense cap consideració respecte el temps. Observarem que la proporció de matrius embeddable (i.e. en temps continu) dins de la versió general del model disminueix a mesura que es relaxen les hipòtesis del model. De fet, veurem que aquesta proporció oscil·la entre el 75% i el 0,05% segons la complexitat del model i que per tant les versions en temps continu són molt més restrictives.
L'apendix B (p.163-172) conté el resum de la tesi en català
2021-05-18T00:00:00ZCompletion and decomposition of hypergraphs by domination hypergraphs
http://hdl.handle.net/10803/458247
Completion and decomposition of hypergraphs by domination hypergraphs
Ruiz Muñoz, José Luis
A graph consists of a finite non-empty set of vertices and a set of unordered pairs of vertices, called edges. A dominating set of a graph is a set of vertices D such that every vertex not in D is adjacent to some vertex in D. A hypergraph on a finite set X is a collection of subsets of X, none of which is a proper subset of another. The domination hypergraph of a graph is the collection of all the minimal vertex dominating sets of the graph. A hypergraph is a domination hypergraph if it is the domination hypergraph of a graph. In general, a hypergraph is not a domination hypergraph. The objective of this work is to approximate a hypergraph by domination hypergraphs and that the optimal approximations determine uniquely the hypergraph.
In Chapter 1 we introduce two structures of distributive lattices on the set of hypergraphs on a finite set and also define some operations: the complementary hypergraph and two transversal operations. We study the behavior of these operations with respect to the partial orders and the lattice structures.
In Chapter 2 we first introduce several hypergraphs associated with a graph, the most important one being the domination hypergraph, and we establish several relationships among them. Then we compute the domination hypergraph of all graphs, modulo isomorphism, up to order 5. We also investigate when a given hypergraph is a domination hypergraph and find all domination hypergraphs in some cases.
In Chapter 3 we present the problem of approximating a hypergraph by domination hypergraphs. We introduce four families of approximations of a hypergraph, which we call completions, depending on which partial order we use and on which side we approximate. We set some sufficient conditions for the existence of completions, introduce the sets of minimal or maximal completions of a hypergraph and study the concept of decomposition, which leads to the decomposition index of a hypergraph. Avoidance properties turn out to be an essential ingredient for the existence of domination completions.
In Chapter 4 we give some computational techniques and calculate the upper minimal domination completions and the decomposition indices of some hypergraphs.
In the appendices we give the SAGE code developed to perform the calculations of the thesis and we list all the domination hypergraphs of all graphs of order 5 and all the graphs of order 5 with the same domination hypergraph.; Un grafo consiste en un conjunto no vacío de vértices y un conjunto de pares no ordenados de vértices denominados aristas. Un conjunto de vértices D es dominante si todo vértice que no esté en D es adyacente a algún vértice de D. Un hipergrafo sobre un conjunto finito X es una colección de subconjuntos de X, ninguno de los cuales es un subconjunto de ningún otro. El hipergrafo de dominación de un grafo es la colección de los conjuntos dominantes minimales del grafo. Un hipergrafo es de dominación si es el hipergrafo de dominación de un grafo. En el capítulo 1 introducimos dos estructuras de retículo distributivo en el conjunto de hipergrafos sobre un conjunto finito y también definimos algunas operaciones: el complementario de un hipergrafo y las dos operaciones de transversal correspondientes a cada una de las estructuras de retículo. Estudiamos el comportamiento de estas operaciones con respecto a los órdenes parciales y las estructuras de retículo. En el capítulo 2 introducimos varios hipergrafos asociados a un grafo, siendo los más importantes el hipergrafo de dominación y el hipergrafo de independencia-dominación del grafo, cuyos elementos son los conjuntos independientes maximales del grafo, y establecemos varias relaciones entre ellos. Después calculamos el hipergrafo de dominación de todos los grafos de orden 5, salvo isomorfismo. También investigamos cuándo un hipergrafo es un hipergrafo de dominación y encontramos todos los hipergrafos de dominación en algunos casos. En el capítulo 3 presentamos el problema de la aproximación de un hipergrafo por hipergrafos de una familia dada. Dado un hipergrafo, definimos cuatro familias de aproximaciones, que llamamos compleciones, dependiendo del orden parcial usado y de por dónde aproximemos el hipergrafo. Establecemos condiciones suficientes para la existencia de compleciones, introducimos los conjuntos de compleciones minimales o maximales de un hipergrafo y estudiamos el concepto de descomposición, que conduce al índice de descomposición de un hipergrafo. Las propiedades de evitación resultan ser cruciales en el estudio de la existencia de descomposiciones. En el capítulo 4 presentamos técnicas de cálculo y calculamos las compleciones de dominación minimales superiores y los índices de descomposición de algunos hipergrafos. En los apéndices damos el código SAGE, desarrollado para realizar los cálculos de esta tesis, y damos la lista de los hipergrafos de dominación de todos los grafos de orden 5 así como todos los grafos de orden 5 que poseen el mismo hipergrafo de dominación.
2017-07-18T00:00:00ZOn the fractional Yamabe problem with isolated singularities and related issues
http://hdl.handle.net/10803/404450
On the fractional Yamabe problem with isolated singularities and related issues
Torre Pedraza, Azahara de la
My research is based on non-local elliptic semilinear equations in conformal geometry. The fractional curvature is defined from the conformal fractional Laplacian and it is a non-local version of some of the classical local curvatures such as the scalar curvature, the fourth-order Q-curvature or the mean curvature. This new notion of non-local curvature has good conformal properties that allow to treat classical problems from a more general convexity point of view. Note that the fractional curvature in my research is different from the one defined by Caffarelli, Roquejoffre and Savin .
In particular, I have worked on the fractional singular Yamabe problem and related issues. This problem arises in conformal geometry when we try to find a conformal metric to a given one having constant fractional curvature and prescribed singularities. The precise problem I considered in my thesis was to find solutions for the fractional Yamabe problem in the Eucliden space of dimension bigger than 2¿, 0<¿<1, with prescribed isolated singularities: first, I just considered radial solutions when there is an isolated singularity and, later, the problem of removing a finite number of points.
This thesis consists of nine chapters. First, we give is a brief introduction and summary of the thesis. Next, provide some background, notation and known results. Later, we show the main results, i.e, Chapters 3, 4, 5 and 6. After this, we introduce the research plan to come. The thesis also has two appendixes with useful computations.
I started my research focusing on the geometric interpretation of the problem for an isolated singularity (Chapter 3). This study is based on an extension problem for the computation of the conformal fractional Laplacian. This is a Dirichlet-to-Neumann problem for a degenerate elliptic, but local, equation, which gives an example of a boundary reaction problem where the nonlinearity is of power type with the critical Sobolev exponent.
Later, I treated the problem as an integro-differential equation, facing two main difficulties: the lack of compactness and the fact that we are dealing with a non-local ODE (Chapter 4) . Our study is carried out using variational methods and it proves the existence of Delaunay-type solutions for the problem. These are radially symmetric metrics with constant fractional curvature.
Finally, I applied some gluing methods together with a Lyapunov reduction to construct solutions for the singular fractional Yamabe problem when the singular set consists of a given finite number of points (Chapter 5).
At the moment, I am working on the fractional Caffarelli-Kohn-Nirenberg inequality, which is an interpolation between the Hardy and Sobolev fractional inequalities. In particular, I am looking at the radial symmetry or symmetry breaking of the minimizers (Chapter 6).
I have collaborated with Weiwei Ao (University of British Columbia), María del Mar González (Universidad Autónoma de Madrid), Manuel del Pino (Universidad de Santiago, Chile) and Juncheng Wei (University of British Columbia).; Mi investigación se basa en ecuaciones no-locales elípticas semilineales que surgen en la geometría conforme. La curvatura fraccionaria se define partir del Laplaciano fraccionario conforme y es una versión no local de algunas de las curvaturas locales clásicas tales como la curvatura escalar, la Q-curvatura (operador de orden 4) o la curvatura media. Esta nueva noción de curvatura no-local tiene buenas propiedades conformes que permiten tratar problemas clásicos desde un punto de vista de convexidad más general. Debemos tener en cuenta que se trata de una curvatura fraccionaria distinta a la definida por Caffarelli, Roquejoffre y Savin . En particular, he trabajado en el problema de Yamabe singular fraccionario y problemas relacionados. Se trata de un problema que aparece en la geometría conforme cuando intentamos encontrar una métrica conforme a la dada en una variedad, que tenga curvatura fraccionaria constante y singularidades prescritas. Más concretamente, el problema que he considerado para mi tesis es encontrar soluciones para el problema de Yamabe fraccionario en el espacio Euclídeo de dimensión mayor que 2¿, 0<¿<1, con singularidades aisladas prescritas: en primer lugar, consideré sólo soluciones radiales para una singularidad aislada y más adelante, soluciones para este problema cuando el conjunto singular consta de un número finito de puntos. La tesis está compuesta por nueve capítulos. En primer lugar, hacemos una introducción a modo de sumario de la tesis. Después, hay un capítulo conocimientos básicos, notación, historia del problema y resultados previos. En los capítulos 3,4,5 y 6 presentamos los principales resultados de la tesis, que resumimos más abajo. Finalmente, presentamos brevemente la idea de trabajo para el futuro cercano. En la tesis podemos encontrar también, dos apéndices con cálculos y resultados que serán útiles en la lectura de la tesis. El comienzo de mi investigación se basó en la interpretación geométrica del problema para un singularidad aislada (Capítulo 3). Este estudio parte del problema de extensión para calcular el Laplaciano fraccionario conforme. Se trata de un problema Dirichlet-to-Neumann para una ecuación elíptica, pero local, que proporciona un ejemplo del problema de reacción con borde en el que la no-linearidad es del tipo exponente crítico de Sobolev. Más adelante, traté el mismo problema pero desde el punto de vista de una ecuación integro diferencial. Este método presenta dos dificultades principales: la pérdida de compacidad y el hecho de que estamos tratando con una ODE( ecuación diferencial ordinaria ) no local (Capítulo 4). Nuestro estudio es llevado a cabo utilizando el método variacional y prueba la existencia de soluciones ¿del tipo Delaunay¿ para nuestro problema. Estas soluciones son radialmente simétricas y tienen curvatura fraccionaria constante. Por último, he utilizado métodos de "gluing" (o pegado) junto con el método de reducción de Lyapunov para la construcción de soluciones para el problema de Yamabe singular fraccionario cuando el conjunto singular dado está formado por un número finito de puntos (Capítulo 5). Actualmente, estoy trabajando en la generalización de la desigualdad de Caffarelli-Kohn-Nirenberg al caso fraccionario; se trata de una interpolación entre las desigualdades de Hardy y Sobolev fraccionarias. En particular, estoy estudiando la simetría o pérdida de simetría de los minimizantes (Capítulo 6). En la investigación presentada en esta tesis he colaborado con Weiwei Ao (University of British Columbia), María del Mar González (Universidad Autónoma de Madrid), Manuel del Pino (Universidad de Santiago, Chile) y Juncheng Wei (University of British Columbia).
2016-12-19T00:00:00ZStark-Heegner points and p-adic L-functions
http://hdl.handle.net/10803/403958
Stark-Heegner points and p-adic L-functions
Casazza, Daniele
Let K|Q be a number field and let Z(K,s) be its associated complex L-function. The analytic class number formula relates special values of Z(K,s) with algebraic invariants of the field K itself. It admits a Galois equivariant refinement known as Stark conjectures.
We have a very similar picture in the case of elliptic curves. Let E/Q be an elliptic curve and let L(E/Q,s) be its associated complex L-function. The conjecture of Birch and Swinnerton-Dyer relates the behaviour of L(E/Q,s) at s=1 to the structure of rational solutions of the equation defined by E. The equivariant Birch and Swinnerton-Dyer conjecture is obtained including in the picture the action of Galois groups.
The elliptic Stark conjecture formulated by H. Darmon, A. Lauder and V. Rotger purposes a p-adic analogue of the equivariant Birch and Swinnerton-Dyer conjecture, under several assumption. In their paper, the authors formulate the conjecture and prove it in some cases of good reduction of E at p using Garrett-Hida method and performing a factorization of p-adic L-functions. In this dissertation we focus on the elliptic Stark conjecture and we show how it is possible to extend the result of Darmon, Lauder and Rotger.
In the case of good reduction of E at p we can slightly extend the result using Hida-Rankin method. This method also gives us a better control of the constants appearing in the result, thus yielding an explicit formula which contains invariants associated with the elliptic curve. To achieve the proof we mimic the main result of Darmon, Lauder and Rotger in our setting and we make use of a p-adic Gross-Zagier formula which relates special values of the Bertolini-Darmon-Prasanna p-adic L-function to Heegner points.
In a second moment we extend both our result and Darmon-Lauder-Rotger result to the case of multiplicative reduction of E at p. In this setting we cannot use Bertolini-Darmon-Prasanna p-adic L-function due to some technical reasons. To avoid the problem we consider Castella's two variables p-adic L-function. We use both Garrett-Hida method and Hida-Rankin method. In the two cases we obtain formulae which are similar to those of the good reduction setting.; Sigui K/Q un cos de nombres i sigui L(K,s) la funció L de Dedekind associada. La fórmula analítica del nombre de classes relaciona els valors especials de L(K,s) amb invariants algebraics del cos K. Aquesta formula admet un refinament Galois equivariant conegut com les conjectures de Stark. En el cas de les corbes el·líptiques ens trobem amb un escenari similar. Sigui E/Q una corba el·líptica i sigui L(E/Q,s) la seva L-sèrie complexa. La conjectura de Birch i Swinnerton-Dyer relaciona el comportament de L(E/Q,s) en el punt central crític s=1 amb l'estructura del conjunt de punts racionals de l'equació definida per E. La versió Galois-equivariant proporciona un refinament d'aquesta conjectura per al canvi de base d'E a un cos de nombres K qualsevol. La conjectura el·líptica de Stark formulada per H. Darmon, A. Lauder i V. Rotger proposa un anàleg p-àdic de la conjectura Galois-equivariant de Birch i Swinnerton-Dyer, sota vàries hipòtesis. En el seu article, els autors formulen la conjectura i la demostren en alguns casos on el primer p és un primer de bona reducció per E, usant el mètode de Garrett-Hida i demostrant pel camí una factorització de funcions L p-àdiques. En aquesta tesi doctoral estudiem i demostrem nous resultats sobre la conjectura el¿líptica de Darmon-Lauder-Rotger En el cas on p és un primer de bona reducció per E, refinem el resultat principal de Darmon-Lauder-Rotger mitjançant el mètode de Rankin-Hida, que ens dóna un millor control de les constants que apareixen en les demostracions i ens permet demostrar una fórmula explícita que involucra invariants globals associats a la corba el¿líptica. Per aconseguir-ho generalitzem la estratègia de Darmon, Lauder and Rotger, tot utilitzant la p-adic Gross-Zagier formula que relaciona els valors especials de la funció L p-àdica de Bertolini-Darmon-Prasanna amb punts de Heegner. L'altre resultat principal d'aquesta tesi és la demostració de la conjectura el·líptica de Stark en un cas on E té reducció multiplicativa en el primer p. Per a fer-ho explotem la funció L p-àdica de F. Castellà, que és una generalització a dos variables de la funció L p-àdica de Bertolini-Darmon-Prasanna.
2016-10-28T00:00:00Z