Isomorfismos entre Grafos Aleatorios Densos No homogéneos.
Loading...
Date
2025
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
En este trabajo estudiamos el problema de encontrar el tamaño del subgrafo inducido en común más grande entre dos grafos aleatorios G1 y G2, que denotaremos por L(G1, G2). Este problema tiene relevancia en distintas aplicaciones como en reconocimiento de patrones, bio química y ciencia molecular. Recientemente se ha estudiado el valor típico de L(G1, G2) entre dos grafos aleatorios generados por el cl´ asico modelo homogéneo de Erdos–Rényi.
La intención de este estudio es generalizar dicho resultado a otros modelos de grafos alea torios. Un grafón W : [0,1]2 → [0,1] es una función simétrica y medible. Los grafones son comúnmente estudiados en la teoría de límites de grafos, y a partir de un grafón W se puede definir un modelo no homogéneo de grafos aleatorios, que se denota por G(n, W), y coincide con el modelo homogéneo cuando el grafón es una función constante. En esta tesis, revisamos resultados conocidos en grafos aleatorios homogéneos, como el estudio del tamaño del clique más grande y el tamaño del subgrafo inducido en común más grande entre dos grafos. Además, extendemos el estudio del tamaño del subgrafo inducido en común más grande entre grafos no necesariamente homogéneos. En particular, obtenemos un resultado que no existe en la literatura actualmente, que corresponde al valor de L(G1,G2) cuando G1 ∼ G(n,1/2) y G2 ∼ G(n, W), donde W es un grafón adecuado.
Description
Tesis presentada para optar al título de Ingeniera Civil Matemática
Keywords
Grafos aleatorios, Modelos matemáticos, Isomorfismo (Matemáticas)