UMA 2022
Reunión Anual de la Unión Matemática Argentina
Estudiamos las implicaciones de la noción de "no obviamente manipulable" para las reglas de votación. Dicha noción, es un debilitamiento de la clásica noción de ser a prueba de estrategia, que proporciona incentivos para que los agentes revelen las verdaderas preferencias en un contexto donde tienen incertidumbre respecto de las preferencias de los demás agentes. Primero mostramos que para reglas que sólo dependen del top la noción de "no obviamente manipulable" es equivalente a que cada vetador es fuertemente vetador. Luego, nos enfocamos en dos familias de métodos de votación (que sólo dependen de los tops): reglas de votante mediano y votaciones por comités. Proporcionamos caracterizaciones completas en cada familia de aquellas reglas que son no obviamente manipulables.
Trabajo en conjunto con: Agustin Bonifacio (IMASL (UNSL-CONICET)).
In a many-to-one matching model with responsive preferences in which indifferences are allowed, we study three notions of core, three notions of stability, and their relationships. We show that (i) the core contains the stable set, (ii) the strong core coincides with the strongly stable set, and (iii) the super core coincides with the super stable set. We also show how the core and the strong core in markets with indifferences relate to the stable matchings of their associated tie-breaking strict markets.
Trabajo en conjunto con: Agustín G. Bonifacio (UNSL- IMASL, Argentina), P. Neme (UNSL- IMASL, Argentina), J. Oviedo (UNSL- IMASL, Argentina).
It is known that a coalition formation game may not have a stable coalition structure. In this study, we propose a new solution concept for these games, which we call “stable decomposition”, and show that each game has at least one. This solution consists of a collection of coalitions organized in sets that “protect” each other in a stable way. When sets of this collection are singletons, the stable decomposition can be identified with a stable coalition structure. As an application, we study convergence to stability in coalition formation games.
Trabajo en conjunto con: Agustín Bonifacio (IMASL-UNSL) y Elena Iñarra (Universidad del País Vasco, España).
En 1947 Tutte demostro que un grafo $G$ tiene matching perfecto si y sólo si para todo $S\subseteq V(G)$ se cumple que $c_0(G-S)\leq |S|$, donde $c_0(G-S)$ denota la cantidad de componentes impares de $G-S$.
En este trabajo damos dos nuevas caracterizaciones de grafos con matching perfecto, la primera en función de la descomposición $F\!P$-$K\!E$ del grafo; y la segunda en función de la relación entre el número de independencia, número de matching y número de cubrimiento. Así, para todo grafo $G$, las siguientes afirmaciones son equivalentes: para todo $S\subseteq V(G)$ se cumple que $c_0(G-S)\leq |S|$; la parte $F\!P(G)$ no tiene flowers y la parte $K\!E(G)$ tiene matching perfecto; el número de independencia de $G$ es igual a dos veces el número de matching de $G$ menos el número de cubrimiento de $G$.
Trabajo en conjunto con: Daniel A. Jaume (Universidad Nacional de San Luis, Argentina) y Gonzalo Molina (Universidad Nacional de San Luis, Argentina).
Introducimos una nueva clase de grafos de intersección, los Grafos Arista Intersección de Caminos en una Grilla Triangular, llamados grafos EPG$_{t}$. Comparamos esta nueva clase con la bien conocida clase de los grafos EPG. Un giro de un camino en un punto de la grilla es llamado un bend. Una representación EPG$_{t}$ en la cual todo camino tiene a lo sumo $k$ bends es llamada una representación B$_k$-EPG$_{t}$ y los grafos correspondientes son llamados grafos B$_k$-EPG$_{t}$. Caracterizamos la representación de los cliques con tres vértices y los $4$-ciclos inducidos en representaciones B$_{1}$-EPG$_{t}$.
Además, consideramos el problema de clique coloración, esto es, colorear los vértices de un grafo dado de modo que ningún clique (maximal) esté monocoloreado. En general, clique coloración puede ser un problema bien diferente del problema de coloración usual de vértices. La principal diferencia es que clique coloración no es una propiedad hereditaria, es decir, un grafo puede ser $k$-clique coloreable y tener un subgrafo inducido que no lo es. Otra diferencia es que aún los grafos que son $2$-clique coloreables pueden tener cliques arbitrariamente grandes. Sin embargo, la clique coloración tiene algunas similitudes con la coloración usual de vértices. Por ejemplo, toda $k$-coloración es también una $k$-clique coloración. Más aún, si $G$ es un grafo libre de triángulos, el número clique cromático y el número cromático de $G$ coinciden. En este trabajo, probamos que los grafos B$_{1}$-EPG$_{t}$ son $7$-clique coloreables.
Trabajo en conjunto con: Vitor Tocci F. de Luca (Universidade do Estado do Rio de Janeiro, Brasil), Fabiano S. Oliveira (Universidade do Estado do Rio de Janeiro, Brasil) y Jayme Szwarcfiter (Universidade Federal do Rio de Janeiro, Brasil).
Introducimos una nueva descomposición de grafos en función de la pertenencia o no de un vértice a un flower o un posy. Un grafo $G$ puede descomponerse en dos partes, la parte König-Everváry, $K\!E(G)$, y la parte flower-posy, $F\!P(G)$. Probamos que todo matching máximo de $G$ es la unión de un matching máximo de $F\!P(G)$ y un matching máximo de $K\!E(G)$. Además, probamos que $\alpha(G)=\alpha(F\!P(G))+\alpha(K\!E(G))$, donde $\alpha(G)$ es un número de independencia de $G$.
Trabajo en conjunto con: Daniel A. Jaume (Universidad Nacional de San Luis, Argentina).
Un poliedro $P\subset [0,1]^n$ tiene la propiedad de \emph{$0,1$-persistencia} [4] si para toda función objetivo lineal, dada una solución óptima $x^*$ del problema de optimización sobre $P$, siempre existe una solución $y^*$ del problema restringido a variables enteras tal que coincide con $x$ en todas las variables con valores 0 o 1 de ésta. Es decir, 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\in \{0,1\}.$ La validez de esta propiedad permite el diseño de rutinas iterativas de búsqueda de soluciones enteras fijando variables en 0 o 1 en cada paso y reoptimizando sobre instancias más pequeñas del problema.
Resulta conveniente distinguir esta propiedad de la que llamaremos $1$-persistencia, en la que se requiere que sólo las variables $x_j^*=1$ mantengan su valor en la solución óptima $y^*$.
En [3] se demostró que, para todo grafo $G$, la relajación por aristas del poliedro de conjuntos estables, $FRAC(G)$, tiene la propiedad de $1$-persistencia (y por lo tanto, por la estructura del problema, la $0,1$-persistencia).
Respecto a otras relajaciones propias del poliedro de los conjuntos estables distintas de $FRAC(G)$, el reciente trabajo [4] muestra que ninguna de ellas verifica la propiedad de $0,1$-persistencia para todo grafo $G$, dejando abierto en particular el interrogante sobre una caracterización de la familia $\mathcal{F}$ de grafos para los cuales la relajación por cliques, $QSTAB(G)$ sí posee la propiedad.
En este trabajo comenzamos el estudio de los grafos de la familia $\mathcal{F}$ con la propiedad de $1$-persistencia, donde pertenecen trivialmente los grafos perfectos, aquellos con clique máxima 2 y antiagujeros impares, entre otros.
Avanzando en este estudio probamos que una superclase de grafos libre de patas (paw-free) también son elementos de $\mathcal{F}$ y vale la propiedad de $1$-persistencia.
Completar una caracterización de $\mathcal{F}$ adquiere una especial relevancia en el contexto del análisis de la propiedad de $0,1$-persistencia para relajaciones del problema de coloreo de un grafo, ya que la formulación por representantes para un grafo $G$ [1,2] tiene la particularidad de coincidir con $QSTAB(G')$ para un cierto grafo $G'$ construido a partir de $G$.
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] M. Campêlo, R. Corrêa, Y. Frota, Cliques, holes and the vertex coloring polytope, Inform. Process. Lett. 89 (2004) 159-164.
[2] Delle Donne, Diego Andrés. Estudios poliedrales de problemas de coloreo de grafos. Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2016.
[3] G. Nemhauser and L. Trotter. Vertex packings: Structural properties and algorithms. Mathematical Programming, 8(1) (1975) 232-248.
[4] E. Rodríguez-Heck, K. Stickler, M. Walter, S. Weltge. Persistency of Linear Programming Relaxations for the Stable Set Problem. In: Bienstock D., Zambelli G. (eds) Integer Programming and Combinatorial Optimization. IPCO 2020. Lecture Notes in Computer Science, vol 12125. Springer, Cham.
En este trabajo damos una formula explicita para la nulidad minima posible entre todos los grafos uniciclios que comparten un misma secuencia de grados. Especificamente demostramos que la nulidad minima es $2n_1 -n+2$ si $ n_1 \geq \frac{n}{2}~\land~n-n_1 -n_2\leq 2$, $2n_1 -n$ si $n_1\geq \frac{n}{2}~\land~n-n_1 -n_2 > 2$, $1$ si $n_1= \frac{n-1}{2}$ y 0 en el resto de los casos, donde $n_1$ es la cantidad de $1's$ y $n_2$ la cantidad de $2's$ en la secuencia de grados.
Trabajo en conjunto con: Daniel A. Jaume (Universidad Nacional de San Luis, Argentina), Gonzalo Molina (Universidad Nacional de San Luis, Argentina) y Maikon Machado Toledo (Universidade Federal de Rio Grande do Sul, Brasil).
In this work, we use the null decomposition of unicyclic graphs in order to show that the core-nilpotent decomposition of \(A(U)\), the adjacency matrix of a unicyclic graph \(U\), can be obtained directly from the unicyclic graph itself. In other words, we give two invertible matrices \(Q\) and \(K\), expressed in terms of some adjacency relations of \(U\), such that \(Q^{-1}A(U)Q\) is a \(2\times 2\) blocks diagonal matrix, whose first block is \(K\), a \(r\times r\) matrix such that \(rk(K) = rk(A(U)) = r\), and whose second block is a zero matrix.
Trabajo en conjunto con: Maikon Machado Toledo (Universidade Federal do Rio Grande do Sul), Gonzalo Molina (Universidad Nacional de San Luis) y Cristian Panelo (Universidad Nacional de San Luis).
Dado un grafo $G$ con conjunto de vértices $V$, decimos que $f=(V_0,V_1, V_2)$ es una función de dominación italiana (o función de $\{2\}$-dominación romana) en $G$ si $\{V_0,V_1, V_2\}$ es una partición de $V$ de tal modo que cada vértice de $V_0$ es adyacente en $G$ a al menos dos vértices de $V_1$ o a uno de $V_2$. El peso de $f$, $w(f)$, es la suma de $f(v)$ sobre $V$. Denotamos por $\gamma_{I}(G)$ al menor peso entre todas las funciones italianas en $G$ y lo denominamos número de dominación italiana de $G$. Esta es una de las variantes de la dominación clásica (Berge, 1958) definida más recientemente [2].
El problema de decisión asociado a este nuevo concepto, el problema de la función de dominación italiana, 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, este problema, como lo es el de dominación usual, es NP-difícil [2]. Resultados muy recientes muestran nuevas clases de grafos donde el mismo se mantiene NP-difícil [1].
Por otra parte, se conocen cotas para el número $\gamma_{I}(G)$ de un grafo $G$ general, como así también algoritmos exactos para hallar $\gamma_{I}(G)$ cuando $G$ es un camino o $G$ es un ciclo [2]. Además, el estudio de la dominación italiana sobre los grafos árboles fue iniciado en [3], pero no desde el punto de vista de la complejidad computacional, sino siguiendo la línea de estudio que brindan las cotas halladas en [2], mostrando caracterizaciones de aquellos árboles para los cuales algunas de esas cotas se verifican por igualdad.
En el presente trabajo abordamos el estudio de este nuevo problema en una subclase propia de los grafos árboles, la de los grafos caterpillar. $G$ es un grafo caterpillar si es conexo y consiste de un camino principal junto con vértices de grado uno adyacentes a algún vértice del camino principal. En particular, aplicamos resultados generales mostrados en [2] al estudio de la dominación italiana en grafos caterpillar.
Trabajo en conjunto con: Valeria Leoni (Universidad Nacional de Rosario y CONICET; valeoni@fceia.unr.edu.ar).
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 (2020), 3, 1081-1086.
[2] Chellali M., T. W Haynes, S. T, Hedetniemi and A.A. McRae, Roman {2}-domination, Discrete Appl. Math., 204 (2016), 22-28.
[3] Henning M. and W. Klostermeyer, Italian domination in trees, Discrete Appl. Math. 217 (2017) 557-564.
La dominación en grafos es uno de los tópicos más fértiles en el área. Esta dio lugar a muchas variantes que han sido estudiadas en diversas clases de grafos, entre ellas en Grafos de Kneser, como por ejemplo en [1], [2], [3], [4].
Dados dos naturales $n$, $r$ con $n > 2r$, el grafo de Kneser $Kn(n,r)$ tiene conjunto de vértices $V=\{v\subseteq [n]:|v|=r\}$ y conjunto de aristas $E=\{uv:u\cap v=\emptyset\}$.
Entre las variantes más estudiadas de dominación, se encuentra la $k$-upla dominación. Dados un grafo $G=(V,E)$ y un número natural $k\leq \delta(G)+1$, un conjunto $k$ -upla dominante $D$ es un subconjunto de $V$ tal que $|N[u]\cap D|\geq k$ para cada $u\in V$. El número de $k$-upla dominación $\gamma_{\times k}(G)$ es el mínimo cardinal de un conjunto $k$-upla dominante de $G$.
En este trabajo estudiamos la $k$-upla dominación en grafos de Kneser. Obtenemos cotas generales para $\gamma_{\times k}(Kn(n,r))$ y demostramos que en algunos casos son ajustadas. Analizamos los conjuntos $k$-upla dominantes para el caso $r=2$ lo que nos permite obtener nuevas cotas y valores exactos para $\gamma_{\times k}(Kn(n,2))$.
Trabajo en conjunto con: Pablo Torres (UNR - CONICET, Argentina).
Referencias
[1] Behtoei, A., & Jalilolghadr, P. (2020). Total dominator chromatic number of Kneser graphs. arXiv preprint arXiv:2001.00221.
[2] Brešar, B., Kos, T., & Torres, P. D. (2019). Grundy domination and zero forcing in Kneser graphs. ARS MATHEMATICA CONTEMPORANEA, 17(2), 419-430.
[3] Gorodezky, I. (2007). Dominating sets in Kneser graphs (Master’s thesis, University of Waterloo)
[4] Östergård, P. R., Shao, Z., & Xu, X. (2014). Bounds on the domination number of Kneser graphs. ARS MATHEMATICA CONTEMPORANEA, 9(2), 187-195.
El grafo de Kneser $Kg(n,k)$ tiene como vértices los subconjuntos de tamaño $k$ de un conjunto base de tamaño $n$. Uno de los problemas abiertos más importantes en lo que respecta a grafos de Kneser es el de Hamiltonicidad, es decir, si todo grafo de Kneser conexo tiene un camino o ciclo que pase por todos los vértices. Como estrategia para la búsqueda de esta estructura, nos enfocamos en encontrar caminos o ciclos en subgrafos de $Kg(n,k)$, con la idea de luego conectarlos para obtener un camino o ciclo de Hamilton en el grafo. Para definir los subgrafos en vez de trabajar con un conjunto base cualquiera, tomamos el conjunto $\{1,2,\ldots,n\}$, y definimos subgrafos poniendo restricciones en los subconjuntos de tamaño $k$. Así, por ejemplo, el grafo estable de $Kg(n,k)$ se obtiene al prohibir que el conjunto tenga elementos consecutivos de manera cíclica. Es decir que un vértice no puede contener subconjuntos de la forma $\{i,i+1\}$ o $\{1,n\}$. En un trabajo anterior demostramos que los grafos estables conexos tienen un ciclo de Hamilton. En este trabajo nos concentramos en buscar caminos y ciclos en los grafos casi estables, cuyos vértices tienen exactamente un par de elementos cíclicamente consecutivos.
Trabajo en conjunto con: Adrián Pastine (IMASL (CONICET) - UNSL).
Una matriz $A \in \{0, 1\}^{n\times m}$ es balanceada [1] si no contiene como submatriz una matriz cuadrada con exactamente dos $1$ por fila y por columna. Un grafo es balanceado [2] si su matriz de incidencia cliques maximales vs. vértices es balanceada. Bonomo, Durán, Lin y Szwarcfiter [5] probaron que un grafo es balanceado si y sólo si no contiene soles impares generalizados como subgrafos inducidos. Sin embargo, esta caracterización no es una caracterización por subgrafos inducidos prohibidos minimales ya que algunos soles impares generalizados contienen otros soles impares generalizados como subgrafos inducidos propios. No se conoce todavía una caracterización por subgrafos inducidos prohibidos minimales de la clase de grafos balanceados. A pesar de esto, existen algunas caracterizaciones parciales en esta dirección.
Un grafo es clique-Helly hereditario (CHH) [9] si todo subgrafo inducido satisface que la intersección de cualquier familia no vacía de cliques maximales que se intersecan dos a dos es no vacía. Todo grafo balanceado es CHH [1]. Un grafo es clique-perfecto si el tamaño máximo de un conjunto independiente de cliques (conjunto de cliques maximales disjuntas dos a dos) y el tamaño mínimo de un conjunto transversal de las cliques (conjunto de vértices que interseca todas las cliques maximales) coinciden para todo subgrafo inducido. Todo grafo balanceado es clique-perfecto [3]. Llamamos claw al grafo bipartito completo $K_{1,3}$. Bonomo, Chudnovsky y Durán [4] probaron que un grafo libre de claw CHH es clique-perfecto si y sólo si no tiene agujeros impares ni antiagujeros de longitud $7$ como subgrafos inducidos.
En nuestro trabajo, probamos que un grafo libre de claw es balanceado si y sólo si es perfecto y CHH o, equivalentemente, si no contiene agujeros impares, antiagujeros de longitud $7$, ni pirámides como subgrafos inducidos. La demostración de este teorema se basa en la caracterización de las descomposiciones por clique-cutsets de los grafos libres de claw perfectos que fue presentada por Chvátal y Sbihi en [6], y refinada por Maffray y Reed en [8], junto con la caracterizacicón de matrices balanceadas por bicoloreos dada por Berge en [1]. Este resultado refina el resultado de Bonomo, Chudnovsky y Durán [4] mostrando que todo grafo libre de claw CHH perfecto no solo es clique-perfecto, sino también balanceado. Como consecuencia de esta caracterización, probamos que existe un algoritmo con complejidad temporal $\mathcal{O}(nm^2)$ que, dado un grafo, determina si es libre de claw balanceado y, en caso que no lo sea, da un certificado de que no lo es. Nuestro algoritmo se basa en el algoritmo de Tarjan [10] para construir una descomposición por clique-cutsets de un grafo dado y el algoritmo de Lin y Szwarcfiter [7] para el reconocimiento de grafos CHH.
Trabajo en conjunto con: Guillermo Durán (Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires (UBA) e Instituto de Cálculo, UBA-CONICET, Buenos Aires, Argentina) y Martín D. Safe (Departamento de Matemática, Universidad Nacional del Sur (UNS) e INMABB, UNS-CONICET, Bahía Blanca, Argentina).
Referencias
[1] C. Berge. “Balanced matrices”. En: Math. Programming 2.1 (1972), págs. 19-31.
[2] C. Berge y V. Chvátal, eds. Topics on perfect graphs. Vol. 88. North-Holland Mathematics Studies. Annals of Discrete Mathematics, 21. North-Holland, Amsterdam, 1984, págs. xiv+369.
[3] C. Berge y M. Las Vergnas. “Sur un théorème du type König pour hypergraphes”. En: Ann. New York Acad. Sci. 175 (1970), págs. 32-40.
[4] F. Bonomo, M. Chudnovsky y G. Durán. “Partial characterizations of clique-perfect graphs. I. Subclasses of claw-free graphs”. En: Discrete Appl. Math. 156.7 (2008), págs. 1058-1082.
[5] F. Bonomo, G. Durán, M. C. Lin y J. L. Szwarcfiter. “On balanced graphs”. En: Math. Program. 105.2-3, Ser. B (2006), págs. 233-250.
[6] V. Chvátal y N. Sbihi. “Recognizing claw-free perfect graphs”. En: J. Combin. Theory Ser. B 44.2 (1988), págs. 154-176.
[7] M. C. Lin y J. L. Szwarcfiter. “Faster recognition of clique-Helly and hereditary clique-Helly graphs”. En: Inform. Process. Lett. 103.1 (2007), págs. 40-43.
[8] F. Maffray y B. A. Reed. “A description of claw-free perfect graphs”. En: J. Combin. Theory Ser. B 75.1 (1999), págs. 134-156.
[9] E. Prisner. “Hereditary clique-Helly graphs”. En: J. Combin. Math. Combin. Comput. 14 (1993), págs. 216-220.
[10] R. E. Tarjan. “Decomposition by clique separators”. En: Discrete Math. 55.2 (1985), págs. 221-232.
Un torneo es un digrafo que tiene un arco por cada par de vértices. Un torneo es transitivo si, dados tres vértices cualesquiera $a, b, c$ se verifica la transitividad, es decir si $(a,b)$ y $(b,c)$ son arcos del digrafo, entonces $(a,c)$ es un arco del digrafo. Todo torneo transitivo tiene una fuente y un sumidero. Consideramos torneos transitivos maximales por contención. El digrafo de intersección de torneos transitivos maximales $\tau$ se define de la siguiente manera:
V($\tau$(D)) es el conjunto de todos los torneos transitivos maximales de D.
A($\tau$(D)) es el conjunto de arcos definido por: si $T_1$ y $T_2$ son torneos transitivos maximales de D y $f_1, f_2, s_1, s_2$ son sus fuentes y sumideros correspondientes, entonces $T_1 \rightarrow T_2$ si y solo si $s_1, f_2\in T_1 \cap T_2$ y $f_1, s_2\notin T_1 \cap T_2$.
Un grafo es de indiferencia si tiene un orden de indiferencia, es decir un orden total en sus vértices $v_1,...,v_n$ tal que si $i < j < k$, $v_i \sim v_k$ entonces $v_i \sim v_j$ y $v_j \sim v_k$.
Fue probado en [1] que la clase de grafos de indiferencia es una clase cerrada respecto al operador clique. Un digrafo es un digrafo de indiferencia orientado si es un digrafo de indiferencia cuyos arcos fueron orientados de manera que si $v_1, v_2,v_3,...,v_n$ es un orden de indiferencia y $v_i \sim v_j$, $v_i \rightarrow v_j$ si y solo si $i < j$. En este trabajo se demuestra que la clase de grafos de indiferencia orientados es una clase cerrada respecto al operador $\tau$.
Trabajo en conjunto con: Marisa Gutierrez (Centro de Matemática, Universidad Nacional de La Plata, Argentina) y Bernardo Llano (Departamento de Matemática, UAM, México).
Referencias
[1] HEDMAN, B; Clique Graphs of Time Graphs; JOURNAL OF COMBINATORIAL THEORY(1984), Series B 37, 270-278