Sesión Matemática Discreta$P_3$-convexidad en el grafo complemento del grafo generalizado de Kneser
Agustina Victoria Ledezma
Instituto de Matemática Aplicada San Luis (UNSL-CONICET) y Departamento de Matemática, Universidad Nacional de San Luis, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Dados $n \gt k$ enteros positivos, definimos $[n] = \{1,2,\ldots,n \}$, y $[n]^k$ el conjunto de $k$-subconjuntos de $[n]$. El grafo de Kneser $K(n,k)$ es el grafo cuyo conjunto de vértices es $[n]^k$ y donde dos $k$-subconjuntos $A,B \in [n]^k$ son adyacentes si y solo si $A \cap B = \emptyset$. Los grafos generalizados de Kneser $K(n,k,i)$, con $ i $ entero no negativo, son obtenidos de los grafos de Kneser de forma natural, tomando el mismo conjunto de vértices, y donde dos vértices $A$ y $B$ son adyacentes si y solo si $|A \cap B| \leq i$. Para este trabajo nos concentramos en los grafos complemento de los grafos generalizados de Kneser. Es decir, en los grafos $\overline{K(n,k,i)}$, cuyos vértices son los subconjuntos de tamaño $k$ del conjunto de tamaño $n$, y donde hay una arista entre dos vértices si el tamaño de su intersección es mayor que $i$.
Para esta familia de grafos estudiamos problemas de propagación en grafos relacionados a la $P_3$-convexidad. Suponiendo que hay un conjunto inicial de vértices contagiados, en estos problemas un vértice se contagia si dos de sus vecinos ya están contagiados. Con estas condiciones, estudiamos tres problemas: el número de cápsula, que es el tamaño del conjunto inicial de vértices contagiados más pequeño que llega a contagiar a todo el grafo; el número de convexidad, que es el conjunto de vértices más grande que no contagia a ningún otro vértice, y el número de percolación, que es el mayor tiempo que puede demorar un conjunto inicial en contagiar a todo el grafo.
Trabajo en conjunto con: Adrián Pastine (Instituto de Matemática Aplicada San Luis (UNSL-CONICET) y Departamento de Matemática, Universidad Nacional de San Luis).