Discrete operators and distances on subdivision networks

Abstract

(English) The research we have carried out lies within the domain of diffusion problems for elliptic operators that are defined on discrete structures called networks, that are graphs that are capable of discriminating between edges and between vertices per se as well.Typically elliptic problems are posed in the continuum setting, defined on surfaces or manifolds and are a corner stone of applied mathematics. Partial differential equations and the geometry of the domain where they are to be satisfied, as well as boundary conditions that a solution must fulfill are the ingredients of this critical tool in the development of mathematics for more than the last two hundred years. We are concerned with elliptical problems that refer to the discrete case. Diffusion in a discrete network is understood as the distribution of a physical entity between all different adjacent vertices of a given vertex. Although diffusion is conceived as a local phenomena that becomes globally widespread, our work is situated in a model that permits adjacencies with vertices that are not only in the spatial vicinity but can be situated far away, at the other end of the structure. Therefore allows an idea of diffusion that overcomes the classical concept. To carry out our research we have applied techniques of the so called Discrete Potential Theory. So the first framework where our work fits in is that of discrete boundary value problems. Specifically we have dealt with solving Poisson problems where the elliptical operator is the combinatorial Laplacian, the normalized Laplacian and Schrödinger type operators as well. The elementary graph operation of subdivision of an edge and, by extension, subdivision of all edges is very useful for deciding planarity of a given graph. But at the same time it can be intimately and undeniably related with the series connection of two elements in an electrical circuit. In our work we have developed a new concept of electrical subdivision (two versions) and we have analyzed the behavior of different diffusion problems in these contexts. Specifically, our main interest has been focused on relating the solution of a DBVP posed on an electrically subdivided network to the solution of another DBVP, related to the previous one, and posed on the pre-existing network, before the subdivision process has been applied. So, the main results obtained determine the relationship between the Green operators associated with an elliptical discrete difference operator that corresponds to a subdivided network and the Green operator associated with the same operator but corresponding to the initially given network. A second target that has been set ourselves, and on which we have been able to find nice results is the analysis of the effective resistances and which is the relationship that is stablished between effective resistances associated with a subdivision network and effective resistances corresponding to the network without being electrically subdivided. Finally a third main objective has been the study of the well known Kirchhoff index as a topologycal network invariant. We have managed to obtain the existing relation between Kirchhoff indices of an initial given network and an electrically compatible subdivision network obtained from it. Since both, the considered elliptic discrete operators that we have taken into account but their associated Green operators as well can be represented by matrices, a possible lecture of our results can be set in the field of computing generalized inverses matrices. Specifically we have found out entrywise expressions of Moore-Penrose inverse matrices of high-dimensional matrices in terms of the contents of Moore-Penrose matrices of smaller matrices. In this sense our results may be related to the well-known Sherman-Morrison-Woodbury expressions.

(Català) La recerca que hem dut a terme s’emmarca en la resolució de problemes de difusió per a operadors el·líptics definits sobre estructures discretes que anomenem xarxes, grafs capaços de distingir no només entre arestes sinó que també entre vèrtexs per se. Típicament els problemes el·líptics es situen en el continu, es defineixen sobre superfícies o varietats i són una eina clau en la matemàtica aplicada. Les equacions en derivades parcials i la geometria del domini en la que es consideren que s’han de satisfer, així com les condicions de frontera que una solució ha de complir són els ingredients d’aquesta eina cabdal en el desenvolupament de la matemàtica dels darrers dos segles. En el cas que ens ocupa, els nostres problemes el·líptics fan referència al cas discret. La difusió en una xarxa discreta s’entén com la distribució per entre els diferents vèrtex adjacents d’alguna entitat física que es troba en un determinat vèrtex. Tot i que la difusió es concep com un fenomen local que s’estén fins a tenir un abast global, el nostre treball es situa en un model que permet adjacències amb punts que no es troben en la immediatesa espacial, que fins i tot es poden situar a l’altre extrem d’una estructura, i per tant permet una nova idea de la difusió que depassa el concepte clàssic. Per dur a terme la nostra recerca hem aplicat tècniques pròpies del que coneixem com a Teoria Discreta del Potencial. Així doncs el primer context en que es pot entendre el nostre treball és el dels problemes de valors a la frontera en el cas discret (PVFD). Específicament hem tractat la resolució de problemes de Poisson pels operadors Laplacià combinatori, Laplacià normalitzat i el cas més general d’operadors de Schrödinger singulars. L’operació de subdivisió d’una aresta en un graf i per extensió en totes les arestes és elemental i de gran utilitat per a demostrar per exemple si un graf donat es pot dibuixar al pla o no. Però a la vegada té una innegable relació amb la connexió en sèrie entre dos elements en un circuit elèctric. En el nostre treball hem desenvolupat un concepte nou de subdivisió elèctrica (dues versions) i hem analitzat el comportament de diversos problemes de difusió en aquests contexts. Específicament, el nostre principal interès s’ha centrat en relacionar la solució d’un PVFD en una xarxa elèctricament subdividida amb la solució d’un altre PVFD relacionat amb l’anterior definit sobre la xarxa preexistent, abans de considerar el procés de subdivisió. Així doncs els principals resultats obtinguts han estat determinar la relació entre els operadors de Green associats a un operador el·líptic corresponent a una xarxa subdividida i l’operador de Green associat al mateix operador el·líptic corresponent a la xarxa inicial. L’anàlisi de les resistències efectives i de com s’estableix la relació entre resistències efectives associades a les dues xarxes, la segona resultat d’una subdivisió elèctrica de la primera, també ha estat un objectiu que ens hem plantejat i sobre el qual hem estat capaces de trobar resultats. Finalment hem estudiat l’índex de Kirchhoff d’una xarxa subdividida i hem aconseguit establir la relació entre els valors que l’índex de Kirchhoff assoleix entre dues xarxes, una inicialment donada i una altra generada a partir de l’anterior per un procediment de subdivisió elèctrica. Donat que tant els operadors discrets el·líptics considerats com els seus corresponents operadors de Green associats poden representar-se matricialment, una possible lectura dels nostres resultats és en el càlcul de matrius inverses generalitzades de matrius d’alta dimensió en termes de matrius inverses generalitzades de matrius de més baixa dimensió. En aquest sentit els nostres resultats poden relacionar-se amb les conegudes expressions de Sherman-Morrison-Woodbury.