Sesión Matemática Discreta
Jueves 21 de septiembre
Mañana - Lugar: Anfiteatro Q
| Horario | Título | Expositor/a |
|---|---|---|
| 8:20 ~ 8:35 | Nash implementation in a many-to-one matching market | Noelia Juarez |
| 8:40 ~ 8:55 | Nonstationary equilibria in a class of dynamic games with heterogeneous discounting | Luis Alcalá |
| 9:00 ~ 9:15 | MODELOS DE ASIGNACIÓN DINÁMICOS | Adriana del Valle Amieva Rodriguez |
| 9:20 ~ 9:35 | Manipulaciones Obvias en Matching con y sin Contratos | R. Pablo Arribillaga |
| 9:40 ~ 9:55 | Trade-off between manipulability and dictatorial power: a proof of the Gibbard-Satterthwaite Theorem | Agustín G. Bonifacio |
| 10:30 ~ 10:45 | Grafos circulantes singularmente coespectrales | Ezequiel Dratman |
| 10:50 ~ 11:05 | El Teorema General de Manipulabilidad para un modelo de matching muchos a muchos | Paola Belén Manasero |
| 11:10 ~ 11:50 | Contando pasos para la re-estabilización | Pablo Neme |
| 11:50 ~ 12:05 | Propiedades de los elementos de un conjunto estable Von Neumann-Morgenstern | Andrés Mauricio Lucero Quevedo |
Tarde - Lugar: Anfiteatro Q
| Horario | Título | Expositor/a |
|---|---|---|
| 14:40 ~ 14:55 | Dominación italiana en grafos con "pocos" caminos inducidos de 4 vértices | Lara Fernández |
| 15:00 ~ 15:15 | Hacia una caracterización de grafos italianos y grafos sicilianos | Alberto José Ferrari |
| 15:20 ~ 15:35 | Propiedades de los asociaedros de grafos | Ana Gargantini |
| 15:40 ~ 15:55 | Problemas localmente verificables en grafos | Carolina Lucía Gonzalez |
| 16:00 ~ 16:15 | Todo conjunto parcialmente ordenado treelike es CPT | Noemí Amalia Gudiño |
| 16:50 ~ 17:05 | Sobre grafos de distancia de Kneser | Agustina Victoria Ledezma |
| 17:10 ~ 17:25 | Problema de la $\{k\}$-dominación total en nuevas subclases de grafos. | María Inés Lopez Pujato |
| 17:30 ~ 17:45 | About of the determinant of graphs with a unique maximum matching. | Diego Gabriel Martinez |
| 17:50 ~ 18:05 | $R$-Secuenciabilidad de grupos no abelianos | María Valentina Soldera Ruiz |
Viernes 22 de septiembre
Mañana - Lugar: Aula 50
| Horario | Título | Expositor/a |
|---|---|---|
| 8:20 ~ 8:35 | KE-index | Daniel Alejandro Jaume |
| 8:40 ~ 9:20 | El problema de Hamilton-Waterloo: historia, variaciones y últimos avances | Adrián Pastine |
| 9:20 ~ 9:35 | Espectro de la matriz de Harary del producto join de grafos regulares. | Luis Medina |
| 9:40 ~ 9:55 | Estudio de una nueva modelización para problemas de locación de servicios. | María Inés Lopez Pujato |
Tarde - Lugar: Aula 51
| Horario | Título | Expositor/a |
|---|---|---|
| 14:40 ~ 14:55 | El problema del conjunto perfecto de aristas dominantes en grafos sin emparejamientos dominantes inducidos y grafos sin $P_6$ inducidos | Camilo Vera |
| 15:00 ~ 15:15 | Grafos cuyo cuadrado de línea es libre de $P_k$* | Martina Vergara |
| 15:20 ~ 15:35 | Sobre la coordinación de los complementos de línea de árboles* | Rocío Belén Suárez Albanesi |
| 15:40 ~ 15:55 | Rango de matriz de distancia en grafos | Verónica Moyano |
| 16:00 ~ 16:15 | Estudios de complejidad del problema de mínima violación cromática en grafos | María Elisa Ugarte |
| 16:20 ~ 16:35 | Empaquetamientos generalizados en grafos con clique-width acotado | Natalí Romina Vansteenkiste |
| 16:40 ~ 16:55 | Sobre la familia de grafos con 1-persistencia en la relajación clique. | Lucía Moroni |
Charlas invitadas
Jueves 21 de septiembre, 11:10 ~ 11:50
Contando pasos para la re-estabilización
Pablo Neme
IMASL-UNSL, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
En los modelos de matching bilateral, uno de los mercados más estudiados son los mercados laborales descentralizados entre firmas y trabajadores. En estos mercados, las firmas tienen preferencias sobre los trabajadores y los trabajadores sobre las firmas. En este trabajo asumimos que las firmas no pueden despedir a sus trabajadores, y solo pueden contratar nuevos cuando tienen puestos vacantes. En este modelo de mercados, una situación común es que un trabajador desee mejorar su condición laboral, y para ello deberá renunciar a su puesto de trabajo para generar una cadena de vacancias en las firmas, en la cual una firma más deseada por este trabajador le realice una oferta y así mejorar su condición laboral. En este articulo presentamos un algoritmo que modela esta situación. Cuando se considera que los trabajadores tienen un costo por la espera de una nueva oferta, dicho algoritmo nos da la información necesaria para que un trabajador pueda tomar la decisión entre renunciar y esperar una nueva oferta, o mantener su actual puesto de trabajo.
Trabajo en conjunto con: Agustín Bonifacio (UNSL-IMASL), Nadia Guiñazú (UNSL-IMASL), Noelia Juarez (UNSL-IMASL) y Jorge Oviedo (UNSL-IMASL).
Viernes 22 de septiembre, 8:40 ~ 9:20
El problema de Hamilton-Waterloo: historia, variaciones y últimos avances
Adrián Pastine
Departamento de Matemática, Universidad Nacional de San Luis, e IMASL (UNSL-CONICET), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
El problema de Hamilton-Waterloo es un problema clásico de descomposición de grafos, que yace en la intersección entre la teoría de grafos y la teoría de diseños combinatorios. Este tipo de problemas tienen aplicaciones en la construcción de otros objetos combinatorios y en el diseño de experimentos.
Un $k$-factor de un grafo es un subgrafo generador $k$-regular. En particular, un $1$-factor es un matching perfecto, y un $2$-factor es una unión disjunta de ciclos. Denotamos por $K_n^*$ al grafo completo $K_n$ de orden $n$ si $n$ es impar, y a $K_n$ menos las aristas de un $1$-factor si $n$ es par. Dados dos $2$-factores de $K_n^*$, $F_1$ y $F_2$, el problema de Hamilton-Waterloo estudia para qué valores de $r$ y $s$ es posible particionar las aristas de $K_n^*$ en $r$ copias de $F_1$ y $s$ copias de $F_2$. La mayor parte del estudio de este problema se realizó para el caso uniforme, que es cuando todos los ciclos de $F_1$ tiene un tamaño fijo $x$, y todos los ciclos de $F_2$ tienen un tamaño fijo $y$. De todos modos, quedan aún casos uniformes por estudiar, en particular cuando $x$ e $y$ son coprimos. En lo que respecta al caso no uniforme, hay muy poco hecho, por lo que queda aún mucho camino por recorrer.
En esta charla daremos un recuento histórico del problema, pasando por los resultados más importantes y presentando el estado del arte actual. Presentaremos algunas construcciones que hacen uso de grupos y de cuasigrupos, y algunas técnicas de producto de grafos y de duplicado de vértices. Hablaremos también de algunas variaciones del problema, como el problema de Hamilton-Waterloo de la luna de miel, y el problema de Hamilton-Waterloo sobre grafos equipartitos completos.
Resúmenes
Jueves 21 de septiembre, 8:20 ~ 8:35
Nash implementation in a many-to-one matching market
Noelia Juarez
Universidad Nacional de San Luis, Instituto de Matemática Aplicada 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.
In a many-to-one matching market with substitutable preferences, we analyze the game induced by a stable rule. When both sides of the market play strategically, we show that any stable rule implements, in Nash equilibrium, the individually rational matchings. Also, when only workers play strategically and firms' preferences satisfy the law of aggregated demand, we show that any stable rule implements, in Nash equilibrium, the stable matchings.
Trabajo en conjunto con: Paola B. Manasero (Instituto de Matemática Aplicada San Luis, Universidad Nacional de San Luis) y Jorge Oviedo (Instituto de Matemática Aplicada San Luis, Universidad Nacional de San Luis).
Jueves 21 de septiembre, 8:40 ~ 8:55
Nonstationary equilibria in a class of dynamic games with heterogeneous discounting
Luis Alcalá
Instituto de Matemática Aplicada San Luis, UNSL-CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
The study of dynamic games with heterogeneous discount factors has remained a relatively unexplored research area which involves several technical challenges. Recent contributions to the literature have found significant differences with the case of symmetric discounting. This paper introduces nonstationary strategies in a class of common property games, also known as dynamic resource games. We show that there exists a full-commitment equilibrium which tends to favor impatient players at the early stages of the game, but more patient players toward the late stages and in the long-run. This equilibrium is Pareto optimal. We also characterize Markov-perfect equilibria in nonstationary strategies and analyze their stability properties.
Jueves 21 de septiembre, 9:00 ~ 9:15
MODELOS DE ASIGNACIÓN DINÁMICOS
Adriana del Valle Amieva Rodriguez
Universidad Nacional de San Luis, Departamento de Matemática, Instituto de Matemática Aplicada San Luis - CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Resumen:
La investigación de los modelos de asignación bilateral (o modelos de matching) comenzó con la resolución de problemas prácticos en la vida real, como la asignación de médicos residentes a hospitales, la asignación de estudiantes y profesores en escuelas públicas, la asignación de riñones a pacientes con problemas renales, entre otros. En 1962, Gale y Shapley publicaron el primer artículo sobre estos modelos, donde presentaron un algoritmo que demostró que siempre existe una asignación ``estable'' para el modelo de matching del tipo escuela-estudiante (también conocido como modelo de muchos a uno). En este trabajo, para modelos muchos a muchos, se considera la situación en la que las escuelas públicas necesitan contratar profesores y los profesores pueden trabajar en \emph{varias} escuelas públicas (también conocido como modelo de muchos a muchos). Lo interesante en estos modelos es cuando se agrega una dimensión temporal, donde un profesor puede trabajar en una o varias escuelas en una etapa y luego cambiar a otra u otras en la siguiente. Además, se tiene en cuenta la posibilidad de que algunos profesores se retiren del mercado laboral público para trabajar en escuelas privadas o jubilarse, mientras que otros profesores nuevos ingresan al mercado laboral. Para estos mercados dinámicos, adaptamos el concepto de estabilidad para dar una solución al problema y estudiamos sus propiedades.
Trabajo en conjunto con: Pablo Neme (Universidad Nacional de San Luis, Departamento de Matemática, Instituto de Matemática Aplicada San Luis - CONICET) y Agustín Bonifacio (Universidad Nacional de San Luis, Departamento de Matemática, Instituto de Matemática Aplicada San Luis - CONICET).
Jueves 21 de septiembre, 9:20 ~ 9:35
Manipulaciones Obvias en Matching con y sin Contratos
R. Pablo Arribillaga
Instituto de Matemática Aplicada San Luis (UNSL-CONICET), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
En el modelo de matching de muchos a uno con contratos, introducidos en [1], hay un mercado bilateral cuyos lados disjuntos se denominan típicamente médicos y hospitales. El problema consiste en asignar agentes de un lado del mercado a agentes del lado opuesto, a través de unos contratos. Cada médico puede firmar un contrato como máximo, mientras que los hospitales pueden firmar múltiples contratos. Dado que dos agentes que deseen suscribir un contrato existente son libres de hacerlo, y además los agentes pueden rescindir unilateralmente contratos anteriores si lo consideran conveniente, consideraremos asignaciones estables, es decir, resultados que son sostenibles en el tiempo, suponiendo que el mercado permanece sin cambios. Además de la estabilidad, la no manipulabilidad de una regla de asignación también tiene un papel central en la literatura de matching. Un agente manipula una regla de asignación si existe una situación en la que obtiene un mejor resultado para él declarando una preferencia alternativa a la verdadera. En el modelo de matching muchos a uno (con y sin contratos) y preferencias sustituibles, cualquier emparejamiento estable será susceptible de manipulaciones (ver [1] y [2]). Dado que las manipulaciones no se pueden evitar por completo en este contexto, buscamos reglas de asignación estables que al menos eviten manipulaciones obvias, tal como las definen en [3]. Una manipulación es obvia si es mucho más fácil para los agentes reconocerla y ejecutarla, en un sentido específico y formal.
Nuestro primer resultado establece que la regla de asignación doctor-óptimal no es obviamente manipulable (para los médicos) en el contexto general de un modelo de matching muchos a uno con contratos y preferencias sustituibles para hospitales. Por lo tanto, aunque no hay reglas de asignación que sean no manipulables, al menos hay una regla de asignación que es no obviamente manipulable, en dicho contexto. Sorprendentemente mostramos que el resultado opuesto es válido para la regla de asignación hospital-óptimal que resulta ser obviamente manipulable incluso en el contexto particular de un modelo de matching uno a uno con contratos. Este resultado revela una diferencia sustancial entre los modelos con y sin contrato desde el punto de vista del comportamiento estratégico de los agentes. Finalmente, probamos que la regla de asignación hospital-óptimal no es obviamente manipulable en el contexto del modelo clásico de matching muchos a uno sin contratos y preferencias sustituibles para los hospitales.
Trabajo en conjunto con: Eliana Pepa Risma (Instituto de Matemática Aplicada San Luis (UNSL-CONICET)).
Referencias
[1] HATFIELD, J. AND P. MILGROM (2005): “Matching with contracts,” American Economic Review, 95, 913–935
[2] MARTÍNEZ, R., J. MASSÓ, A. NEME, AND J. OVIEDO (2004): “On group strategy-proof mechanisms for a many-to-one matching model,” International Journal of Game Theory, 33, 115–128.
[3] TROYAN, P. AND T. MORRILL (2020): “Obvious manipulations,” Journal of Economic The- ory, 185, 104970.
Jueves 21 de septiembre, 9:40 ~ 9:55
Trade-off between manipulability and dictatorial power: a proof of the Gibbard-Satterthwaite Theorem
Agustín G. Bonifacio
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.
By endowing the class of tops-only and efficient social choice rules with a dual order structure that exploits the trade-off between different degrees of manipulability and dictatorial power rules allow agents to have, we provide a proof of the Gibbard-Satterthwaite Theorem.
Referencias
[1] ARRIBILLAGA, R. P. AND J. MASSÓ (2016): “Comparing generalized median voter schemes according to their manipulability,” Theoretical Economics,11, 547-586.
[2] BARBERÀ, S. (2011): “Strategyproof social choice,” Handbook of Social Choice and Welfare, 2, 731-831.
[3] GIBBARD, A. (1973): “Manipulation of voting schemes: a general result,” Econometrica, 41, 587-601.
[4] MAUS, S., H.PETERS, AND T.STORCKEN (2007): “Anonymous voting and minimal manipulability,” Journal of Economic Theory, 135, 533-544.
[5] NINJBAT, U. (2012): “Another direct proof for the Gibbard–Satterthwaite Theorem,” Economics Letters, 116, 418-421.
[6] PATHAK, P. A. AND T. SÖNMEZ (2013): “School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability to manipulation,” American Economic Review, 103, 80-106.
[7] SATTERTHWAITE, M. A. (1975): “Strategy-proofness and Arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions,”Journal of Economic Theory,10,187-217.
[8] SEN, A. (2001): “Another direct proof of the Gibbard–Satterthwaite theorem,” Economics Letters, 70, 381-385.
Jueves 21 de septiembre, 10:30 ~ 10:45
Grafos circulantes singularmente coespectrales
Ezequiel Dratman
Universidad Nacional de General Sarmiento, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Un grafo $G=G(\mathbb{Z}_n,S)$ es circulante de orden $n$ si los vértices de $G$ son los elementos de $\mathbb{Z}_n$, e $ij$ es una arista de $G$ si y solo si $j-i\in S$, donde $S$ es un subconjunto de $\mathbb{Z}_n\setminus\{0\}$ cerrado con respecto a tomar inverso aditivo, es decir, $S=-S$. Es fácil de ver que la matriz de adyacencia $A_G$, para este tipo de grafos, es una matriz circulante para cierto orden de sus vértices. Los grafos circulantes han sido muy estudiados (ver [1] y las referencias presentes en él). En conexión con el espectro de los grafos circulantes, en 2006, So caracterizó aquellos que tienen autovalores enteros [2] y conjeturó que los grafos circulantes integrales son isomorfos si y solo si son coespectrales. Sander y Sander probaron esta conjetura en 2015 [3].
Recientemente, Conde, Dratman y Grippo presentaron condiciones necesarias y suficientes para que dos grafos sean singularmente coespectrales [4] (es decir los valores absolutos de sus autovalores no nulos coinciden). En el mismo artículo, presentan familias de parejas de grafos singularmente coespectrales no isomorfos y clases de grafos donde coespectralidad singular implica casi coespectralidad, es decir, que los autovalores no negativos coinciden, contados con multiplicidad.
La energía de un grafo fue definida por Gutman en 1978 como la suma de sus valores singulares contados con multiplicidad [5]. En 2005, Stevanović y Stanković probaron que casi todos los grafos circulantes son hiperenergéticos [6], es decir, sus energías son mayores que dos veces el número de vértices menos uno. Blackburn y Shparlinski, en 2008, encuentran cotas superiores e inferiores para la energía promedio de los grafos circulantes [7].
En esta comunicación, nos enfocamos en la búsqueda de familias de parejas de grafos circulantes no coespectrales singularmente coespectrales, con una cantidad de vértices par. Para una cantidad prima impar de vértices, probamos que no hay parejas de grafos circulantes singularmente coespectrales no isomorfos.
Trabajo en conjunto con: Cristian M. Conde (Universidad Nacional de General Sarmiento), Luciano N. Grippo (Universidad Nacional de General Sarmiento) y Melina Privitelli (Universidad Nacional de General Sarmiento).
Referencias
[1] E. A. Monakhova. A survey on undirected circulant graphs. Discrete Math. Algorithms Appl., 4(1), 2012.
[2] W. So. Integral circulant graphs. Discrete Mathematics, 306(1), 2006.
[3] J. W. Sander, T. Sander. On So’s conjecture for integral circulant graphs. Appl. Anal. Discrete Math., 9(1), 2015.
[4] C. M. Conde, E. Dratman, L. N. Grippo. Finding singularly cospectral graphs. Linear Multilinear Algebra, 71(3), 2023.
[5] I. Gutman. The energy of a graph: old and new results. In Algebraic combinatorics and applications (Gößweinstein, 1999), Springer, Berlin, 2001.
[6] D. Stevanović, I. Stanković. Remarks on hyperenergetic circulant graphs. Linear Algebra and its Applications, 400, 2005.
[7] S. R. Blackburn, I. E. Shparlinski. On the average energy of circulant graphs. Linear Algebra Appl., 428(8-9), 2008.
Jueves 21 de septiembre, 10:50 ~ 11:05
El Teorema General de Manipulabilidad para un modelo de matching muchos a muchos
Paola Belén Manasero
Universidad Nacional de San Luis (Dpto. de Matemática-IMASL), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
En este trabajo estudiamos un modelo de matching muchos a muchos. Estos modelos han sido útiles para estudiar problemas de asignación con la característica distintiva de que los agentes pueden dividirse en dos subconjuntos disjuntos (por ejemplo, empresas y trabajadores). Nuestro marco general asume la condición de sustituibilidad en todas las preferencias de los agentes. Esta condición, introducida por primera vez por Kelso y Crawgord (1982), es el requisito más débil en las preferencias para garantizar la existencia de matchings estables en un modelo muchos a muchos.
Estudiamos mercados de matching en los que se utilizan mecanismos centralizados para proponer a los participantes sus correspondientes parejas de un determinado matching estable. Estos mercados estudian propiedades que tienen implicaciones más prácticas y están relacionadas con los incentivos estratégicos de los agentes que participan en dichos mercados. Sin embargo, que un matching sea o no estable depende de las preferencias de los agentes y, dado que constituyen información privada, hay que pedírselas a los agentes; de ahí que puedan surgir informes poco veraces. Esta es la razón por la que la literatura sobre matching ha estudiado intensamente las propiedades estratégicas de las reglas (mecanismos) estables.
En este trabajo, además de la sustituibilidad, exigimos que las preferencias de los agentes satisfagan la ``ley de la demanda agregada (LAD)" (Alkan, 2002). Esta condición dice que cuando un agente elige de un conjunto ampliado, selecciona al menos tantos agentes como antes. Bajo estos dos supuestos sobre las preferencias, el conjunto de matching estables satisface el llamado Teorema del Hospital Rural, que afirma que cada agente es emparejado con el mismo número de compañeros en cada matching estable. En un modelo muchos a muchos, demostramos que la sustituibilidad de las preferencias y la LAD garantizan el Teorema General de Manipulabilidad, el cual afirma que para cada agente, si el resultado de la regla estable no es el matching estable óptimo para su lado del mercado, entonces es cierto que cada agente puede obtener una pareja mejor falseando sus preferencias. Además, demostramos que el Teorema General de Manipulabilidad falla cuando las preferencias de los agentes sólo satisfacen sustituibilidad. Este es uno de los resultados más importantes sobre propiedades estratégicas de las reglas estables.
Trabajo en conjunto con: Jorge Oviedo (Universidad Nacional de San Luis, Argentina).
Referencias
[1] ALKAN, A. (2002): “A class of multipartner matching markets with a strong lattice structure,” Economic Theory, 19, 737–746.
[2] KELSO, A. AND V. CRAWFORD (1982): “Job matching, coalition formation, and gross substitutes,” Econometrica, 50, 1483–1504.
Jueves 21 de septiembre, 11:10 ~ 11:50
Contando pasos para la re-estabilización
Pablo Neme
IMASL-UNSL, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
En los modelos de matching bilateral, uno de los mercados más estudiados son los mercados laborales descentralizados entre firmas y trabajadores. En estos mercados, las firmas tienen preferencias sobre los trabajadores y los trabajadores sobre las firmas. En este trabajo asumimos que las firmas no pueden despedir a sus trabajadores, y solo pueden contratar nuevos cuando tienen puestos vacantes. En este modelo de mercados, una situación común es que un trabajador desee mejorar su condición laboral, y para ello deberá renunciar a su puesto de trabajo para generar una cadena de vacancias en las firmas, en la cual una firma más deseada por este trabajador le realice una oferta y así mejorar su condición laboral. En este articulo presentamos un algoritmo que modela esta situación. Cuando se considera que los trabajadores tienen un costo por la espera de una nueva oferta, dicho algoritmo nos da la información necesaria para que un trabajador pueda tomar la decisión entre renunciar y esperar una nueva oferta, o mantener su actual puesto de trabajo.
Trabajo en conjunto con: Agustín Bonifacio (UNSL-IMASL), Nadia Guiñazú (UNSL-IMASL), Noelia Juarez (UNSL-IMASL) y Jorge Oviedo (UNSL-IMASL).
Jueves 21 de septiembre, 11:50 ~ 12:05
Propiedades de los elementos de un conjunto estable Von Neumann-Morgenstern
Andrés Mauricio Lucero Quevedo
Universidad Nacional de San Luis - Instituto de Matemática Aplicada 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.
En el modelo de matching uno a uno, la estabilidad se considera una propiedad central, aquí es equivalente a la estabilidad del core. Von Neumann y Morgenstern (1944) introdujeron la noción de conjunto estable de un juego cooperativo. La definición de conjunto estable depende crucialmente del concepto de dominancia. En el modelo uno a uno, un conjunto de matchings es un conjunto estable si satisface las condiciones de estabilidad interna y externa con respecto a esta relación de dominio. Von Neumann y Morgenstern (1944) demuestran una caracterización de los conjuntos estables. Ehlers (2007) ha demostrado que el conjunto de matchings en el core es un subconjunto de cualquier conjunto estable y un conjunto estable puede contener matchings que están fuera del core. Además, el conjunto estable puede no ser único. Motivados por esto: En este trabajo se estudiará qué propiedades debe cumplir, o no, un matching para pertenecer a conjunto estable. En base a estas propiedades, se dará una caracterización del core de cuando es, o no, un conjunto estable.
Referencias
[1] Ehlers, L. (2007), "Von Neumann-Morgenstern Stable Sets in Matching Problems," Journal of Economic Theory, 134, 537--547.
[2] Neumann, J. Von, y Morgenstern, O. (1944), Theory of Games and Economic Be-havior, Princeton University Press, Princeton, New Jersey.
[3] A. Roth y M. Sotomayor, Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, Cambridge University Press, Cambridge , 1990.
Jueves 21 de septiembre, 14:40 ~ 14:55
Dominación italiana en grafos con "pocos" caminos inducidos de 4 vértices
Lara Fernández
FCEIA (UNR) y CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Dado un grafo $G$ con conjunto de vértices $V$, decimos que $f:V\rightarrow \{0,1,2\}$ es una función de dominación italiana (o función de $\{2\}$-dominación romana) en $G$ si en cada $v\in V$ tal que $f(v)=0$, la suma de los valores asignados por $f$ a los vértices adyacentes a $v$ es al menos 2. Es decir que si $f(v)=0$, $v$ debe ser adyacente en $G$ a al menos un vértice $u$ con $f(u)=2$ o a dos vértices distintos $x,y$ tales que $f(x)=f(y)=1$. El peso de $f$ es la suma de $f(v)$ sobre $V$. El número de dominación italiana de $G$, $\gamma_{I}(G)$, es el menor peso entre todas las funciones de dominación italiana en $G$. La dominación italiana es una de las variantes de la dominación clásica (Berge, 1958) definida en los últimos años [2].
El problema de decisión asociado a este nuevo concepto, el problema de la función de dominación italiana (R2DP), consiste en decidir si existe en un grafo dado $G$, una función italiana de peso $\gamma_{I}(G)$. Desde el punto de vista de la complejidad computacional de problemas de decisión u optimización, R2DP es NP-difícil [2, 4], aunque se conocen algunas clases de grafos donde el problema se puede resolver eficientemente (entre ellas, en un trabajo previo mostramos un algoritmo eficiente que resuelve R2DP para cualquier grafo caterpillar [4]).
Un grafo es $F$-free si no tiene como subgrafo inducido a ningún miembro de $F$. Recientemente se ha demostrado que R2DP es NP-difícil para grafos $(2K_2,C_4,C_5)$-free (o grafos split) [3]. Claramente, como consecuencia, R2DP es NP-difícil aún para grafos $(2K_2, C_4)$-free. Por otro lado, en [1] se prueba que el problema puede resolverse en tiempo polinomial para grafos que son $(2K_2, C_4)$-free y además $P_4$-free (cografos); estos son los grafos threshold. Sin embargo, en [5] se había demostrado que R2DP puede resolverse en tiempo polinomial en todo cografo.
Resulta prometedor continuar el estudio de la complejidad computacional de R2DP en otras superclases de grafos threshold, y más aún, de cografos. Nos enfocamos entonces en aquellas familias de grafos definidas por la presencia de un número acotado de caminos con 4 vértices (o $P_4$s).
En el presente trabajo comenzamos estudiando cómo se comporta el número de dominación italiana ante diferentes operaciones entre grafos y, haciendo uso de la descomposición modular conocida de los cografos, presentamos una nueva demostración de la polinomialidad de R2DP en esta clase. Este enfoque nos permite probar la polinomialidad del problema en grafos $P_4$-sparse y en grafos $P_4$-tidy. Mostramos por último los avances obtenidos sobre grafos partner-limited, con el objeto de extender lo más posible la polinomialidad de R2DP, o en su defecto, determinar una frontera en esta línea.
Trabajo en conjunto con: Valeria Leoni (FCEIA (UNR) y CONICET, Argentina).
Referencias
[1] Chakradhar P, S. Venkata and R. Palagiri, Complexity of Roman $\{2\}$-domination and the double Roman domination in graphs, AKCE Intenational Journal of Graphs and Combinatorics, 17(3), pp.1081-1086, 2020.
[2] Chellali M., T. W Haynes, S. T, Hedetniemi and A.A. McRae, Roman $\{2\}$-domination, Discrete Appl. Math., 204, pp.22-28, 2016.
[3] Chen H. and Lu C. Roman $\{2\}$-Domination Problem in Graphs, Discussiones Mathematicae Graph Theory, 42(2), pp.641-660, 2022.
[4] Fernández, L. and Leoni V., New complexity results on Roman $\{2\}$-domination, RAIRO-Oper. Res., Forthcoming article, 2023. https://doi.org/10.1051/ro/2023049
[5] W. Klostermeyer and G. Mac Gillivray, Roman, italian and 2-domination, Journal of Combinatorial Mathematics and Combinatorial Computing, 108, pp.125-146, 2019.
Jueves 21 de septiembre, 15:00 ~ 15:15
Hacia una caracterización de grafos italianos y grafos sicilianos
Alberto José Ferrari
Universidad Nacional de Rosario, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Un subconjunto $D$ de vértices de un grafo $G$ es un conjunto dominante en $G$ si todo vértice fuera de $D$ es adyacente a al menos un vértice de $D$. El tamaño mínimo de un conjunto dominante en un grafo $G$ es llamado el número de dominación de $G$ y denotado por $\gamma(G)$ (Berge, 1958).
Numerosos y diversos problemas de la vida real pueden ser formulados como problemas de dominación en grafos, por ejemplo asignar recursos (usualmente escasos) a diferentes lugares de forma de cubrir una necesidad en ese lugar y su vecindad próxima. Muchas variantes de la dominación usual han sido y siguen siendo estudiadas en la literatura. En este trabajo nos enfocamos en dos variantes, la $\{2\}$-dominación y la dominación italiana.
Dado un grafo $G$ con conjunto de vértices $V$, una función de dominación italiana $f : V \rightarrow \{0, 1, 2\}$ tiene la propiedad de que para cada vértice $v\in V$ con $f(v) =0$, o bien existe un vértice $u$ adyacente a $v$ con $f(u) = 2$, o al menos dos vértices $x,\; y$ adyacentes a $v$ con $f(x)=f(y)=1$. El peso de una función de dominación italiana es el valor $f(V) = \sum_{v\in V} f(v)$. El mínimo peso de una función de dominación italiana en $G$ es llamado el número de dominación italiano de $G$ y denotado por $\gamma_{I}(G)$ [1]. La dominación italiana está fuertemente relacionada con la $\{2\}$-dominación, introducida por Hedetniemi et al. en 1991, en la que, además de la propiedad mencionada para la dominación italiana, también se pide que para cada vértice $v \in V$ con $f(v)=1$, exista al menos un vértice $u$ adyacente a $v$ con $f(u) \neq 0$. El mínimo peso de una función $\{2\}$-dominante en $G$ es llamado el número de $\{2\}$-dominación de $G$ y denotado por $\gamma_{\{2\}}(G)$.
Al comparar la dominación usual y la dominación italiana, en [1] los autores presentan la siguiente desigualdad: $\gamma(G) \leq \gamma_I(G) \leq 2\gamma(G)$. En [5] se define un grafo italiano $G$ como aquel tal que $\gamma_I(G) = 2\gamma(G)$. En [4] se presenta una caracterización de los grafos árboles italianos. Sin embargo no se conocía una caracterización general de los grafos italianos.
Claramente, si $G$ es un grafo italiano, conociendo el valor exacto y/o un algoritmo eficiente que encuentra $\gamma(G)$, se conocerá el valor exacto de $\gamma_I(G)$ y recíprocamente. De aquí la importancia de tener una caracterización de ellos o de algunas otras subclases. En este trabajo introducimos la definición de grafo I2a como aquel para el cual el rango de alguna función de dominación italiana de peso mínimo es $\{0,2\}$. Probamos que un grafo $G$ es I2a si y sólo si $G$ es italiano.
Por otro lado, en [6] los autores presentan la siguiente desigualdad: $\gamma_I(G) \leq \gamma_{\{2\}}(G)$ para todo grafo $G$. No es difícil probar que $\gamma_{\{2\}}(G)\leq 2 \gamma(G)$. En base a esto, nosotros introducimos una superclase de los grafos italianos: $G$ es un grafo siciliano si $\gamma_{I}(G)= \gamma_{\{2\}}(G)$.
En un trabajo reciente, el número $\gamma_{\{2\}}(G)$ fue obtenido para una clase relevante de grafos, la de los grafos web $G$ [2]. Nos propusimos entonces estudiar el número de dominación italiana para esta clase de grafos y en [3] mostramos cómo obtuvimos el valor de $\gamma_{I}(G)$ para todo grafo web $G$. Exhibimos una subfamilia infinita de grafos web que son sicilianos pero no italianos.
Con el objetivo de avanzar hacia una caracterización de los grafos sicilianos, en este trabajo nos enfocamos en los grafos complementos de los grafos bipartitos (co-bipartitos), obteniendo los valores de $\gamma_{I}(G)$ y $\gamma_{\{2\}}(G)$ para todo grafo co-bipartito $G$. Presentamos también una subfamilia infinita de grafos co-bipartitos que son sicilianos pero no italianos. Probamos que todo grafo siciliano no italiano y para el cual no existe una función de dominación italiana con rango $\{0,1\}$, tiene número de dominación italiana por lo menos 4. Encontramos condiciones necesarias para que dicha cota se alcance por igualdad.
Trabajo en conjunto con: Valeria Leoni (Conicet - Universidad Nacional de Rosario) y María Inés Lopez Pujato (Universidad Nacional de Rosario).
Referencias
[1] Chellali, M., Haynes, T. W., Hedetniemi, S. T., McRae, A. A., Roman {2}-domination, Discrete Appl. Math., 204, (2016) 22-28.
[2] Cheng, Y. J., Fu, H. L., Liu, C. A., The integer {k}-domination number of circulant graphs, Discrete Math. Algorithms Appl., 12, 4 (2020) 2050055, 1-9.
[3] Ferrari, A. J., Leoni, V., Lopez Pujato, M. I., Dominación italiana, 2-dominación y {2}-dominación en grafos, XVII Congreso Dr. Antonio Monteiro, (2023).
[4] Henning, M. A., Klostermeyer, W. F., Italian domination in trees, Discrete Appl. Math., 217, (2017) 557-564.
[5] Klostermeyer, W. F., MacGillivray, G., Roman, italian, and 2-domination, J. Combin. Math. Combin. Comput, 108, (2019) 125-146.
[6] Wang, C. X., Yang Y., Wang, H. J., Xu S. J., Roman {k}-domination in trees and complexity results for some classes of graphs, J. Comb. Optim., 42, (2021) 174-186.
Jueves 21 de septiembre, 15:20 ~ 15:35
Propiedades de los asociaedros de grafos
Ana Gargantini
Facultad de Ciencias Exactas y Naturales de la Universidad Nacional de Cuyo, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Una rotación en un árbol binario es una operación local y reversible sobre dicho árbol, que intercambia el nivel de un par de nodos adyacentes. Dado $n\in\mathbb{N}$, el asociaedro clásico $(n-1)$-dimensional se puede describir como el politopo cuyo 1-esqueleto es isomorfo al grafo de rotaciones de árboles binarios de $n$ nodos internos, es decir, el grafo cuyos vértices son todos los árboles binarios de $n$ nodos internos, y dos árboles son adyacentes si difieren en una rotación. Esta construcción se generaliza para definir el asociaedro de un grafo $G$ a partir del grafo de rotaciones de los árboles de búsqueda sobre $G$, recuperando familias conocidas de politopos como casos particulares: el asociaedro clásico como asociaedro de un camino, el permutoedro como asociaedro de un grafo completo, el cicloedro como asociaedro de un ciclo, entre otros [1].
Los asociaedros como politopos son objetos de interés en geometría discreta y topología algebraica, pero también admiten formulaciones que permiten establecer relaciones con distintos sistemas combinatorios. Las propiedades estructurales de los grafos que determinan los asociaedros resultan de utilidad debido a sus variadas aplicaciones. Estas van desde complejidad computacional hasta física [4] y biología [5]. Para el asociaedro clásico, se han estudiado y establecido distintos parámetros de grafos, entre ellos su diámetro [3]. Para el caso general, solo se conocen resultados sobre el diámetro de asociaedros de algunas familias de grafos [2]. En la actualidad esta sigue siendo un área de estudio abierta.
En esta comunicación, presentaremos resultados obtenidos a partir del estudio de distancias en asociaedros de grafos bipartitos completos. Además, mostraremos el efecto de eliminar ciertos subconjuntos de aristas de un grafo en el diámetro de su asociaedro, acotándolo inferior y superiormente. Mostraremos también cómo se pueden utilizar estas cotas en el cálculo de algunos diámetros de asociaedros de grafos bipartitos completos. Por otro lado, presentaremos algunos resultados sobre ciertos parámetros de asociaedros de grafos estrella, en particular su número de independencia y su número cromático.
Trabajo en conjunto con: Adrián Pastine (Instituto de Matemática Aplicada San Luis, CONICET-UNSL) y Pablo Torres (Universidad Nacional de Rosario - CONICET).
Referencias
[1] J. Cardinal, S. Langerman, P. Perez-Lantero, On the diameter of tree associahedra, Electronic Journal of Combinatorics, 25(4) (2018), P4.18.
[2] J. Cardinal, L. Pournin, M. Valencia-Pabon, Diameter estimates for graph associahedra, Annals of Combinatorics, 26 (2022), 873–902.
[3] L. Pournin, The diameter of associahedra, Advances in Mathematics, 259 (2014), 13–42.
[4] F. Santos, A counterexample to the Hirsch conjecture, Annals of Mathematics, 176 (2012), 383–412.
[5] C. Semple, M. Steel, Phylogenetics. Oxford Lecture Series in Mathematics and its Applications 24, Oxford University Press, 2003.
Jueves 21 de septiembre, 15:40 ~ 15:55
Problemas localmente verificables en grafos
Carolina Lucía Gonzalez
Instituto de Investigación en Ciencias de la Computación (UBA-CONICET), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Intuitivamente, un problema localmente verificable es un problema de partición de vértices (o, equivalentemente, de coloreo de vértices) para el cual una solución puede ser verificada simplemente chequeando una determinada propiedad local para cada vértice, es decir, una propiedad que involucra solamente la solución restringida al vértice y a sus vecinos. Este es el caso de diversas variantes de los problemas de dominación, conjunto independiente y $k$-coloreo, entre otros.
En esta presentación, la cual es una síntesis de los artículos [1,2,3], daremos una definición formal de lo que entendemos por problemas localmente verificables y estudiaremos bajo qué circunstancias podemos resolverlos eficientemente en distintas clases de grafos. Expresaremos su complejidad en función de los parámetros treewidth, clique-width y mim-width. Como consecuencia inmediata, podemos afirmar que múltiples problemas existentes en la literatura (por ejemplo, dominación Grundy, $k$-comunidad y $[k]$-dominación romana) se pueden resolver en tiempo polinomial en clases de grafos de treewidth acotada, clique-width acotada o mim-width acotada.
Trabajo en conjunto con: Narmina Baghirova (University of Fribourg, Suiza), Flavia Bonomo-Braberman (Instituto de Investigación en Ciencias de la Computación, UBA-CONICET, Argentina), Felix Mann (University of Fribourg, Suiza), Bernard Ries (University of Fribourg, Suiza) y David Schindl (University of Fribourg, Suiza).
Referencias
[1] N. Baghirova, C.L. Gonzalez, B. Ries y D. Schindl. Locally checkable problems parameterized by clique-width. 33rd International Symposium on Algorithms and Computation (ISAAC 2022), volume 248 of Leibniz International Proceedings in Informatics (LIPIcs), 31:1-31:20, 2022.
[2] F. Bonomo-Braberman y C.L. Gonzalez. A new approach on locally checkable problems. Discrete Applied Mathematics, 314:53-80, 2022.
[3] C.L. Gonzalez y F. Mann. On $d$-stable locally checkable problems on bounded mim-width graphs. arXiv:2203.15724 [cs.DM], 2022.
Jueves 21 de septiembre, 16:00 ~ 16:15
Todo conjunto parcialmente ordenado treelike es CPT
Noemí Amalia Gudiño
Centro de Matemática de La Plata, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Sea $\mathbf{P}=(X, P)$ un conjunto parcialmente ordenado o poset, un \textit{modelo de contención} de un poset asigna a cada elemento $x\in X$ un conjunto $M_x$ de tal manera que $(u, v) \in P$ si y solo si $M_u$ es un subconjunto propio de $M_v$. Si los conjuntos $M_x$ son caminos de un árbol se dice que el poset $\mathbf{P}$ admite un modelo de contención de caminos en un árbol (o que $\mathbf{P}$ es CPT). Un poset es \textit{treelike} si alguno de sus diagramas de Hasse asociados admite a un árbol como grafo cubrimiento. Un grafo es un \textit{grafo treelike} si es el grafo de comparabilidad de un poset treelike.
En [1] se obtuvo una caracterización por subposets prohibidos minimales en la clase de posets k-tree que son CPT. Un problema abierto en la clase de posets CPT es la caracterización por subposets prohibidos minimales. En este trabajo demostramos que los posets treelike son CPT.
Trabajo en conjunto con: Marisa Gutierrez (Centro de Matemática de La Plata, CONICET, Argentina).
Referencias
[1] On k-tree Containment Graphs of Paths in a Tree, L. Alcón, N. Gudiño, M. Gutierrez, Order vol. 38 (2021), pp. 229-244.
Jueves 21 de septiembre, 16:50 ~ 17:05
Sobre grafos de distancia 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 $k,r$ enteros positivos, definimos $[2k+r] = \{1,2,\ldots,2k+r\}$, y $[2k+r]^k$ el conjunto de $k$-subconjuntos de $[2k+r]$. El grafo de Kneser $K(2k+r,k)$ es el grafo cuyo conjunto de vértices es $[2k+r]^k$ y donde dos $k$-subconjuntos $A,B \in [2k+r]^k$ son adyacentes si y solo si $A \cap B = \emptyset$.
Sean $G = (V,E)$ un grafo y $D$ su diámetro. Para un entero fijo $d$, con $1 \leq d \leq D$, el grafo de $d$-distancia exacta de $G$, denotado por $G_{=d}$, es el grafo que posee el mismo conjunto de vértices $V$ de $G$, y donde dos vértices $a,b \in G_{=d}$ son adyacentes si y solo si su distancia en $G$ es igual a $d$. Este tipo de grafos ha sido estudiado mayormente por sus aplicaciones a problemas de coloreo.
En este trabajo caracterizamos la relación de adyacencia de los vértices en el grafo de $d$-distancia exacta de Kneser $K_{=d}(2k+r,k)$ y calculamos la función distancia entre cualquier par de vértices no adyacentes, en términos de la cardinalidad de su intersección como $k$-conjuntos de $[2k+r]^k$.
Trabajo en conjunto con: Mario Valencia-Pabon (Université de Lorraine, LORIA, Nancy, France) y Adrián Pastine (Instituto de Matemática Aplicada San Luis (UNSL-CONICET) y Departamento de Matemática, Universidad Nacional de San Luis, San Luis, Argentina).
Referencias
[1] Brešar, B., Gastineau, N., Klavžar, S., & Togni, O. (2019). Exact distance graphs of product graphs. Graphs and Combinatorics, 35(6), 1555-1569.
[2] Chen, Y., & Wang, Y. (2008). On the diameter of generalized Kneser graphs. Discrete mathematics, 308(18), 4276-4279.
[3] Frankl, P., & Füredi, Z. (1986). Extremal problems concerning Kneser graphs. Journal of Combinatorial Theory, Series B, 40(3), 270-284.
[4] Lovász, L. (1978). Kneser's conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory, Series A, 25(3), 319-324.
[5] Stahl, S. (1976). n-Tuple colorings and associated graphs. Journal of Combinatorial Theory, Series B, 20(2), 185-203.
[6] Valencia-Pabon, M., & Vera, J. C. (2005). On the diameter of Kneser graphs. Discrete mathematics, 305(1-3), 383-385.
Jueves 21 de septiembre, 17:10 ~ 17:25
Problema de la $\{k\}$-dominación total en nuevas subclases de grafos.
María Inés Lopez Pujato
Universidad Nacional de Rosario (FCEIA), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Los problemas de dominación total consisten en asignar recursos (usualmente escasos) a diferentes lugares, de forma de cubrir una necesidad en la vecindad próxima de ese lugar. Ejemplos de aplicaciones que pueden ser modeladas por estos problemas son los problemas de ubicación y/o asignación de servicios: cajeros automáticos, cámaras de seguridad, entre otros.
En este trabajo abordamos una variante del problema de dominación total que fue introducida en $[4]$ y está definida de la siguiente manera: dado un grafo $G$ con conjunto de vértices $V$ y un entero no negativo $k$ (fijo), una función $f:V\rightarrow \{0,1,\dots,k\}$ es una función $\{k\}$-dominante total de $G$ si $f\left(N(v)\right)\geq k$ para cada vértice $v$ del grafo $G$, donde $N(v)$ denota el subconjunto de los vértices adyacentes a $v$, y $f(U) = \sum_{v\in U} f(v)$ (peso de la función $f$ sobre el conjunto $U$) para cualquier $U\subset V$. El número de $\{k\}$-dominación total de $G$, $\gamma_{\{k\}}^{t}(G)$, es el peso de una función $\{k\}$-dominante total de $G$ de mínimo peso sobre el conjunto de vértices $V$. El problema de $\{k\}$-dominación total consiste en hallar este mínimo número para un grafo $G$ dado y un entero no negativo $k$. Para $k = 1$, este problema coincide con el de dominación total en grafos, muy estudiado en la literatura específica.
Respecto a la complejidad computacional, los problemas de decisión asociados a estos problemas son NP-difíciles para cada $k$ fijo ($[3]$ y $[5]$). Por otra parte, se conocen instancias donde se puede resolver en tiempo polinomial, ver por ejemplo $[1]$, $[2]$ y $[5]$. En $[2]$ se presenta el valor del número de $\{k\}$-dominación total para los grafos ciclos, caminos, grafos rueda (wheels) y grafos que consisten en la 1-suma de un ciclo y un camino de longitud dos (grafo pan).
Siguiendo esta línea de investigación, analizamos la complejidad del problema de $\{k\}$-dominación total en otras familias de grafos. Con el objetivo de completar este estudio en la clase de los grafos cactus (1-suma de caminos y ciclos) comenzamos estudiando los grafos obtenidos por 1-suma de un ciclo con un camino de cualquier longitud, superclase de los grafos pan. Hallamos el número de $\{k\}$-dominación total para esta familia, para todo entero no negativo ${k}$. Además, a partir de los resultados obtenidos y aquellos en [2], analizamos la $\{k\}$-dominación total sobre los grafos oruga (caterpillar).
Trabajo en conjunto con: Mariana Escalante (Conicet-UNR) y Valeria Leoni (Conicet-UNR)..
Referencias
[1] G. Argiroffo, V. Leoni and P. Torres, Complexity of k-tuple total and total $\{k\}$-dominations for some subclasses of bipartite graphs, Information Processing Letters 138 (2018) 75-80.
[2] T. Haisheng, L. Liuyan and L. Hongyu, Total $\{k\}$-domination in special graphs, Mathematical Foundations of Computing, 1, 3 (2018).
[3] J. He and H. Liang, Complexity of Total $\{k\}$-Domination and Related Problems, Lecture Notes in Computer Science 6681 (2011), 147-155.
[4] N. Li and X. Hou, On the total $\{k\}$-domination number of Cartesian products of graphs, J. Comb. Optim 18 (2009) 173-178.
[5] D. Pradhan, Algorithmic aspects of $\{k\}$-tuple total domination in graphs, Inform. Process. Lett. 112 (21) (2012) 816--822.
Jueves 21 de septiembre, 17:30 ~ 17:45
About of the determinant of graphs with a unique maximum matching.
Diego Gabriel Martinez
Departamento de Matemáticas, Universidad Nacional de San Luis -- Instituto de Matemáticas Aplicadas de San Luis -- CONICET, Argentina, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
The structure of graphs with a unique perfect matching - UPM graphs-, was studied by Kotzig in 1959 (see [1]). His mayor result was that every connected UPM graph has a bridge that belongs to the perfect matching. This result was strengthen by Wang, Shang and Yuan in 2015 via the Gallai-Edmonds Structure Theorem (see [2]). In this work we prove that if \(G\) is a KE and a UPM graph, then \(det(G)=(-1)^{\mu(G)}\), where \(\mu(G)\) is the matching number of \(G\). The FP-KE decomposition applied to UPM graph give us the following result: if \(G\) is a UPM graph, then \[ \det(G)=(-1)^{\mu(\text{KE}(G))}\det(\text{FP}(G)). \] Hence, if \(G\) is a UPM graph, then \(\det(G)=1\mod 2\).
Trabajo en conjunto con: Daniel A. Jaume(Departamento de Matemáticas, Universidad Nacional de San Luis -- Instituto de Matemáticas Aplicadas de San Luis -- CONICET, Argentina), Gonzalo Molina (Departamento de Matemáticas, Universidad Nacional de San Luis -- Instituto de Matem\'{a}ticas Aplicadas de San Luis -- CONICET, Argentina) y Cristian Panelo (Departamento de Matemáticas, Universidad Nacional de San Luis, Argentina)..
Referencias
[1] A. Kotzig. On the theory of finite graphs with linear factor II. Mat.- Fyz. Casopis. Slovensk. Akad. Vied, 9(3)(1959), p. 136-159
[2] Xiumei Wang, Weiping Shang, Jinjiang Yuan. On Graphs with Unique perfect Matching. Graphs ans Combinatorics(2015)
Jueves 21 de septiembre, 17:50 ~ 18:05
$R$-Secuenciabilidad de grupos no abelianos
María Valentina Soldera Ruiz
Departamento de Matemática, Universidad Nacional de San Luis, e IMASL (UNSL-CONICET), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Un grupo orden $n$ es $R$-secuenciable si existe una permutación de los elementos distintos a la identidad $$g_1,g_2,\ldots,g_{n-1}$$ de manera tal que los elementos de la sucesión \[ g_{1}^{-1}g_{2},g_{2}^{-1}g_3,\ldots,g_{n-2}^{-1}g_{n-1},g_{n-1}^{-1}g_{2} \] son todos distintos.
Se puede caraterizar a los grupos $R$-secuenciables a travez de digrafos completos de Cayley. El digrafo completo de Cayley de un grupo $G$ tiene por vértices los elementos de $G$ y arcos de la forma $(g,gs)$ para cada $g,s\in G$ con $s\neq e$. Un grupo $G$ es $R$-secuenciable si y solo si su digrafo completo de Cayley tiene un ciclo de longitud $|G|-1$ que utiliza un arco de la forma $(g,gs)$ para cada $s\in G\setminus\{e\}$.
El problema de $R$-secuenciabilidad ha sido muy estudiado a lo largo de los años. Los grupos abelianos $R$-secuenciables fueron caracterizados por Alspach, Kreher y Pastine en [1]; los diedrales por Keedwell en [3]; los diciclicos por Wang y Leonard en [4]; los de orden $pq$, con $p$ y $q$ primos impares distintos, por Keedwell en [3] y Wang y Leonard en [4]; y no abelianos de orden 27 por Bedford en [2]. Sin embargo, estos grupos forman solo una pequeña fracción de los grupos finitos. Por lo que queda mucho aún por hacer.
En este trabajo presentamos una herramienta para estudiar $R$-secuenciabilidad de grupos de orden impar a travez de subgrupos normales y grupos cocientes. Utilizando esta herramienta, demostramos que todos los grupos de orden coprimo con 30 son $R$-secuenciables, cubriendo un gran porcentaje de los grupos que restan por estudiar.
Trabajo en conjunto con: Adrián Pastine (Departamento de Matemática, Universidad Nacional de San Luis, e IMASL (UNSL-CONICET)).
Referencias
[1] B. Alspach, D. L. Kreher y A. Pastine, The Friedlander-Gordon-Miller Conjecture is true, Australian Journal of Combinatorics, Volumen 67, año 2017, pp. 11-24.
[2] D. Bedford, On groups of orders $p$, $p^2$, $pq$ and $p^3$, $p, q$ prime: their classification and a discussion as to whether they are super $P$-groups, Undergraduate Special Study, University of Surrey, año 1987.
[3] A. D. Keedwell, On the R-sequenceability and Rh-sequenceability of groups, Annals of Discrete Mathematics, Volumen 18, año 1983, pp. 535-548.
[4] C.-D. Wang and P. A. Leonard, More on sequences in groups, Australasian Journal of Combinatorics, Volumen 21, año 2000, pp. 187-196.
Viernes 22 de septiembre, 8:20 ~ 8:35
KE-index
Daniel Alejandro Jaume
Universidad Nacional de San Luis -- IMASL -- CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
In this work, we introduce the KE-index. The KE-index of a graph is defined as the difference between the vertex covering number and the matching number of the graph. This number measures, in some sense, how far a graph is from being a K\H{o}nig-Egerv\'{a}ry graph. We present several properties of the KE-index and demonstrate that various statements involving K\H{o}nig-Egerv\'{a}ry graphs are, in fact, general statements about graphs when considered in terms of the KE-index. We also provide lower and upper bounds for the K\H{o}nig Deletion Problem.
Trabajo en conjunto con: Gonzalo Molina (Universidad Nacional de San Luis).
Viernes 22 de septiembre, 8:40 ~ 9:20
El problema de Hamilton-Waterloo: historia, variaciones y últimos avances
Adrián Pastine
Departamento de Matemática, Universidad Nacional de San Luis, e IMASL (UNSL-CONICET), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
El problema de Hamilton-Waterloo es un problema clásico de descomposición de grafos, que yace en la intersección entre la teoría de grafos y la teoría de diseños combinatorios. Este tipo de problemas tienen aplicaciones en la construcción de otros objetos combinatorios y en el diseño de experimentos.
Un $k$-factor de un grafo es un subgrafo generador $k$-regular. En particular, un $1$-factor es un matching perfecto, y un $2$-factor es una unión disjunta de ciclos. Denotamos por $K_n^*$ al grafo completo $K_n$ de orden $n$ si $n$ es impar, y a $K_n$ menos las aristas de un $1$-factor si $n$ es par. Dados dos $2$-factores de $K_n^*$, $F_1$ y $F_2$, el problema de Hamilton-Waterloo estudia para qué valores de $r$ y $s$ es posible particionar las aristas de $K_n^*$ en $r$ copias de $F_1$ y $s$ copias de $F_2$. La mayor parte del estudio de este problema se realizó para el caso uniforme, que es cuando todos los ciclos de $F_1$ tiene un tamaño fijo $x$, y todos los ciclos de $F_2$ tienen un tamaño fijo $y$. De todos modos, quedan aún casos uniformes por estudiar, en particular cuando $x$ e $y$ son coprimos. En lo que respecta al caso no uniforme, hay muy poco hecho, por lo que queda aún mucho camino por recorrer.
En esta charla daremos un recuento histórico del problema, pasando por los resultados más importantes y presentando el estado del arte actual. Presentaremos algunas construcciones que hacen uso de grupos y de cuasigrupos, y algunas técnicas de producto de grafos y de duplicado de vértices. Hablaremos también de algunas variaciones del problema, como el problema de Hamilton-Waterloo de la luna de miel, y el problema de Hamilton-Waterloo sobre grafos equipartitos completos.
Viernes 22 de septiembre, 9:20 ~ 9:35
Espectro de la matriz de Harary del producto join de grafos regulares.
Luis Medina
Departamento de Matemáticas, Universidad de Antofagasta., Chile - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
La distancia entre dos vértices (de una misma componente conexa) es igual al número de lados del camino más corto que los une. La matriz de Harary es conocida también como la matriz recíproca de la distancia. Para un grafo de orden $n$, simple, conectado, sin pesos y no dirigido, la matriz de Harary es una matriz irreducible, no negativa y de orden $n$, tal que para i distinto de j, su entrada en la posición $(i,j)$ es igual al inverso multiplicativo de la distancia entre el vérice i y el vértice j, y si i=j, entonces la entrada $(i,i)$ es igual a cero. En esta charla se presentará una forma en bloques para la matriz de Harary del producto join de grafos. En el caso de que los grafos usados en el producto dado sean regulares, entonces se mostrará como obtener los autovalores de la matriz de Harary a través de matrices de orden menor al orden del grafo.
Trabajo en conjunto con: M. Trigo (Departamento de Matemáticas, Universidad de Antofagasta..
Referencias
[1] D. Cardoso, R. Diaz, O. Rojo, 2018. Distance matrices on the $H$-join of graphs: A general result and applications. Linear Algebra and its Applications, 559, 34-53.
[2] L. Medina, M. Trigo, 2021, Upper bounds and lower bounds for the spectral radius of Reciprocal Distance, Reciprocal Distance Laplacian and Reciprocal Distance signless Laplacian matrices, Linear Algebra and its Applications, 609: 386-412. DOI: 10.1016/j.laa.2020.09.024
[3] L. Medina, M. Trigo, 2021, Spectral radius of the Harary matrix of the join product of regular graphs, Journal of Physics: Conference Series 2090, 012103.
Viernes 22 de septiembre, 9:40 ~ 9:55
Estudio de una nueva modelización para problemas de locación de servicios.
María Inés Lopez Pujato
Universidad Nacional de Rosario (FCEIA), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Los empaquetamientos limitados en grafos fueron inicialmente introducidos en [3]. Algunas variantes de este concepto han sido definidas y estudiadas desde aquel trabajo de 2010 (algunos pueden verse en [1, 2, 4]). Todas ellas modelan diferentes problemas de locación de servicios (perjudiciales pero necesarios), en los cuales se requiere que en las cercanías de cada usuario se ubique un número acotado de éstos. El objetivo en estos problemas es maximizar el número de servicios a ubicar.
Con el propósito de abordar nuevas situaciones que requieren relajar condiciones sobre algunos usuarios del servicio a instalar, en este trabajo introducimos una nueva variante de este concepto. Dado un grafo $G$ con conjunto de vértices $V$, un vector $\mathbf{k}=(k_v)$ de capacidades enteras no negativas y vectores enteros $\mathbf{l}=(l_v)$ y $\mathbf{u}=(u_v)$, una función $f : V \rightarrow \mathbf{Z}^+$ es una función empaquetadora relajada en $G$ si $l_v\leq f(v)\leq u_v$ para cada $v\in V$ y tal que, para aquellos vértices $v$ para los cuales $f(v) > l_v$, $f$ satisface que la suma de sus valores sobre la vecindad cerrada de $v$ es a lo sumo $k_v$. El peso de una función empaquetadora relajada $f$ es $f(V) = \sum_{v\in V}f(v)$. Consideramos el problema de hallar una función empaquetadora relajada de máximo peso (número de empaquetamiento relajado) en un grafo dado. Pretendemos modelar, entre otras, situaciones que requieren que la acotación del número de servicios sea solo en las cercanías del usuario $v\in V$ en el que efectivamente se instaló al menos $l_v$ servicios.
Estudiamos diferentes instancias del problema general y para algunas de ellas, hallamos el valor exacto del número de empaquetamiento relajado.
Mostramos que es NP-completo decidir si un grafo dado tiene una función empaquetadora relajada de máximo peso, a través de una reducción al problema del máximo conjunto estable con pesos en un grafo.
Remarcamos que, mientras que todas las versiones de problemas de empaquetamientos estudiados en la literatura son NP-completos para grafos bipartitos, esta nueva variante se resuelve en tiempo polinomial para instancias dadas por grafos bipartitos.
Trabajo en conjunto con: M. P. Dobson (UNR), E. Hinrichsen (UNR) y V. Leoni (Conicet-UNR).
Referencias
[1] Bai X., H. Chang, X. Li, More on limited packings in graphs, Journal of Combinatorial Optimization 40, (2020), 412–430.
[2] Dobson M. P., E. Hinrichsen, V. Leoni, On the complexity of the {k}-packing functionproblem, International Transactions in Operational Research 24 (2017), 347-354.
[3] Gallant R., G. Gunther, B. Hartnell, D. Rall, Limited packing in graphs, Discrete Applied Mathematics 158 Issue 12 (2010), 1357–1364.
[4] Hinrichsen E., V. Leoni, M. Safe, Labelled packing functions in graphs, Inf. Processing Letters 154 (2020), doi.org/10.1016/j.ipl.2019.105863.
Viernes 22 de septiembre, 14:40 ~ 14:55
El problema del conjunto perfecto de aristas dominantes en grafos sin emparejamientos dominantes inducidos y grafos sin $P_6$ inducidos
Camilo Vera
Instituto de Cálculo, FCEN, UBA, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Dado un grafo $G = (V, E)$ y dos aristas $e,f\in E$, decimos que $e$ domina a $f$ si ambas comparten un extremo o bien si $e = f$. Un subconjunto $P$ de $E$ es un conjunto perfecto de aristas dominantes (PED por sus siglas en inglés) si toda arista de $E \setminus P$ es dominada por exactamente una arista de $P$. Por otro lado, decimos que un subconjunto $M$ de $E$ es un conjunto eficiente de aristas dominantes (EED por sus siglas en inglés) si toda arista de $E$ está dominada por exactamente una arista de $M$. Claramente, todo EED es un emparejamiento dominante inducido (DIM por sus siglas en inglés) y recíprocamente, todo DIM es un EED. No todo grafo tiene un DIM. En [2] se demostró que determinar la existencia de un DIM es un problema NP-completo. Notar que un DIM es un PED de cardinalidad mínima (ver [1]).
En este trabajo demostramos que encontrar un PED de tamaño a lo sumo $k$ en un grafo conexo que no contiene un DIM es NP-completo. Además se presenta un algoritmo de tiempo polinomial para encontrar un PED de cardinalidad mínima en grafos sin $P_6$ como subgrafo inducido. Este resultado se basa en una caracterización presentada en [3] para grafos sin $P_6$ como subgrafo inducido y extiende un resultado análogo para grafos sin $P_5$ como subgrafo inducido demostrado en [4].
Trabajo en conjunto con: Luciano N. Grippo (Universidad Nacional de General Sarmiento, Argentina) y Min C. Lin (Universidad de Buenos Aires, Argentina).
Referencias
[1] C. L. Lu, M. T. Ko, C. Y. Tang, Perfect edge domination and efficient edge domination in graphs, Discrete Applied Mathematics 119 (2002)
[2] D. L. Grinstead, P. J. Slater, N. A. Sherwani, N. D. Holmes, Efficient edge domination problems in graphs, Inform. Process. Lett. 48 (5) (1993)
[3] Pim van’t Hof, D. Paulusma, A new characterization of $P_6$-free graphs, Discrete Applied Mathematics 158 (2010)
[4] M. C. Lin, V. Lozin, V. A. Moyano, J. L. Szwarcfiter, Perfect edge domination: hard and solvable cases, Ann. Oper. Res. 264:287-305 (2018)
Viernes 22 de septiembre, 15:00 ~ 15:15
Grafos cuyo cuadrado de línea es libre de $P_k$*
Martina Vergara
Departamento de Matemática, UNS e INMABB, UNS-CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
El grafo de línea de un grafo $G$, denotado $L(G)$, tiene un vértice por cada arista de $G$ y dos vértices de $L(G)$ son adyacentes si y solo si corresponden a aristas que comparten un extremo. El cuadrado de un grafo $G$, denotado $G^2$, tiene los mismos vértices que $G$ y dos vértices de $G^2$ son adyacentes si y solo si están unidos en $G$ por un camino de longitud a lo sumo $2$. Denotamos por $P_k$ al camino sin cuerdas con $k$ vértices. Un grafo es libre de $P_k$ si no contiene $P_k$ como subgrafo inducido.
Dos aristas se dicen independientes si no comparten extremos ni son ambas incidentes a una arista en común. El problema del Matching Inducido Máximo consiste en encontrar un conjunto de aristas independientes dos a dos de cardinalidad máxima. El problema del Conjunto Independiente Máximo consiste en hallar un conjunto de vértices no adyacentes dos a dos de máxima cardinalidad. Claramente, resolver el problema de Matching Inducido Máximo en un grafo $G$ es equivalente a resolver el problema de Conjunto Independiente Máximo en $L(G)^2$. Este hecho implica que el problema de Matching Inducido Máximo puede resolverse en tiempo polinomial (resp. cuasipolinomial) en la clase de todos los grafos $G$ tales que $L(G)^2\in\mathcal H$, para cada clase de grafos $\mathcal H$ en la cual el problema de Conjunto Independiente Máximo puede resolverse en tiempo polinomial (resp. cuasipolinomial).
Por ejemplo, una clase de grafos $\mathcal H$ en la cual el problema de Conjunto Independiente Máximo puede resolverse en tiempo polinomial es la clase de los grafos cordales [2]. Luego, el problema del Matching Inducido Máximo puede resolverse en tiempo polinomial en la clase de los grafos $G$ tales que $L(G)^2$ es cordal. Una caracterización de la clase de tales grafos $G$, por subgrafos inducidos prohibidos minimales, fue dada por Scheidweiler y Wiederrecht [4].
Una clase de grafos $\mathcal H$ en la cual el problema de Conjunto Independiente Máximo puede resolverse en tiempo cuasipolinomial es la clase de los grafos libres de $P_k$, para cada $k$ [1]. En consecuencia, si $\mathcal G_k$ es la clase de los grafos $G$ tales que $L(G)^2$ es libre de $P_k$ entonces el problema de Matching Inducido Máximo puede resolverse en tiempo cuasipolinomial en $\mathcal G_k$, cualquiera sea $k$. Hatzel y Wiederrecht [3] estudiaron el problema de caracterizar la clase $\mathcal G_k$ por subgrafos inducidos prohibidos. Sin embargo, su caracterización no es por subgrafos inducidos prohibidos minimales, pues algunos de los subgrafos prohibidos contienen a otros como subgrafos inducidos propios.
En este trabajo, obtenemos una caracterización por subgrafos inducidos prohibidos minimales de la clase $\mathcal G_k$, para cada $k$. Cada familia de subgrafos inducidos prohibidos minimales queda caracterizada mediante un conjunto de cadenas aceptadas por un autómata finito determinista.
*Este trabajo fue financiado parcialmente por el subsidio PGI 24/L115 de la Universidad Nacional del Sur. M.D. Safe fue financiado parcialmente por el subsidio PIBAA 28720210101185CO del CONICET.
Trabajo en conjunto con: Martín D. Safe (Departamento de Matemática, UNS e INMABB, UNS-CONICET).
Referencias
[1] P. Gartland and D. Lokshtanov. Independent set on Pk-free graphs in quasi-polynomial time. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pages 613–624. IEEE Computer Soc., Los Alamitos, CA, 2020.
[2] F. Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput., 1(2):180–187, 1972.
[3] M. Hatzel and S. Wiederrecht. On perfect linegraph squares. In Graph-theoretic Concepts in Computer Science, volume 11159 of Lecture Notes in Comput. Sci., pages 252–265. Springer, Cham, 2018.
[4] R. Scheidweiler and S. Wiederrecht. On chordal graph and line graph squares. Discrete Appl. Math., 243:239–247, 2018.
Viernes 22 de septiembre, 15:20 ~ 15:35
Sobre la coordinación de los complementos de línea de árboles*
Rocío Belén Suárez Albanesi
Departamento de Matemática, UNS e INMABB, UNS-CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Los grafos coordinados [1] son aquellos en los cuales, para todo subgrafo inducido, coinciden el grado clique (que es el cardinal máximo de un conjunto de cliques maximales que comparten todas un mismo vértice) y el número clique-cromático (que es el mínimo número de colores necesario para pintar las cliques maximales de modo que dos cliques maximales con el mismo color no compartan vértices).
La clase de grafos coordinados es hereditaria, es decir, cerrada por subgrafos inducidos. Por lo tanto, admite una caracterización por subgrafos inducidos prohibidos minimales. Si bien no se conoce una descripción completa de la lista de subgrafos inducidos prohibidos minimales para la clase de los grafos coordinados, sí se han obtenido resultados parciales para aquellos grafos coordinados dentro de las clases de los grafos de línea y de los complementos de árboles [3] y las clases de los grafos libres de paw y de los libres simultáneamente de gem, 4-wheel y bull [2]. Cada una de estas caracterizaciones conduce a un algoritmo de tiempo polinomial (o incluso lineal) para el reconocimiento de los grafos coordinados dentro de cada una de estas clases. Sin embargo, se sabe que la clase de los grafos coordinados admite familias de grafos prohibidos minimales cuya cardinalidad crece exponencialmente con el número de vértices [4] y que el reconocimiento de grafos coordinados es NP-duro en general [5].
En este trabajo, buscamos caracterizar por subgrafos inducidos prohibidos minimales cuándo un complemento de un grafo de línea de un árbol $T$ es coordinado. Conjeturamos una caracterización por subgrafos inducidos prohibidos minimales y la demostramos para todos los árboles $T$ con diámetro a lo sumo 5. Más aún, demostramos que para probar que la conjetura es cierta, alcanza con demostrarla para los árboles cuyo diámetro es 6.
*Este trabajo fue financiado parcialmente por el subsidio PGI 24/L115 de la Universidad Nacional del Sur. M.D. Safe fue financiado parcialmente por el subsidio PIBAA 28720210101185CO del CONICET.
Trabajo en conjunto con: Martín D. Safe (Departamento de Matemática, UNS e INMABB, UNS-CONICET).
Referencias
[1] F. Bonomo, G. Durán, and M. Groshaus. Coordinated graphs and clique graphs of clique-Helly perfect graphs. Util. Math., 72:175-191, 2007.
[2] F. Bonomo, G. Durán, F. Soulignac, and G. Sueiro. Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs. Discrete Appl. Math., 157(17):3511-3518, 2009.
[3] F. Bonomo, G. Durán, F. Soulignac, and G. Sueiro. Partial characterizations of coordinated graphs: line graphs and complements of forests. Math. Oper. Res., 69(2):251–270, 2009.
[4] F. Soulignac and G. Sueiro. Exponential families of minimally non-coordinated graphs. Rev. Un. Mat. Argentina, 50(1):75–85, 2009.
[5] F. Soulignac and G. Sueiro. NP-hardness of the recognition of coordinated graphs. Ann. Oper. Res., 169(1):17–34, 2009.
Viernes 22 de septiembre, 15:40 ~ 15:55
Rango de matriz de distancia en grafos
Verónica Moyano
Universidad Nacional de General Sarmiento, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Dado un grafo conexo $G$ con vértices $V=\{v_1,...,v_n\}$, se define la entrada $(i,j)$ de la matriz de distancia $D(G)$ como la distancia entre los vértices $v_i$ y $v_j$ en $G$. Usando resultados de la teoría de Ramsey probamos que para cada entero $k\geq 2$, existe una cantidad finita de grafos cuya matriz de distancia tienen rango $k$. Además describimos los grafos cuyas matrices de distancia tienen rango 2 y 3.
Se definen los grafos trivially perfect como los grafos en que, para todo subgrafo inducido $H$ el tamaño del conjunto independiente máximo en $H$ coincide con la cantidad de cliques maximales en $H$. Veremos que en esta clase de grafos se cumple que para cada $\eta\geq 1$ existe un grafo trivially perfect cuya matriz de distancia tiene nulidad $\eta$. Además, para los grafos threshold, una subfamilia de los trivially perfect, veremos que la nulidad está acotada por 1.
Trabajo en conjunto con: Ezequiel Dratman (Universidad Nacional de General Sarmiento), Luciano Grippo (Universidad Nacional de General Sarmiento), Adrián Pastine (Universidad Nacional de San Luis).
Viernes 22 de septiembre, 16:00 ~ 16:15
Estudios de complejidad del problema de mínima violación cromática en grafos
María Elisa Ugarte
Facultad de Ciencias Exactas, Ingeniería y Agrimensura - Universidad Nacional de Rosario, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
El \emph{problema de mínima violación cromática} (PMVC) [1] es una generalización del problema clásico de coloreo de vértices (PCV). Dado un grafo $G=(V,E)$, un conjunto especial de aristas $F\subseteq E$ (a las que llamamos \emph{débiles}) y un conjunto finito $\mathcal C$ de colores, decimos que una función $\phi : V \rightarrow \mathcal C$ es un \emph{semi-coloreo} de $(G,F)$ si es un coloreo propio de $G\setminus F$ (es decir, se permite asignar el mismo color a los extremos de aristas débiles). La \emph{violación cromática} de $\phi$ sobre $(G,F)$ es el número $\nu (G,F,\phi) := | \{ij\in F: \phi(i) = \phi(j)\}|$, i.e., la cantidad de aristas débiles de $G$ cuyos extremos reciben el mismo color. El PMVC para un grafo $G$ y un conjunto de aristas débiles $F\subseteq E$ consiste en encontrar un semi-coloreo $\phi$ de $(G,F)$ con mínimo valor de $\nu (G,F,\phi)$. Este valor representa el \emph{número de violación cromática} de $(G,F)$ y se denota como $\chi_{\mathsf{v}}(G,F,\mathcal C)$. El PMVC es NP-difícil ya que el problema de hallar un coloreo de $G$ con $|\mathcal C|$ colores es el caso particular de PMVC que fija $F=\emptyset$.\\
En [1] se abordan estudios poliedrales de una formulación de programación entera para el PMVC proponiendo familias de desigualdades válidas y condiciones para que las mismas definan facetas. Por otro lado, en [2] se estudia el problema de separación de estas familias de desigualdades y se implementan rutinas de separación para un algoritmo de planos de corte.\\
En el presente trabajo estudiamos la complejidad del PMVC en distintas clases de grafos. Como resultado principal, probamos que el PMVC continúa siendo NP-difícil aún cuando nos restringimos a instancias donde $G\setminus F$ pertenece a una clase de grafos $\mathcal H$ definida en función de otra familia de grafos $\mathcal G$ para la cual el problema de \emph{precoloring extension} [3] es NP-difícil [4,5]. Esto nos permite demostrar la NP-dificultad de PMVC cuando $G\setminus F$ es un grafo de intervalos unitarios o un grafo distancia-hereditario, entre otros casos particulares. Por otro lado, proponemos y analizamos un algoritmo de tiempo polinomial para el PMVC, para el caso en que el grafo $G$ pertenece a una subclase de los grafos de intervalos unitarios.
Trabajo en conjunto con: Diego Delle Donne (ESSEC Business School of Paris, Cergy-Pontoise, France) y Mariana Escalante (FCEIA, Universidad Nacional de Rosario - CONICET, Argentina).
Referencias
[1] M. Braga, D. Delle Donne, M. Escalante, J. Marenco, M. E. Ugarte, M. C. Varaldo, The minimum chromatic violation problem: a polyhedral approach. Discrete Applied Mathematics - 281 (2020) 69--80.
[2] D. Delle Donne, M. Escalante, M. E. Ugarte, Implementing cutting planes for the chromatic violation problem. Proceedings of the Joint ALIO/EURO International Conference 2021-2022 on Applied Combinatorial Optimization, OpenProceedings.org (2022) 17--22.
[3] M. Biró, M. Hujter, Zs. Tuza, Precoloring extension. I. Interval graphs. Discrete Mathematics - 100 (1992)267--279.
[4] D. Marx, Precoloring extension on unit interval graphs. Discrete Applied Mathematics - 154 (2006) 995-- 1002.
[5] F. Bonomo , G. Durán, J. Marenco, Exploring the complexity boundary between coloring and list-coloring. Annals of Operations Research - 169 (2009) 3--16.
Viernes 22 de septiembre, 16:20 ~ 16:35
Empaquetamientos generalizados en grafos con clique-width acotado
Natalí Romina Vansteenkiste
Facultad de Ciencias Exactas, Ingeniería y Agrimensura, UNR - CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Los empaquetamientos en grafos modelan problemas de ubicación de recursos, como por ejemplo de puntos de venta en un mercado saturado, donde es necesario imponer restricciones de máxima cantidad de unidades a ser ubicadas en un lugar y en su vecindad.
Dado un grafo $G=(V,E)$ y $\mathbf k, \mathbf u\in \mathbb Z_+^V$, un $(\mathbf k, \mathbf u)$-empaquetamiento de $G$ es una función $f:V\rightarrow \mathbb Z_{+}$ que satisface $0\leq f(v)\leq u(v)$ y $f(N[v])\leq k(v)$, para todo $v\in V$. El problema de optimización asociado (PEG) consiste en calcular el valor máximo de $f(V)$ entre todos los $(\mathbf k, \mathbf u)$-empaquetamientos $f$ de $G$. Con respecto al análisis de complejidad computacional, es útil considerar instancias de PEG con capacidades acotadas por una constante, esto es, dado $M\in \mathbb Z_+$, notamos $M$-PEG a PEG reducido a instancias donde $\mathbf \leq M \mathbf{1}$. En la literatura se han estudiado otros problemas de empaquetamiento en grafos [3, 4, 5, 6], todos los cuales pueden ser pensados como el PEG con restricciones sobre $\mathbf k$ y $\mathbf u$ en sus instancias. Entre los resultados de complejidad computacional de estos problemas, en [2] se prueba que en grafos dualmente cordales el PEG es NP-difícil y resulta polinomial cuando se reduce a instancias donde $\mathbf u=\mathbf k= \mathbf 1 k$ , para un $k\in \mathbb Z_+$ fijo, llamadas funciones $\{k\}$-empaquetadoras.
En lo referido a grafos con \emph{clique-width} acotado, a partir del Teorema de Courcelle [1] se prueba la polinomialidad del PEG reducido a instancias donde $\mathbf{u}= \mathbf 1$ y $\mathbf k=k \mathbf 1$ para un $k\in \mathbb Z_+$ fijo (empaquetamientos $k$-limitados). Una reducción polinomial entre los dos problemas permitió tambien demostrar la polinomialidad para el caso de funciones $\{k\}$-empaquetadoras [5]. Con el objetivo de obtener resultados más generales en clases de grafos con clique-width acotado, en [7] se trabaja con el PEG en grafos $P_4$-\emph{tidy} a partir de su descomposición modular. Se presentan fórmulas para resolver el PEG en la unión y join de grafos generales y se inicia el estudio sobre los grafos quasi-arañas. Para instancias con $\textbf{k}\in \mathbb Z_+^V$ y $\textbf{u}\geq \textbf{k}$ se resuelve en grafos arañas flacas y se obtienen resultados parciales para grafos arañas gordas.
En este trabajo se prueba que el $M$-GPF es polinomial en grafos con \emph{clique-width} acotado y se presenta un algoritmo lineal para el GPF en arañas gordas sin cabeza, que deriva en un algoritmo polinomial específico para el PEG en la subclase de grafos $P_4$-\emph{sparce}.
Trabajo en conjunto con: Erica Hinrichsen (Universidad Nacional de Rosario, Argentina) y Graciela Nasini (Universidad Nacional de Rosario, CONICET, Argentina).
Referencias
[1] Courcelle, B., Makowsky J. A., Rotics U.: Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width. Theory of Computing Systems 33, 125--150, 2000.
[2] Dobson, M. P., Hinrichsen, E., Leoni, V.: On the complexity of the {k}-packing function problem, International Transactions in Operational Research 24, 347–354, 2017.
[3] Dobson M. P., Leoni V., Nasini G.: The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs. Electron. Notes Discrete Math., 36(23-24):559-556, 2010.
[4] Gallant R., Gunther G., Hartnell B. L., Rall D.: Limited packings in graphs. Discrete Appl. Math., 158(12):1357-1364, 2010.
[5] Hinrichsen E. G. Leoni V.: {k}-packing functions of graphs. Lecture Notes in Comput. Sci., 8596:325-335, 2014.
[6] Hinrichsen E. G., Leoni V., Safe M.D.: Labelled packing functions in graphs. Inform. Process. Lett., 154:105863, 7, 2020.
[7] Hinrichsen E., Nasini G., Torres P., Vansteenkiste N.: Problema de empaquetamiento generalizado en grafos con pocos P4's, LXVIII Reunión Anual de Comunicaciones Científicas UMA 2019.
Viernes 22 de septiembre, 16:40 ~ 16:55
Sobre la familia de grafos con 1-persistencia en la relajación clique.
Lucía Moroni
Facultad de Ciencias Exactas, Ingeniería y Agrimensura-Universidad Nacional de Rosario, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
En este trabajo avanzamos en el estudio de la propiedad de 1-persistencia sobre la relajación por cliques del poliedro de conjuntos estables de un grafo $G$, QSTAB($G$). En general, se dice que un poliedro $P\subset [0,1]^n$ tiene la propiedad de 1-persistencia si para todo $c\in \mathbb{R}^n$ y $x^*$ solución óptima de $\max\{cx:\ x\in P\}$, existe una solución óptima $y^*$ del problema $\max\{cx:\ x\in P\cap\{0,1\}^n\}$ tal que $y^*_j=x^*_j$ si $x^*_j=1$. La validez de esta propiedad permite el diseño de rutinas iterativas de búsqueda de soluciones enteras fijando variables en 1 en cada paso y reoptimizando sobre instancias más pequeñas del problema. Esta propiedad se relaciona con otra propiedad más fuerte, la de 0,1-persistencia, analizada en [1].
En [2,3] se demostró que, para todo grafo $G$ en cierta superclase de grafos libres de patas (paw-free), QSTAB($G$) verifica la propiedad de 1-persistencia, pero también que existen grafos para los cuales esto no ocurre. Llamando $F$ a la familia de todos los grafos $G$ tales que QSTAB($G$) sí tiene la propiedad, presentaremos resultados sobre el comportamiento de esta familia bajo algunas operaciones en grafos. En particular, veremos que la familia es cerrada para la operación de borrado de un nodo, y por ello que cualquier subgrafo inducido $G'$ de un grafo $G$ en $F$ también pertenece a la familia.
Siendo la familia $F$ hereditaria en ese sentido, conocer los grafos mas pequeños que no pertenecen a ella implicaría una caracterización de la misma. Definimos que un grafo $G$ es $mnF$ si $G$ no pertenece a $F$ pero todo subgrafo inducido propio sí está en la familia. En esta linea de trabajo, presentaremos una descripción parcial de los grafos $mnF$.
Trabajo en conjunto con: Diego Delle Donne (ESSEC Business School of Paris, Cergy-Pontoise, Francia), Mariana Escalante (Universidad Nacional de Rosario- CONICET, Argentina) y Pablo Fekete (Universidad Nacional de Rosario, Argentina).
Referencias
[1] E. Rodríguez-Heck, K. Stickler, M. Walter, S. Weltge. ``Persistency of Linear Programming Relaxations for the Stable Set Problem.'' Bienstock D., Zambelli G. (eds) Integer Programming and Combinatorial Optimization. IPCO 2020. Lecture Notes in Computer Science, vol 12125. Springer, Cham.
[2] Moroni, L. ``Propiedad de Persistencia en la relajación clique del poliedro de conjuntos estables de un grafo.'' Tesina de Licenciatura en Matemática. FCEIA. UNR (Aprobada el 23 de marzo de 2023).
[3] Delle Donne, D., Escalante, M., Fekete, P., Moroni, L. ``Sobre la propiedad de persistencia en la relajación clique del poliedro de los conjuntos estables en un grafo''. Comunicación científica en la Reunión Anual de la Unión Matemática Argentina (UMA) 2022, ciudad de Neuquén, Argentina. Septiembre de 2022.